Optimization and Control
- [1] arXiv:2405.09660 [pdf, ps, other]
-
Title: Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement LearningSubjects: Optimization and Control (math.OC); Machine Learning (cs.LG)
Two-time-scale optimization is a framework introduced in Zeng et al. (2024) that abstracts a range of policy evaluation and policy optimization problems in reinforcement learning (RL). Akin to bi-level optimization under a particular type of stochastic oracle, the two-time-scale optimization framework has an upper level objective whose gradient evaluation depends on the solution of a lower level problem, which is to find the root of a strongly monotone operator. In this work, we propose a new method for solving two-time-scale optimization that achieves significantly faster convergence than the prior arts. The key idea of our approach is to leverage an averaging step to improve the estimates of the operators in both lower and upper levels before using them to update the decision variables. These additional averaging steps eliminate the direct coupling between the main variables, enabling the accelerated performance of our algorithm. We characterize the finite-time convergence rates of the proposed algorithm under various conditions of the underlying objective function, including strong convexity, convexity, Polyak-Lojasiewicz condition, and general non-convexity. These rates significantly improve over the best-known complexity of the standard two-time-scale stochastic approximation algorithm. When applied to RL, we show how the proposed algorithm specializes to novel online sample-based methods that surpass or match the performance of the existing state of the art. Finally, we support our theoretical results with numerical simulations in RL.
- [2] arXiv:2405.09727 [pdf, ps, html, other]
-
Title: Inference in higher-order undirected graphical models and binary polynomial optimizationSubjects: Optimization and Control (math.OC)
We consider the problem of inference in higher-order undirected graphical models with binary labels. We formulate this problem as a binary polynomial optimization problem and propose several linear programming relaxations for it. We compare the strength of the proposed linear programming relaxations theoretically. Finally, we demonstrate the effectiveness of these relaxations by performing a computational study for two important applications, namely, image restoration and decoding error-correcting codes.
- [3] arXiv:2405.09832 [pdf, ps, html, other]
-
Title: Mixed-Integer Linear Optimization for Cardinality-Constrained Random ForestsComments: 16 pages,3 figures. arXiv admin note: text overlap with arXiv:2401.09848, arXiv:2303.12532Subjects: Optimization and Control (math.OC)
Random forests are among the most famous algorithms for solving classification problems, in particular for large-scale data sets. Considering a set of labeled points and several decision trees, the method takes the majority vote to classify a new given point. In some scenarios, however, labels are only accessible for a proper subset of the given points. Moreover, this subset can be non-representative, e.g., due to collection bias. Semi-supervised learning considers the setting of labeled and unlabeled data and often improves the reliability of the results. In addition, it can be possible to obtain additional information about class sizes from undisclosed sources. We propose a mixed-integer linear optimization model for computing a semi-supervised random forest that covers the setting of labeled and unlabeled data points as well as the overall number of points in each class for a binary classification. Since the solution time rapidly grows as the number of variables increases, we present some problem-tailored preprocessing techniques and an intuitive branching rule. Our numerical results show that our approach leads to a better accuracy and a better Matthews correlation coefficient for biased samples compared to random forests by majority vote, even if only few labeled points are available.
- [4] arXiv:2405.09869 [pdf, ps, html, other]
-
Title: Optimality conditions at infinity for nonsmooth minimax programmingComments: 18 pagesSubjects: Optimization and Control (math.OC)
This paper is devoted to study of optimality conditions at infinity in nonsmooth minimax programming problems and applications. By means of the limiting subdifferential and normal cone at infinity, we dirive necessary and sufficient optimality conditions of Karush--Kuhn--Tucker type for nonsmooth minimax programming problems with constraint. The obtained results are applied to a nonsmooth vector optimization problem.
- [5] arXiv:2405.09927 [pdf, ps, html, other]
-
Title: Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution StrategyComments: Accepted by ICML 2024Subjects: Optimization and Control (math.OC); Machine Learning (cs.LG)
This work focuses on addressing two major challenges in the context of large-scale nonconvex Bi-Level Optimization (BLO) problems, which are increasingly applied in machine learning due to their ability to model nested structures. These challenges involve ensuring computational efficiency and providing theoretical guarantees. While recent advances in scalable BLO algorithms have primarily relied on lower-level convexity simplification, our work specifically tackles large-scale BLO problems involving nonconvexity in both the upper and lower levels. We simultaneously address computational and theoretical challenges by introducing an innovative single-loop gradient-based algorithm, utilizing the Moreau envelope-based reformulation, and providing non-asymptotic convergence analysis for general nonconvex BLO problems. Notably, our algorithm relies solely on first-order gradient information, enhancing its practicality and efficiency, especially for large-scale BLO learning tasks. We validate our approach's effectiveness through experiments on various synthetic problems, two typical hyper-parameter learning tasks, and a real-world neural architecture search application, collectively demonstrating its superior performance.
- [6] arXiv:2405.09973 [pdf, ps, html, other]
-
Title: Adaptive Ensemble Control for Stochastic Systems with Mixed Asymmetric Laplace NoisesSubjects: Optimization and Control (math.OC)
This paper presents an adaptive ensemble control for stochastic systems subject to asymmetric noises and outliers. Asymmetric noises skew system observations, and outliers with large amplitude deteriorate the observations even further. Such disturbances induce poor system estimation and degraded stochastic system control. In this work, we model the asymmetric noises and outliers by mixed asymmetric Laplace distributions (ALDs), and propose an optimal control for stochastic systems with mixed ALD noises. Particularly, we segregate the system disturbed by mixed ALD noises into subsystems, each of which is subject to a specific ALD noise. For each subsystem, we design an iterative quantile filter (IQF) to estimate the system parameters using system observations. With the estimated parameters by IQF, we derive the certainty equivalence (CE) control law for each subsystem. Then we use the Bayesian approach to ensemble the subsystem CE controllers, with each of the controllers weighted by their posterior probability. We finalize our control law as the weighted sum of the control signals by the sub-system CE controllers. To demonstrate our approach, we conduct numerical simulations and Monte Carlo analyses. The results show improved tracking performance by our approach for skew noises and its robustness to outliers, compared with single ALD based and RLS-based control policy.
- [7] arXiv:2405.09986 [pdf, ps, other]
-
Title: Integral action feedback design for conservative abstract systems in the presence of input nonlinearitiesLing Ma (LAGEPP), Vincent Andrieu (LAGEP, CNRS), Daniele Astolfi (CNRS, LAGEPP), Mathieu Bajodek (LAGEPP, CPE), Cheng-Zhong Xu (LAGEP), Xuyang LouSubjects: Optimization and Control (math.OC)
In this article, we present a stabilization feedback law with integral action for conservative abstract linear systems subjected to actuator nonlinearity. Based on the designed control law, we first prove the well-posedness and global asymptotic stability of the origin of the closed-loop system by constructing a weak Lyapunov functional. Secondly, as an illustration, we apply the results to a wave equation coupled with an ordinary differential equation (ODE) at the boundary. Finally, we give the simulation results to illustrate the effectiveness of our method.
- [8] arXiv:2405.10002 [pdf, ps, html, other]
-
Title: Rapid stabilization and finite time stabilization of the bilinear Schr\"odinger equationSubjects: Optimization and Control (math.OC); Analysis of PDEs (math.AP)
We propose a method to establish the rapid stabilization of the bilinear Schrödinger control system and its linearized system, and the finite time stabilization of the linearized system using the Grammian operators. The analysis of the rapid stabilization involves a new quantity (variable) which is inspired by the adjoint state in the optimal control theory and is proposed in our recent work on control systems associated with strongly continuous group. The analysis of the finite time stabilization follows the strategy introduced by Coron and Nguyen in the study of the finite time stabilization of the heat equation and incorporate a new ingredient involving the estimate of the cost of controls of the linearized system in small time derived in this paper.
- [9] arXiv:2405.10074 [pdf, ps, html, other]
-
Title: Planning and Optimizing Transit LinesSubjects: Optimization and Control (math.OC)
For all line-based transit systems like bus, metro and tram, the routes of the lines and the frequencies at which they are operated are determining for the operational performance of the system. However, as transit line planning happens early in the planning process, it is not straightforward to predict the effects of line planning decisions on relevant performance indicators. This challenge has in more than 40 years of research on transit line planning let to many different models.
In this chapter, we concentrate on models for transit line planning including transit line planning under uncertainty. We pay particular attention to the interplay of passenger routes, frequency and capacity, and specify three different levels of aggregation at which these can be modeled.
Transit line planning has been studied in different communities under different names.The problem can be decomposed into the components line generation, line selection, and frequency setting. We include publications that regard one of these individual steps as well as publications that combine two or all of them. We do not restrict to models build with a certain solution approach in mind, but do have a focus on models expressed in the language of mathematical programming. - [10] arXiv:2405.10083 [pdf, ps, html, other]
-
Title: Two person non-zero-sum linear-quadratic differential game with Markovian jumps in infinite horizonSubjects: Optimization and Control (math.OC)
This paper investigates an inhomogeneous non-zero-sum linear-quadratic (LQ, for short) differential game problem whose state process and cost functional are regulated by a Markov chain. Under the $L^2$ stabilizability framework, we first provide a sufficient condition to ensure the $L^2$-integrability of the state process and study a class of linear backward stochastic differential equation (BSDE, for short) in infinite horizon. Then, we seriously discuss the LQ problem and show that the closed-loop optimal control is characterized by the solutions to coupled algebra Riccati equations (CAREs, for short) with some stabilizing conditions and a linear BSDE. Based on those results, we further analyze the non-zero-sum stochastic differential game problem and give the closed-loop Nash equilibrium through the solution to a system of two cross-coupled CAREs and two cross-coupled BSDEs. Finally, some related numerical
- [11] arXiv:2405.10221 [pdf, ps, html, other]
-
Title: Scalarisation-based risk concepts for robust multi-objective optimisationComments: The code is available at: this https URLSubjects: Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML)
Robust optimisation is a well-established framework for optimising functions in the presence of uncertainty. The inherent goal of this problem is to identify a collection of inputs whose outputs are both desirable for the decision maker, whilst also being robust to the underlying uncertainties in the problem. In this work, we study the multi-objective extension of this problem from a computational standpoint. We identify that the majority of all robust multi-objective algorithms rely on two key operations: robustification and scalarisation. Robustification refers to the strategy that is used to marginalise over the uncertainty in the problem. Whilst scalarisation refers to the procedure that is used to encode the relative importance of each objective. As these operations are not necessarily commutative, the order that they are performed in has an impact on the resulting solutions that are identified and the final decisions that are made. This work aims to give an exposition on the philosophical differences between these two operations and highlight when one should opt for one ordering over the other. As part of our analysis, we showcase how many existing risk concepts can be easily integrated into the specification and solution of a robust multi-objective optimisation problem. Besides this, we also demonstrate how one can principally define the notion of a robust Pareto front and a robust performance metric based on our robustify and scalarise methodology. To illustrate the efficacy of these new ideas, we present two insightful numerical case studies which are based on real-world data sets.
- [12] arXiv:2405.10289 [pdf, ps, html, other]
-
Title: Subgradient Convergence Implies Subdifferential Convergence on Weakly Convex Functions: With Uniform Rates GuaranteesSubjects: Optimization and Control (math.OC); Statistics Theory (math.ST); Machine Learning (stat.ML)
In nonsmooth, nonconvex stochastic optimization, understanding the uniform convergence of subdifferential mappings is crucial for analyzing stationary points of sample average approximations of risk as they approach the population risk. Yet, characterizing this convergence remains a fundamental challenge.
This work introduces a novel perspective by connecting the uniform convergence of subdifferential mappings to that of subgradient mappings as empirical risk converges to the population risk. We prove that, for stochastic weakly-convex objectives, and within any open set, a uniform bound on the convergence of subgradients -- chosen arbitrarily from the corresponding subdifferential sets -- translates to a uniform bound on the convergence of the subdifferential sets itself, measured by the Hausdorff metric.
Using this technique, we derive uniform convergence rates for subdifferential sets of stochastic convex-composite objectives. Our results do not rely on key distributional assumptions in the literature, which require the population and finite sample subdifferentials to be continuous in the Hausdorff metric, yet still provide tight convergence rates. These guarantees lead to new insights into the nonsmooth landscapes of such objectives within finite samples.
New submissions for Friday, 17 May 2024 (showing 12 of 12 entries )
- [13] arXiv:2405.09676 (cross-list from math.ST) [pdf, ps, html, other]
-
Title: The radius of statistical efficiencySubjects: Statistics Theory (math.ST); Optimization and Control (math.OC); Machine Learning (stat.ML)
Classical results in asymptotic statistics show that the Fisher information matrix controls the difficulty of estimating a statistical model from observed data. In this work, we introduce a companion measure of robustness of an estimation problem: the radius of statistical efficiency (RSE) is the size of the smallest perturbation to the problem data that renders the Fisher information matrix singular. We compute RSE up to numerical constants for a variety of test bed problems, including principal component analysis, generalized linear models, phase retrieval, bilinear sensing, and matrix completion. In all cases, the RSE quantifies the compatibility between the covariance of the population data and the latent model parameter. Interestingly, we observe a precise reciprocal relationship between RSE and the intrinsic complexity/sensitivity of the problem instance, paralleling the classical Eckart-Young theorem in numerical analysis.
- [14] arXiv:2405.09677 (cross-list from math.AP) [pdf, ps, html, other]
-
Title: Homogenization of non-local energies on disconnected setsSubjects: Analysis of PDEs (math.AP); Optimization and Control (math.OC)
We consider the problem of the homogenization of non-local quadratic energies defined on $\delta$-periodic disconnected sets defined by a double integral, depending on a kernel concentrated at scale $\varepsilon$. For kernels with unbounded support we show that we may have three regimes: (i) $\varepsilon<\!<\delta$, for which the $\Gamma$-limit even in the strong topology of $L^2$ is $0$; (ii) $\frac\varepsilon\delta\to\kappa$, in which the energies are coercive with respect to a convergence of interpolated functions, and the limit is governed by a non-local homogenization formula parameterized by $\kappa$; (iii) $\delta<\!<\varepsilon$, for which the $\Gamma$-limit is computed with respect to a coarse-grained convergence and exhibits a separation-of-scales effect; namely, it is the same as the one obtained by formally first letting $\delta\to 0$ (which turns out to be a pointwise weak limit, thanks to an iterated use of Jensen's inequality), and then, noting that the outcome is a nonlocal energy studied by Bourgain, Brezis and Mironescu, letting $\varepsilon\to0$. A slightly more complex description is necessary for case (ii) if the kernel is compactly supported.
- [15] arXiv:2405.09742 (cross-list from cs.LG) [pdf, ps, html, other]
-
Title: Random Scaling and Momentum for Non-smooth Non-convex OptimizationSubjects: Machine Learning (cs.LG); Optimization and Control (math.OC)
Training neural networks requires optimizing a loss function that may be highly irregular, and in particular neither convex nor smooth. Popular training algorithms are based on stochastic gradient descent with momentum (SGDM), for which classical analysis applies only if the loss is either convex or smooth. We show that a very small modification to SGDM closes this gap: simply scale the update at each time point by an exponentially distributed random scalar. The resulting algorithm achieves optimal convergence guarantees. Intriguingly, this result is not derived by a specific analysis of SGDM: instead, it falls naturally out of a more general framework for converting online convex optimization algorithms to non-convex optimization algorithms.
- [16] arXiv:2405.09752 (cross-list from eess.SP) [pdf, ps, html, other]
-
Title: Time-Varying Graph Signal Recovery Using High-Order Smoothness and Adaptive Low-ranknessSubjects: Signal Processing (eess.SP); Numerical Analysis (math.NA); Optimization and Control (math.OC)
Time-varying graph signal recovery has been widely used in many applications, including climate change, environmental hazard monitoring, and epidemic studies. It is crucial to choose appropriate regularizations to describe the characteristics of the underlying signals, such as the smoothness of the signal over the graph domain and the low-rank structure of the spatial-temporal signal modeled in a matrix form. As one of the most popular options, the graph Laplacian is commonly adopted in designing graph regularizations for reconstructing signals defined on a graph from partially observed data. In this work, we propose a time-varying graph signal recovery method based on the high-order Sobolev smoothness and an error-function weighted nuclear norm regularization to enforce the low-rankness. Two efficient algorithms based on the alternating direction method of multipliers and iterative reweighting are proposed, and convergence of one algorithm is shown in detail. We conduct various numerical experiments on synthetic and real-world data sets to demonstrate the proposed method's effectiveness compared to the state-of-the-art in graph signal recovery.
- [17] arXiv:2405.09764 (cross-list from q-fin.TR) [pdf, ps, html, other]
-
Title: Clearing time randomization and transaction fees for auction market designComments: 30 pages, 11 figuresSubjects: Trading and Market Microstructure (q-fin.TR); Optimization and Control (math.OC)
Flaws of a continuous limit order book mechanism raise the question of whether a continuous trading session and a periodic auction session would bring better efficiency. This paper wants to go further in designing a periodic auction when both a continuous market and a periodic auction market are available to traders. In a periodic auction, we discover that a strategic trader could take advantage of the accumulated information available along the auction duration by arriving at the latest moment before the auction closes, increasing the price impact on the market. Such price impact moves the clearing price away from the efficient price and may disturb the efficiency of a periodic auction market. We thus propose and quantify the effect of two remedies to mitigate these flaws: randomizing the auction's closing time and optimally designing a transaction fees policy. Our results show that these policies encourage a strategic trader to send their orders earlier to enhance the efficiency of the auction market, illustrated by data extracted from Alphabet and Apple stocks.
- [18] arXiv:2405.09809 (cross-list from q-bio.MN) [pdf, ps, other]
-
Title: Biomarker Selection for Adaptive SystemsSubjects: Molecular Networks (q-bio.MN); Optimization and Control (math.OC)
Biomarker selection and real-time monitoring of cell dynamics remains an active challenge in cell biology and biomanufacturing. Here, we develop scalable adaptations of classic approaches to sensor selection for biomarker identification on several transcriptomics and biological datasets that are otherwise cannot be studied from a controls perspective. To address challenges in system identification of biological systems and provide robust biomarkers, we propose Dynamic and Structure Guided Sensors Selection (DSS and SGSS), methods by which temporal models and structural experimental data can be used to supplement traditional approaches to sensor selection. These approaches leverage temporal models and experimental data to enhance traditional sensor selection techniques. Unlike conventional methods that assume well-known, fixed dynamics, DSS and SGSS adaptively select sensors that maximize observability while accounting for the time-varying nature of biological systems. Additionally, they incorporate structural information to identify robust sensors even in cases where system dynamics are poorly understood. We validate these two approaches by performing estimation on several high dimensional systems derived from temporal gene expression data from partial observations.
- [19] arXiv:2405.09852 (cross-list from eess.SY) [pdf, ps, other]
-
Title: Adaptive tracking MPC for nonlinear systems via online linear system identificationSubjects: Systems and Control (eess.SY); Optimization and Control (math.OC)
This paper presents an adaptive tracking model predictive control (MPC) scheme to control unknown nonlinear systems based on an adaptively estimated linear model. The model is determined based on linear system identification using a moving window of past measurements, and it serves as a local approximation of the underlying nonlinear dynamics. We prove that the presented scheme ensures practical exponential stability of the (unknown) optimal reachable equilibrium for a given output setpoint. Finally, we apply the proposed scheme in simulation and compare it to an alternative direct data-driven MPC scheme based on the Fundamental Lemma.
- [20] arXiv:2405.09982 (cross-list from math.PR) [pdf, ps, html, other]
-
Title: Dynamical behavior and optimal control of a stochastic SAIRS epidemic model with two saturated incidencesComments: 18 pages, 5 figuresSubjects: Probability (math.PR); Optimization and Control (math.OC); Physics and Society (physics.soc-ph)
Stochastic models are widely used to investigate the spread of epidemics in a complex environment. This paper extends a deterministic SAIRS epidemic model to a stochastic case with limited patient capacity and exposure. We first study the dynamical properties of the model under certain conditions, including persistence, extinction, and ergodic. Then, we introduce vaccination and isolation into the model as control variables. The optimal control strategies are obtained based on the Pontryagin minimum principle. Finally, numerical simulations are given to illustrate our theoretical results.
- [21] arXiv:2405.10064 (cross-list from eess.SY) [pdf, ps, html, other]
-
Title: Meta results on data-driven control of nonlinear systemsSubjects: Systems and Control (eess.SY); Optimization and Control (math.OC)
This note aims to provide a systematic understanding of direct data-driven control, enriching the existing literature not by adding another isolated result, but rather by offering a comprehensive, versatile, and unifying framework that sets the stage for future explorations and applications in this domain. To this end, we formulate the nonlinear design problem from a high-level perspective as a set of desired controlled systems and propose systematic procedures to synthesize data-driven control algorithms that meet the design requirements specified in the desired set. Various examples are presented to demonstrate the comprehensiveness and adaptability of the proposed approach.
- [22] arXiv:2405.10110 (cross-list from q-bio.QM) [pdf, ps, html, other]
-
Title: Source identification using different moment hierarchiesSubjects: Quantitative Methods (q-bio.QM); Optimization and Control (math.OC)
This work considers the localization of a bioluminescent source in a tissue-mimicking phantom. To model the light propagation in the resulting inverse problem the radiative transfer equation is approximated by using hierarchical simplified moment approximations. The inverse problem is then solved by using a consensus-based optimization algorithm.
- [23] arXiv:2405.10215 (cross-list from cs.LG) [pdf, ps, html, other]
-
Title: SMLP: Symbolic Machine Learning Prover (User Manual)Comments: arXiv admin note: text overlap with arXiv:2402.01415Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO); Symbolic Computation (cs.SC); Optimization and Control (math.OC)
SMLP: Symbolic Machine Learning Prover an open source tool for exploration and optimization of systems represented by machine learning models. SMLP uses symbolic reasoning for ML model exploration and optimization under verification and stability constraints, based on SMT, constraint and NN solvers. In addition its exploration methods are guided by probabilistic and statistical methods. SMLP is a general purpose tool that requires only data suitable for ML modelling in the csv format (usually samples of the system's input/output). SMLP has been applied at Intel for analyzing and optimizing hardware designs at the analog level. Currently SMLP supports NNs, polynomial and tree models, and uses SMT solvers for reasoning and optimization at the backend, integration of specialized NN solvers is in progress.
Cross submissions for Friday, 17 May 2024 (showing 11 of 11 entries )
- [24] arXiv:2209.09936 (replaced) [pdf, ps, html, other]
-
Title: Solving Fredholm Integral Equations of the First Kind via Wasserstein Gradient FlowsComments: Accepted for publication in Stochastic Processes and their Applications. In the journal version we erroneously state that convergence to the unregularized functional requires stronger assumptions on the kernel $k$ than those considered here; in fact, this is not the case and one can apply [27, Theorem 4.1] or [82, Theorem 1] to obtain this result under A1 and A3Subjects: Optimization and Control (math.OC); Functional Analysis (math.FA); Numerical Analysis (math.NA); Computation (stat.CO); Methodology (stat.ME)
Solving Fredholm equations of the first kind is crucial in many areas of the applied sciences. In this work we adopt a probabilistic and variational point of view by considering a minimization problem in the space of probability measures with an entropic regularization. Contrary to classical approaches which discretize the domain of the solutions, we introduce an algorithm to asymptotically sample from the unique solution of the regularized minimization problem. As a result our estimators do not depend on any underlying grid and have better scalability properties than most existing methods. Our algorithm is based on a particle approximation of the solution of a McKean--Vlasov stochastic differential equation associated with the Wasserstein gradient flow of our variational formulation. We prove the convergence towards a minimizer and provide practical guidelines for its numerical implementation. Finally, our method is compared with other approaches on several examples including density deconvolution and epidemiology.
- [25] arXiv:2211.08677 (replaced) [pdf, ps, html, other]
-
Title: Clarke's tangent cones, subgradients, optimality conditions and the Lipschitzness at infinitySubjects: Optimization and Control (math.OC); Classical Analysis and ODEs (math.CA)
We first study Clarke's tangent cones at infinity to unbounded subsets of $\mathbb{R}^n.$ We prove that these cones are closed convex and show a characterization of their interiors. We then study subgradients at infinity for extended real value functions on $\mathbb{R}^n$ and derive necessary optimality conditions at infinity for optimization problems. We also give a number of rules for the computing of subgradients at infinity and provide some characterizations of the Lipschitz continuity at infinity for lower semi-continuous functions.
- [26] arXiv:2305.02501 (replaced) [pdf, ps, html, other]
-
Title: Optimal boundary control for the Cahn-Hilliard-Navier-Stokes EquationsSubjects: Optimization and Control (math.OC)
In this work, we study an optimal boundary control problem for a Cahn - Hilliard -Navier-Stokes (CHNS) system in a two dimensional bounded domain. The CHNS system consists of a Navier-Stokes equation governing the fluid velocity field coupled with a convective Cahn - Hilliard equation for the relative concentration of the fluids. An optimal control problem is formulated as the minimization of a cost functional subject to the controlled CHNS system where the control acts on the boundary of the Navier-Stokes equations. We first prove that there exists an optimal boundary control. Then we establish that the control-to-state operator is Frechet differentiable and derive first-order necessary optimality conditions in terms of a variational inequality involving the adjoint system.
- [27] arXiv:2308.16731 (replaced) [pdf, ps, html, other]
-
Title: An Efficient Framework for Global Non-Convex Polynomial Optimization over the HypercubeSubjects: Optimization and Control (math.OC); Mathematical Software (cs.MS); Numerical Analysis (math.NA)
We present a novel efficient theoretical and numerical framework for solving global non-convex polynomial optimization problems. We analytically demonstrate that such problems can be efficiently reformulated using a non-linear objective over a convex set; further, these reformulated problems possess no spurious local minima (i.e., every local minimum is a global minimum). We introduce an algorithm for solving these resulting problems using the augmented Lagrangian and the method of Burer and Monteiro. We show through numerical experiments that polynomial scaling in dimension and degree is achievable for computing the optimal value and location of previously intractable global polynomial optimization problems in high dimension.
- [28] arXiv:2312.01273 (replaced) [pdf, ps, html, other]
-
Title: An Augmented Lagrangian Primal-Dual Semismooth Newton Method for Multi-Block Composite OptimizationComments: 27 pagesSubjects: Optimization and Control (math.OC)
In this paper, we develop a novel primal-dual semismooth Newton method for solving linearly constrained multi-block convex composite optimization problems. First, a differentiable augmented Lagrangian (AL) function is constructed by utilizing the Moreau envelopes of the nonsmooth functions. It enables us to derive an equivalent saddle point problem and establish the strong AL duality under the Slater's condition. Consequently, a semismooth system of nonlinear equations is formulated to characterize the optimality of the original problem instead of the inclusion-form KKT conditions. We then develop a semismooth Newton method, called ALPDSN, which uses purely second-order steps and a nonmonotone line search based globalization strategy. Through a connection to the inexact first-order steps when the regularization parameter is sufficiently large, the global convergence of ALPDSN is established. Under the regularity conditions, partial smoothness, the local error bound, and the strict complementarity, we show that both the primal and the dual iteration sequences possess a superlinear convergence rate and provide concrete examples where these regularity conditions are met. Numerical results on the image restoration with two regularization terms and the corrected tensor nuclear norm problem are presented to demonstrate the high efficiency and robustness of our ALPDSN.
- [29] arXiv:2312.05156 (replaced) [pdf, ps, html, other]
-
Title: Minimax dual control with finite-dimensional information stateComments: Accepted for the 6th annual Learning for Dynamics & Control Conference, Added examples 1--3 to further motivate the problem class and merged propositions 1 and 2 on page 2. Rewrote the explanation of the worst-case history and its recursive update rules. Also corrected typos and inconsistent notation detected by the L4DC reviewers. No changes to the theoretical resultsSubjects: Optimization and Control (math.OC)
This article considers output-feedback control of systems where the function mapping states to measurements has a set-valued inverse. We show that if the set has a bounded number of elements, then minimax dual control of such systems admits finite-dimensional information states. We specialize our results to a discrete-time integrator with magnitude measurements and derive a surprisingly simple sub-optimal control policy that ensures finite gain of the closed loop. The sub-optimal policy is a proportional controller where the magnitude of the gain is computed offline, but the sign is learned, forgotten, and relearned online.
The discrete-time integrator with magnitude measurements captures real-world applications such as antenna alignment, and despite its simplicity, it defies established control-design methods. For example, whether a stabilizing linear time-invariant controller exists for this system is unknown, and we conjecture that none exists. - [30] arXiv:2312.10670 (replaced) [pdf, ps, other]
-
Title: On Solving General and Special Structure Medium-Scale MINLP ProblemsComments: The paper was shared without the permission of the second authorSubjects: Optimization and Control (math.OC)
Mixed integer nonlinear programming (MINLP) problems are encountered in modeling a physical/industrial process consisting both nonlinearity and discrete selective parameters. There are variety of algorithms for solving MINLP problems most of which solve large-scale MINLP problems very slowly. In this research two parallelization scheme are suggested for solving general and special structure large-scale MINLP problems satisfyingly fast. Special structure refers to problems in which a group of variables are appeared in the objective function and constraints and others are appeared in some constraints separately. Moreover, it is proved that both algorithms have at least R-linear convergence. To show the efficiency of algorithms, numerical test results are presented and compared to available GAMS solvers. According to the numerical results, in almost 80 percent of tests both algorithms compute the solution faster than the best solver in GAMS.
- [31] arXiv:2402.01489 (replaced) [pdf, ps, html, other]
-
Title: Conformal Inverse OptimizationSubjects: Optimization and Control (math.OC)
Inverse optimization has been increasingly used to estimate unknown parameters in an optimization model based on decision data. We show that such a point estimation is insufficient in a prescriptive setting where the estimated parameters are used to prescribe new decisions. The prescribed decisions may be low-quality and misaligned with human intuition and thus are unlikely to be adopted. To tackle this challenge, we propose conformal inverse optimization, which seeks to learn an uncertainty set for the unknown parameters and then solve a robust optimization model to prescribe new decisions. Under mild assumptions, we show that our method enjoys provable guarantees on solution quality, as evaluated using both the ground-truth parameters and the decision maker's perception of the unknown parameters. Our method demonstrates strong empirical performance compared to classic inverse optimization.
- [32] arXiv:2403.07572 (replaced) [pdf, ps, html, other]
-
Title: On Weakly Contracting Dynamics for Convex OptimizationComments: 16 pages, 4 FiguresSubjects: Optimization and Control (math.OC); Dynamical Systems (math.DS)
We analyze the convergence behavior of \emph{globally weakly} and \emph{locally strongly contracting} dynamics. Such dynamics naturally arise in the context of convex optimization problems with a unique minimizer. We show that convergence to the equilibrium is \emph{linear-exponential}, in the sense that the distance between each solution and the equilibrium is upper bounded by a function that first decreases linearly and then exponentially. As we show, the linear-exponential dependency arises naturally in certain dynamics with saturations. Additionally, we provide a sufficient condition for local input-to-state stability. Finally, we illustrate our results on, and propose a conjecture for, continuous-time dynamical systems solving linear programs.
- [33] arXiv:2307.10980 (replaced) [pdf, ps, html, other]
-
Title: Denoising of Sphere- and SO(3)-Valued Data by Relaxed Tikhonov RegularizationSubjects: Numerical Analysis (math.NA); Optimization and Control (math.OC)
Manifold-valued signal- and image processing has received attention due to modern image acquisition techniques. Recently, a convex relaxation of the otherwise nonconvex Tikhonov-regularization for denoising circle-valued data has been proposed by Condat (2022). The circle constraints are here encoded in a series of low-dimensional, positive semi-definite matrices. Using Schur complement arguments, we show that the resulting variational model can be simplified while leading to the same solution. The simplified model can be generalized to higher dimensional spheres and to SO(3)-valued data, where we rely on the quaternion representation of the latter. Standard algorithms from convex analysis can be applied to solve the resulting convex minimization problem. As proof-of-the-concept, we use the alternating direction method of multipliers to demonstrate the denoising behavior of the proposed method. In a series of experiments, we demonstrate the numerical convergence of the signal- or image values to the underlying manifold.
- [34] arXiv:2310.04922 (replaced) [pdf, ps, html, other]
-
Title: Robust Multivariate Detection and Estimation with Fault Frequency Content InformationComments: 32pages, 15 figuresSubjects: Systems and Control (eess.SY); Optimization and Control (math.OC)
This paper studies the problem of fault detection and estimation (FDE) for linear time-invariant (LTI) systems with a particular focus on frequency content information of faults, possibly as multiple disjoint continuum ranges, and under both disturbances and stochastic noise. To ensure the worst-case fault sensitivity in the considered frequency ranges and mitigate the effects of disturbances and noise, an optimization framework incorporating a mixed H_/H2 performance index is developed to compute the optimal detection filter. Moreover, a thresholding rule is proposed to guarantee both the false alarm rate (FAR) and the fault detection rate (FDR). Next, shifting attention to fault estimation in specific frequency ranges, an exact reformulation of the optimal estimation filter design using the restricted Hinf performance index is derived, which is inherently non-convex. However, focusing on finite frequency samples and fixed poles, a lower bound is established via a highly tractable quadratic programming (QP) problem. This lower bound together with an alternating optimization (AO) approach to the original estimation problem leads to a suboptimality gap for the overall estimation filter design. The effectiveness of the proposed approaches is validated through a synthetic non-minimum phase system and an application of the multi-area power system.
- [35] arXiv:2311.04117 (replaced) [pdf, ps, html, other]
-
Title: Hilbert Direct Integrals of Monotone OperatorsSubjects: Functional Analysis (math.FA); Optimization and Control (math.OC)
Finite Cartesian products of operators play a central role in monotone operator theory and its applications. Extending such products to arbitrary families of operators acting on different Hilbert spaces is an open problem, which we address by introducing the Hilbert direct integral of a family of monotone operators. The properties of this construct are studied and conditions under which the direct integral inherits the properties of the factor operators are provided. The question of determining whether the Hilbert direct integral of a family of subdifferentials of convex functions is itself a subdifferential leads us to introducing the Hilbert direct integral of a family of functions. We establish explicit expressions for evaluating the Legendre conjugate, subdifferential, recession function, Moreau envelope, and proximity operator of such integrals. Next, we propose a duality framework for monotone inclusion problems involving integrals of linearly composed monotone operators and show its pertinence towards the development of numerical solution methods. Applications to inclusion and variational problems are discussed.