The Bundle Method for Getting an Improved SDP Relaxation of the Stabi...

The Lovasz theta function is an upper bound on the stability number of a graph, which can be computed in polynomial time as semidefinite program (SDP). One possibility to further improve this upper bound is to include so called exact subgraph constraints (ESC) for many small subgraphs into the SDP. For a certain subgraph the ESC ensures that the

submatrix of the calculation of the Lovasz theta function corresponding to the subgraph is contained in the convex hull of all stable set matrices of the subgraph. However, solving the resulting SDP is very time-consuming with off-the-shelf solvers, hence it requires alternative solution methods to calculate this improved upper bound. After reformulation, the bundle method with easy sum components (a specialized version of the bundle method) can be applied in a very natural way and yields significantly faster running times. We will discuss some details of the bundle method we use. 4 - A Dynamic Scaling Approach for Bundle Methods in ConvexOptimization Speaker: Christoph Helmberg, TU Chemnitz, DE, talk 145 Co-Authors: Alois Pichler, Acanonicalbundlemethodforconvexoptimizationgenerates the next candidate point by minimizing a quadratic subproblem. Typically, this consists of a piecewise linear cutting model of the convex function formed from collected subgradient information and a quadratic proximal term keeping the candidate close to the current center of stability. For convergence a minimal cutting model consisting of a so called aggregate(cuttingplane)andthelatestsubgradientinequality suffices. This allows to trade quality of the model against solutiontimeofthesubproblem. Weproposeasystematicapproach for including subgradient information in the proximal term in order to support reduced size models. In the smooth case this term should mimic the Hessian and we highlight some theoretical connections in this respect. The practical benefits of the approach will be illustrated by numerical experiments on a class of large scale instances from practice using the callable library ConicBundle.