Extensions of the Standard Quadratic Optimization Problem: Strong Duality, Optimality, Hidden Convexity and S-lemma

摘要

Many formulations of quadratic allocation problems, portfolio optimization problems, the maximum weight clique problem, among others, take the form as the well-known standard quadratic optimization problem, which consists in minimizing a homogeneous quadratic function on the usual simplex in the non negative orthant. We propose to analyze the same problem when the simplex is substituted by a convex and compact base of any pointed, closed, convex cone (so, the cone of positive semidefinite matrices or the cone of copositive matrices are particular instances). Three main duals (for which a semi-infinite formulation of the primal problem is required) are associated, and we establish some characterizations of strong duality with respect to each of the three duals in terms of copositivity of the Hessian of the quadratic objective function on suitable cones. Such a problem reveals a hidden convexity and the validity of S-lemma. In case of bidimensional quadratic optimization problems, copositivity of the Hessian of the objective function is characterized, and the case when every local solution is global.