The standard quadratic program (QPS) is $\min_{x\in\Delta} x’Qx$, where $\Delta\subset\Re^n$ is the simplex $\Delta=\{ x\ge 0 : \sum_{i=1}^n x_i=1 \}$. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One … Read more
We consider the problem of global minimization of rational functions on $\LR^n$ (unconstrained case), and on an open, connected, semi-algebraic subset of $\LR^n$, or the (partial) closure of such a set (constrained case). We show that in the univariate case ($n=1$), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced … Read more
We obtain rigorous estimates for linear and semidefinite relaxations of global optimization problems on the simplex and on the sphere Citation Research report, February, 2003 Article Download View Global Optimization of Homogeneous Polynomials on the Simplex and on the Sphere
We consider the global minimization of a multivariate polynomial on a semi-algebraic set \Omega defined with polynomial inequalities. We then compare two hierarchies of relaxations, namely, LP-relaxations based on products of the original constraints, in the spirit of the RLT procedure of Sherali and Adams and recent SDP (semi definite programming) relaxations introduced by the … Read more
A form p on R^n (homogeneous n-variate polynomial) is called positive semidefinite (psd) if it is nonnegative on R^n. In other words, the zero vector is a global minimizer of p in this case. The famous 17th conjecture of Hilbert (later proven by Artin) is that a form p is psd if and only if … Read more
We propose new classes of globally convexized filled functions. Unlike the globally convexized filled functions previously proposed in literature, the ones proposed in this paper are continuously differentiable and, under suitable assumptions, their unconstrained minimization allows to escape from any local minima of the original objective function. Moreover we show that the properties of the … Read more
The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities … Read more
We develop a method for generating valid convex polynomial inequalities for mixed 0-1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities. Article Download View Generating Convex … Read more