Optimization and Control (math.OC)

Abstract: This chapter investigates how symmetries can be used to reduce the computational complexity in polynomial optimization problems. A focus will be specifically given on the Moment-SOS hierarchy in polynomial optimization, where results from representation theory and invariant theory of groups can be used. In addition, symmetry reduction techniques which are more generally applicable are also presented.

Abstract: We are considering differential-algebraic equations with embedded optimization criteria (DAEOs) in which the embedded optimization problem is solved by global optimization. This actually leads to differential inclusions for cases in which there are multiple global optimizer at the same time. Jump events from one global optimum to another result in nonsmooth DAEs and thus reduction of the convergence order of the numerical integrator to first-order. Implementation of event detection and location as introduced in this work preserves the higher-order convergence behavior of the integrator. This allows to compute discrete tangents and adjoint sensitivities for optimal control problems.

Abstract: In this article, we establish a class of new projected type iteration methods based on matrix spitting for solving the linear complementarity problem. Also, we provide a sufficient condition for the convergence analysis when the system matrix is an $H_+$-matrix. We show the efficiency of the proposed method by using two numerical examples for different parameters. Keywords. Iterative method, Linear complementarity problem, $H_{+}$-matrix, $P$-matrix, Matrix splitting, Convergence.

Abstract: Two-stage robust optimization is a fundamental paradigm for modeling and solving optimization problems with uncertain parameters. A now classical method within this paradigm is finite-adaptability, introduced by Bertsimas and Caramanis (IEEE Transactions on Automatic Control, 2010). In this note, we point out that the continuity assumption they stated to ensure the convergence of the method is not correct, and we propose an alternative assumption for which we prove the desired convergence.

Abstract: In this work, optimality conditions and classical results from duality theory are derived for continuous-time linear optimization problems with inequality constraints. The optimality conditions are given in the Karush-Kuhn-Tucker form. Weak and strong duality properties, as well as, the complementary slackness theorem are established. A result concerning the existence of solutions is also stated.

Abstract: The stochastic heavy ball momentum (SHBM) method has gained considerable popularity as a scalable approach for solving large-scale optimization problems. However, one limitation of this method is its reliance on prior knowledge of certain problem parameters, such as singular values of a matrix. In this paper, we propose an adaptive variant of the SHBM method for solving stochastic problems that are reformulated from linear systems using a user-defined distribution. Our adaptive SHBM (ASHBM) method utilizes iterative information to update the parameters, addressing an open problem in the literature regarding the adaptive learning of momentum parameters. We prove that our method converges linearly in expectation, with a better convergence rate compared to the basic method. Notably, we demonstrate that the deterministic version of our ASHBM algorithm can be reformulated as a variant of the conjugate gradient (CG) method, inheriting many of its appealing properties, such as finite-time convergence. Consequently, the ASHBM method can be further generalized to develop a brand-new framework of the stochastic CG (SCG) method for solving linear systems. Our theoretical results are supported by numerical experiments.

Abstract: This paper aims at distributed algorithms for solving a system of linear algebraic equations. Different from most existing formulations for this problem, we assume that the local data at each node is not accurately measured but subject to some disturbances. To be specific, the local measurement consists of two parts: a nominal value and a multiple sinusoidal disturbance. By introducing an identifier-enhanced observer to estimate the disturbance, we present a novel distributed least squares solver for the linear equations using noisy measurements. The proposed solver is proven to be able to recover the least squares solution to the linear equations associated with the nominal values irrespective of any multi-sinusoidal disturbance even with unknown frequencies. We also show the robustness of the distributed solvers under standard conditions against unstructured perturbations. The effectiveness of our design is verified by a numerical example.

Abstract: We study the tropical analogue of the notion of polar of a cone, working over the semiring of tropical numbers with signs and show that the tropical polars of sets of nonnegative tropical vectors are precisely sets of signed vectors that are closed and that are stable by an operation of linear combination. We relate tropical polars with images by the nonarchimedean valuation of classical polars over real closed nonarchimedean fields and show, in particular, that for semi-algebraic sets over such a field, the operation of taking the polar commutes with the operation of signed valuation (keeping track both of the nonarchimedean valuation and sign). We apply these results to characterize images by the signed valuation of classical cones of matrices, including the cones of positive semidefinite matrices, completely positive matrices, completely positive semidefinite matrices, and their polars, including the cone of co-positive matrices. It turns out, in particular, that hierarchies of classical cones collapse under tropicalization. We finally discuss a simple application of these ideas to optimization with signed tropical numbers.