ALOP-Colloquium with Immanuel Bomze

On June 13, 2016,   Immanuel Bomze from the University of Vienna will join the ALOP-Colloquium and present his recent work. At 15:45 there will be a coffee hour in E10. At 16:15 the presentation will take place in HS10.

Second-order local optimality conditions involving copositivity of the Hessian of the Lagrangian on the reduced (polyhedral) tangent conehave 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 [2].

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 [2].

[1] I.M. Bomze. Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs. SIAM J. Optimization 25 (3), 1249–1275 (2015).

[2] I.M. Bomze. Copositivity for second-order optimality conditions in general smooth optimization problems. Optimization 64(1), 779-795 (2016).