An outer approximation method for solving mixed-integer convex quadratic programs with indicators

Mixed-integer convex quadratic programs with indicator variables (MIQP) encompass a wide range of applications, from statistical learning to energy, finance, and logistics. The outer approximation (OA) algorithm has been proven efficient in solving MIQP, and the key to the success of an OA algorithm is the strength of the cutting planes employed. In this paper, … Read more

Mathematical Foundations of Robust and Distributionally Robust Optimization

Robust and distributionally robust optimization are modeling paradigms for decision-making under uncertainty where the uncertain parameters are only known to reside in an uncertainty set or are governed by any probability distribution from within an ambiguity set, respectively, and a decision is sought that minimizes a cost function under the most adverse outcome of the … Read more

Dual optimal design and the Christoffel-Darboux polynomial

The purpose of this short note is to show that the Christoffel-Darboux polynomial, useful in approximation theory and data science, arises naturally when deriving the dual to the problem of semi-algebraic D-optimal experimental design in statistics. It uses only elementary notions of convex analysis. Article Download View Dual optimal design and the Christoffel-Darboux polynomial

Robust Convex Optimization: A New Perspective That Unifies And Extends

Robust convex constraints are difficult to handle, since finding the worst-case scenario is equivalent to maximizing a convex function. In this paper, we propose a new approach to deal with such constraints that unifies approaches known in the literature and extends them in a significant way. The extension is either obtaining better solutions than the … Read more

On the strong concavity of the dual function of an optimization problem

We provide three new proofs of the strong concavity of the dual function of some convex optimization problems. For problems with nonlinear constraints, we show that the the assumption of strong convexity of the objective cannot be weakened to convexity and that the assumption that the gradients of all constraints at the optimal solution are … Read more

Tractable approximation of hard uncertain optimization problems

In many optimization problems uncertain parameters appear in a convex way, which is problematic as common techniques can only handle concave uncertainty. In this paper, we provide a systematic way to construct conservative approximations to such problems. Specifically, we reformulate the original problem as an adjustable robust optimization problem in which the nonlinearity of the … Read more

Pointed Closed Convex Sets are the Intersection of All Rational Supporting Closed Halfspaces

We prove that every pointed closed convex set in $\mathbb{R}^n$ is the intersection of all the rational closed halfspaces that contain it. This generalizes a previous result by the authors for compact convex sets. Citation arXiv:1802.03296. February 2018 Article Download View Pointed Closed Convex Sets are the Intersection of All Rational Supporting Closed Halfspaces

Extreme point inequalities and geometry of the rank sparsity ball

We investigate geometric features of the unit ball corresponding to the sum of the nuclear norm of a matrix and the l_1 norm of its entries — a common penalty function encouraging joint low rank and high sparsity. As a byproduct of this effort, we develop a calculus (or algebra) of faces for general convex … Read more

Unbounded Convex Sets for Non-Convex Mixed-Integer Quadratic Programming

This paper introduces a fundamental family of unbounded convex sets that arises in the context of non-convex mixed-integer quadratic programming. It is shown that any mixed-integer quadratic program with linear constraints can be reduced to the minimisation of a linear function over a set in the family. Some fundamental properties of the convex sets are … Read more

Convexity Conditions of Kantorovich Function and Related Semi-infinite Linear Matrix Inequalities

The Kantorovich function $(x^TAx)( x^T A^{-1} x)$, where $A$ is a positive definite matrix, is not convex in general. From a matrix or convex analysis point of view, it is interesting to address the question: When is this function convex? In this paper, we prove that the 2-dimensional Kantorovich function is convex if and only … Read more