In this master’s thesis, we present the max-cut problem on weighted, undirected graphs. First, we describe the basics of semidefinite programming and duality theory, and then write the problem in the form of an unconstrained binary quadratic program. We introduce its SDP relaxation, derive its dual and argue that strong duality holds for the primal and dual pair. The quality of the solution obtained by solving the dual SDP is improved by introducing triangle inequalities and hypermetric inequalities of higher order. To understand how the relaxed problem is solved numerically, we present some of the basic and most well-known iterative methods for solving optimization problems. In particular, we focus on the class of quasi-Newton methods, including the L-BFGS-B algorithm. We thus assign the augmented Lagrangian function to the dual problem and compute its minimum using the L-BFGS-B algorithm. Numerical results are presented for instances of the graphs G1 to G23 (Helmberg and Rendl) and be150 (Billionet and Elloumi).
|
