A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown—by several authors using different techniques—that the convex hull of the intersection of an ellipsoid, $\E$, and a split disjunction, $(l – x_j)(x_j – u) \le 0$ with $l < u$, equals the intersection ... Read more
A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set $K$ described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J.~B.~Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations … Read more
The current bottleneck of globally solving mixed-integer (nonconvex) quadratically constrained problem (MIQCP) is still to construct strong but computationally cheap convex relaxations, especially when dense quadratic functions are present. We pro- pose a cutting surface procedure based on multiple diagonal perturbations to derive strong convex quadratic relaxations for nonconvex quadratic problem with separable constraints. Our … Read more
Relaxations of the bilinear term, $x_1x_2=x_3$, play a central role in constructing relaxations of factorable functions. This is because they can be used directly to relax products of functions with known relaxations. In this paper, we provide a compact, closed-form description of the convex hull of this and other more general bivariate monomial terms (which … Read more
We consider fixed-degree polynomial optimization over the simplex. This problem is well known to be NP-hard, since it contains the maximum stable set problem in combinatorial optimization as a special case. In this paper, we consider a known upper bound by taking the minimum value on a regular grid, and a known lower bound based … Read more
The quadratic programming over one inequality quadratic constraint (QP1QC) is a very special case of quadratically constrained quadratic programming (QCQP) and attracted much attention since early 1990’s. It is now understood that, under the primal Slater condition, (QP1QC) has a tight SDP relaxation (PSDP). The optimal solution to (QP1QC), if exists, can be obtained by … Read more
The trust region subproblem with a fixed number m additional linear inequality constraints, denoted by (T_m), have drawn much attention recently. The question as to whether Problem ( T_m) is in Class P or Class NP remains open. So far, the only affirmative general result is that (T_1) has an exact SOCP/SDP reformulation and thus … Read more
We study non-convex quadratic minimization problems under (possibly non-convex) quadratic and linear constraints, and characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation (which has been known for quite a while, although the presented form, incorporating explicitly linear constraints, seems to be … Read more
We study the {\em Celis-Dennis-Tapia (CDT) problem}: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that … Read more
Locating and identifying points as global minimizers is, in general, a hard and time-consuming task. Difficulties increase when the derivatives of the functions defining the problem are not available for use. In this work, we propose a new class of methods suited for global derivative-free constrained optimization. Using direct search of directional type, the algorithm … Read more