The role of copositivity in optimality conditions and relaxation bounds

Abstract: 

Second-order local optimality conditions involving copositivity of the Hessian of the Lagrangian on the reduced (polyhedral) tangent cone have the advantage that there is only a small gap between sufficient  (the Hessian is strictly copositive) and necessary (the Hessian is  copositive) conditions. In this respect, this is a proper generalization of convexity of the Lagrangian. We also specify a copositivity-based variant which is sufficient for global optimality. 

For (nonconvex) quadratic optimization problems over polyhedra (QPs), the distinction between sufficiency and necessity vanishes, both for local and global optimality. However, in the strictly copositive case we can provide a distance lower (error) bound of the increment around a local minimizer. This is a refinement of an earlier result which focussed on mere (non-strict) copositivity. In addition, an apparently new variant of constraint qualification (CQ) is presented which is implied by Abadie's CQ and which is suitable for second-order analysis. This new reflected Abadie CQ is neither implied, nor implies, Guignard's CQ. However, it implies the necessary second-order local optimality condition based on copositivity.

For minimization problems under (possibly non-convex) quadratic and linear constraints, we characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation, the Semi-Lagrangian dual we study is equivalent to a natural copositive relaxation. This way, we arrive at a full hierarchy of tractable conic bounds tighter than the usual Lagrangian dual (and thus than the SDP) bounds. In particular, the usual zero-order approximation by doubly nonnegative matrices improves upon the Lagrangian dual bounds. Specialized to this setting, the optimality conditions developed above now return as sufficient conditions for tightness of the relaxation; for instance, copositivity of the slack matrix guarantees global optimality for KKT points of this problem.