Publication Date
2019
Document Type
Dissertation/Thesis
First Advisor
Krislock, Nathan
Degree Name
Ph.D. (Doctor of Philosophy)
Legacy Department
Department of Mathematical Sciences
Abstract
Semidefinite programming (SDP) problems have been investigated and solved in this work. A novel approach has been introduced and validated to solve SDP relaxations of binary quadratic optimization problems. In the BiqCrunch solver, a penalty method is used to compute the solution of a semidefinite relaxation of a binary quadratic problem. This problem generates a bound on the optimal value of the original problem. A branch-and- bound approach then uses this semidefinite bound to solve the binary quadratic problems. In this study, a new approach has been developed to replace the penalty method with the augmented Lagrangian method. Also, according to the value of the parameter α, a hybrid method that switches between the two methods was developed called the combined method.
The proposed three approaches of the equality augmented Lagrangian problem, the in- equality augmented Lagrangian problem, and the penalty problem were studied for the linear programming (LP) problems. As a result, only two approaches were justified and approved as valid methods to be used for solving the SDP relaxations. However, the equality aug- mented Lagrangian problem provides a nonsmooth function that could not be investigated further. Based on the initial results, the other two approaches were studied for the SDP
relaxation of MAX-CUT problems. Several graphs available in the Biq Mac library were used to test the new model.
The use of the line search is essential in various quasi-Newton solution methods such as conjugate gradient, BFGS, LBFGS, and LBFGS-B methods. Further investigations were carried out to identify the best line search algorithm, which provides a better convergence. The two line-search algorithms (Hager-Zhang and BackTracking) were studied with the solu- tion methods under study. The LBFGS method with the BackTracking line search provided the best convergence to the solution.
This study also presents the duality of Moreau-Yosida regularization that leads to the development of the augmented Lagrangian method.
Our new algorithm is shown to be often faster in half the number of function calls and is more robust than the penalty method used in the BiqCrunch solver. In addition, the theoretical convergence properties were improved to show that the new algorithm is the method of choice for solving the SDP relaxations of the binary quadratic problems. This study also confirms that the triangle inequality technique improved the performance of the bound when solving the SDP relaxation. The users of the developed solver for the SDP relaxation will benefit by obtaining faster results.
Recommended Citation
Al-Jilawi, Ahmed Sabah, "Solving the Semidefinite Programming Relaxation of Max-Cut Using an Augmented Lagrangian Method" (2019). Graduate Research Theses & Dissertations. 6797.
https://huskiecommons.lib.niu.edu/allgraduate-thesesdissertations/6797
Extent
171 pages
Language
eng
Publisher
Northern Illinois University
Rights Statement
In Copyright
Rights Statement 2
NIU theses are protected by copyright. They may be viewed from Huskie Commons for any purpose, but reproduction or distribution in any format is prohibited without the written permission of the authors.
Media Type
Text
