A so-called Standard Bi-Quadratic Optimization Problem (StBQP) consists in minimizing a bi-quadratic form over the Cartesian product of two simplices (so this is different from a Bi-Standard QP where a quadratic function is minimized over the same set). An application example arises in portfolio selection. In this paper we present a bi-quartic formulation of StBQP, … Read more
To obtain a primal-dual pair of conic programming problems having zero duality gap, two methods have been proposed: the facial reduction algorithm due to Borwein and Wolkowicz [1,2] and the conic expansion method due to Luo, Sturm, and Zhang [5]. We establish a clear relationship between them. Our results show that although the two methods … Read more
This paper surveys results on the NP-hard mixed-integer quadratically constrained programming problem. The focus is strong convex relaxations and valid inequalities, which can become the basis of efficient global techniques. In particular, we discuss relaxations and inequalities arising from the algebraic description of the problem as well as from dynamic procedures based on disjunctive programming. … Read more
If a mathematical program (be it linear or nonlinear) has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and reformulating the problem so … Read more
We improve the best known lower bounds on the distance between two points of a Morse cluster in $\mathbb{R}^3$, with $\rho \in [4.967,15]$. Our method is a generalization of the one applied to the Lennard-Jones potential in~\cite{Schac}, and it also leads to improvements of lower bounds for the energy of a Morse cluster. Some of … Read more
In this paper, we develop a convexification tool that enables the construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and … Read more
Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, … Read more
The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. … Read more
Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more
In this paper we propose a Fully Polynomial Time Approximation Scheme (FPTAS) for a class of optimization problems where the feasible region is a polyhedral one and the objective function is the sum or product of linear ratio functions. The class includes the well known ones of Linear (Sum-of-Ratios) Fractional Programming and Multiplicative Programming. ArticleDownload … Read more