Semidefinite relaxation based branch-and-bound method for nonconvex quadratic programming
Citable URI: http://hdl.handle.net/1721.1/39217
| Title: | Semidefinite relaxation based branch-and-bound method for nonconvex quadratic programming |
| Author: | Hu, Sha, S.M. Massachusetts Institute of Technology |
| Advisor: | Pablo A. Parrilo. |
| Department: | Massachusetts Institute of Technology. Computation for Design and Optimization Program. |
| Abstract: |
In this thesis, we use a semidefinite relaxation based branch-and-bound method to solve nonconvex quadratic programming problems. Firstly, we show an interval branch-and-bound method to calculate the bounds for the minimum of bounded polynomials. Then we demonstrate four SDP relaxation methods to solve nonconvex Box constrained Quadratic Programming (BoxQP) problems and the comparison of the four methods. For some lower dimensional problems, SDP relaxation methods can achieve tight bounds for the BoxQP problem; whereas for higher dimensional cases (more than 20 dimensions), the bounds achieved by the four Semidefinite programming (SDP) relaxation methods are always loose. To achieve tight bounds for higher dimensional BoxQP problems, we combine the branch-and-bound method and SDP relaxation method to develop an SDP relaxation based branch-and-bound (SDPBB) method. We introduce a sensitivity analysis method for the branching process of SDPBB. This sensitivity analysis method can improve the convergence speed significantly. (cont.) Compared to the interval branch-and-bound method and the global optimization software BARON, SDPBB can achieve better bounds and is also much more efficient. Additionally, we have developed a multisection algorithm for SDPBB and the multisection algorithm has been parallelized using Message Passing Interface (MPI). By parallelizing the program, we can significantly improve the speed of solving higher dimensional BoxQP problems. |
| Description: | Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006. Includes bibliographical references (leaves 73-75). |
| URI: | http://hdl.handle.net/1721.1/39217 |
| Issue Date: | 2006 |
| Publisher: | Massachusetts Institute of Technology |
| Keywords: | Computation for Design and Optimization Program. |
Files in this item
| Files | Size | Format |
|---|---|---|
| Preview, non-printable (open to all) | 2.621Mb | application/pdf |
| Full printable version (MIT only) | 2.621Mb | application/pdf |
This item appears in the following Collection(s)
All Items in DSpace@MIT are protected by original copyright, with all rights reserved, unless otherwise indicated.
|
|
Contact
MIT Libraries
|