Approximation Properties of Sum-Up Rounding in the Presence of Vanishing Constraints

Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Systems governed by Differential Equations Optimization Tags , ,

Approximation algorithms like sum-up rounding that allow to compute integer-valued approximations of the continuous controls in a weak$^*$ sense have attracted interest recently. They allow to approximate (optimal) feasible solutions of continuous relaxations of mixed-integer control problems (MIOCPs) with integer controls arbitrarily close. To this end, they use compactness properties of the underlying state equation, … Read more

Moments and convex optimization for analysis and control of nonlinear partial differential equations

Categories Distributed Control, Optimization of Systems modeled by PDEs, Semi-definite Programming Tags , , , ,

This work presents a convex-optimization-based framework for analysis and control of nonlinear partial differential equations. The approach uses a particular weak embedding of the nonlinear PDE, resulting in a \emph{linear} equation in the space of Borel measures. This equation is then used as a constraint of an infinite-dimensional linear programming problem (LP). This LP is … Read more

Fast Multilevel Algorithms for Compressive Principle Component Pursuit

Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

Recovering a low-rank matrix from highly corrupted measurements arises in compressed sensing of structured high-dimensional signals (e.g., videos and hyperspectral images among others). Robust principal component analysis (RPCA), solved via principal component pursuit (PCP), recovers a low-rank matrix from sparse corruptions that are of unknown value and support by decomposing the observation matrix into two … Read more

Primal-Dual Interior-Point Methods for Domain-Driven Formulations: Algorithms

Categories Convex Optimization Tags , , ,

We study infeasible-start primal-dual interior-point methods for convex optimization problems given in a typically natural form we denote as Domain-Driven formulation. Our algorithms extend many advantages of primal-dual interior-point techniques available for conic formulations, such as the current best complexity bounds, and more robust certificates of approximate optimality, unboundedness, and infeasibility, to Domain-Driven formulations. The … Read more

Complexity of gradient descent for multiobjective optimization

Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

A number of first-order methods have been proposed for smooth multiobjective optimization for which some form of convergence to first order criticality has been proved. Such convergence is global in the sense of being independent of the starting point. In this paper we analyze the rate of convergence of gradient descent for smooth unconstrained multiobjective … Read more

New inertial factors of a splitting method for monotone inclusions

Categories Convex and Nonsmooth Optimization

In this article, we consider monotone inclusions of two operators in real Hilbert spaces, in which one is further assumed to be Lipschitz continuous, and we suggest adding an inertial term to a splitting method at each iteration. The associated weak convergence is analyzed under standard assumptions. The way of choosing steplength is self-adaptive via … Read more

On Integer and MPCC Representability of Affine Sparsity

Categories (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities Tags , ,

In addition to sparsity, practitioners of statistics and machine learning often wish to promote additional structures in their variable selection process to incorporate prior knowledge. Borrowing the modeling power of linear systems with binary variables, many of such structures can be faithfully modeled as so-called affine sparsity constraints (ASC). In this note we study conditions … Read more

Dynamic Risked Equilibrium

Categories Game Theory, Stochastic Programming Tags , , ,

We revisit the correspondence of competitive partial equilibrium with a social optimum in markets where risk-averse agents solve multistage stochastic optimization problems formulated in scenario trees. The agents trade a commodity that is produced from an uncertain supply of resources which can be stored. The agents can also trade risk using Arrow-Debreu securities. In this … Read more

Block Coordinate Proximal Gradient Method for Nonconvex Optimization Problems: Convergence Analysis

Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

We propose a block coordinate proximal gradient method for a composite minimization problem with two nonconvex function components in the objective while only one of them is assumed to be differentiable. Under some per-block Lipschitz-like conditions based on Bregman distance, but without the global Lipschitz continuity of the gradient of the differentiable function, we prove … Read more

Exact converging bounds for Stochastic Dual Dynamic Programming via Fenchel duality

Categories Dynamic Programming, Stochastic Programming

The Stochastic Dual Dynamic Programming (SDDP) algorithm has become one of the main tools to address convex multistage stochastic optimal control problem. Recently a large amount of work has been devoted to improve the convergence speed of the algorithm through cut-selection and regularization, or to extend the field of applications to non-linear, integer or risk-averse … Read more