The Legendre-Fenchel conjugate of the product of two positive-definite quadratic forms was posted as an open question in the field of nonlinear analysis and optimization by Hiriart-Urruty [`Question 11′ in {\it SIAM Review} 49, 255-273, (2007)]. Under a convex assumption on the function, it was answered by Zhao [SIAM J. Matrix Analysis $\&$ Applications, 31(4), … Read more
We present a global optimization algorithm, Branch-and-Sandwich, for optimistic bilevel programming problems which satisfy a regularity condition in the inner problem. The functions involved are assumed to be nonconvex and twice continuously differentiable. The proposed approach can be interpreted as the exploration of two solution spaces (corresponding to the inner and the outer problems) using … Read more
An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. These linear programs have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This … Read more
The paper presents a generalization of a known density theorem of Arrow, Barankin, and Blackwell for properly efficient points defined as support points of sets with respect to monotonically increasing sublinear functions. This result is shown to hold for nonconvex sets of a reflexive Banach space partially ordered by a Bishop–Phelps cone. Citation Department of … Read more
This paper follows the recent discussion on the sparse solution recovery with quasi-norms Lq; q\in(0,1) when the sensing matrix possesses a Restricted Isometry Constant \delta_{2k} (RIC). Our key tool is an improvement on a version of “the converse of a generalized Cauchy-Schwarz inequality” extended to the setting of quasi-norm. We show that, if \delta_{2k}\le 1/2, … Read more
This paper presents a branch-and-lift algorithm for solving optimal control problems with smooth nonlinear dynamics and nonconvex objective and constraint functionals to guaranteed global optimality. This algorithm features a direct sequential method and builds upon a spatial branch-and-bound algorithm. A new operation, called lifting, is introduced which refines the control parameterization via a Gram-Schmidt orthogonalization … Read more
In this paper we study valid inequalities for a fundamental set that involves a continuous vector variable x in [0,1]^n, its associated quadratic form x x’ and its binary indicators. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). We treat valid inequalities for this set as lifted from QPB, which … Read more
G. P. McCormick [Math Prog 1976] provides the framework for convex/concave relaxations of factorable functions, via rules for the product of functions and compositions of the form F(f(z)), where F is a univariate function. Herein, the composition theorem is generalized to allow multivariate outer functions F, and theory for the propagation of subgradients is presented. … Read more
Bi-level problems are optimisation problems in which some of the decision variables must optimise a subordinate (lower-level) problem. In general, the lower-level problem can possess multiple optimal solutions. One therefore distinguishes between optimistic formulations, which assume that the most favourable lower-level solution is implemented, and pessimistic formulations, in which the most adverse lower-level solution is … Read more
Mathematical programming problems involving nonconvexities are usually solved to optimality using a (spatial) Branch-and-Bound algorithm. Algorithmic efficiency depends on many factors, among which the widths of the bounding box for the problem variables at each Branch-and-Bound node naturally plays a critical role. The practically fastest box-tightening algorithm is known as FBBT (Feasibility-Based Bounds Tightening): an … Read more