In this thesis we propose a coordinate ascent method for a class of semidefinite programming problems arising in the reformulation of non-convex quadratic optimization problems where the variables are restricted to subsets of the integer numbers.It is known that non-convex quadratic integer problems are NP-hard for two reasons: the non-convexity of the objective function and the restrictions of integrality on the variables. Therefore no polynomial time algorithm is known for solving this class of optimization problems. Standard techniques for addressing these probles are reformulations through linearization or semidefinite programming (SDP), aiming at producing tight convex relaxations of the problem that are then embedded into branch-and-bound schemes. Semidefinite programming has been proved to be a powerful tool for constructing strong convex relaxations for several combinatorial optimization problems, however at increased computational cost. Interior-point based algorithms are the classical solution approaches for semidefinite programming problems, although it turns out that large scale instances are beyond the scope of these algorithms. Buchheim and Wiegele have devised an SDP-based branch-and-bound algorithm (Q-MIST) for a class of mixed-integer quadratic programming problems, that contains the quadratic problems we are considering here. The semidefinite relaxations are solved using the SDP solver CSDP, which based on interior point methods. It has been proved experimentally that this approach outperforms the state-of-the-art non convex mixed-integer programming software COUENNE. Recently, Dong has studied the same class of quadratic problems, and has proposed a semi-infinite convex relaxation. The resulting separation problem is solved by a primal-barrier coordinate minimization algorithm.In this thesis, we have developed an algorithm that on the one hand exploits the structure of the semidefinite relaxations proposed by Buchheim and Wiegele, namely a small total number of active constraints and constraint matrices characterized by a low rank. On the other hand, our algorithm exploits this special structure by solving the dual problem of the semidefinite relaxation, using a barrier method in combination with a coordinate-wise exact line search, motivated by the algorithm presented by Dong. The main ingredient of our algorithm is the computationally cheap update at each iteration and an easy computation of the exact step size. Compared to interior point methods, our approach is much faster in obtaining strong dual bounds. Moreover, no explicit separation and re-optimization is necessary even if the set of primal constraints is large, since in our dual approach this is covered by implicitly considering all primal constraints when selecting the next coordinate. Even more, the structure of the problem allows us to perform a plane search instead of a single line search, this speeds up the convergence of the algorithm. Finally, linear constraints are easily integrated into the algorithmic framework.We have performed experimental comparisons on randomly generated instances, showing that our approach significantly improves the performance of Q-MIST when compared with CSDP and outperforms other specialized global optimization software, such as BARON.
展开▼
