Enhancing convexification techniques for solving nonconvex quadratic programming problems
At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory. With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has m...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/72726 |
| _version_ | 1811690485094285312 |
|---|---|
| author | Qi, Xiaofei |
| author2 | Tai Kang |
| author_facet | Tai Kang Qi, Xiaofei |
| author_sort | Qi, Xiaofei |
| collection | NTU |
| description | At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory. With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades. As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.
Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree. The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound. Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.
We begin by enhancing existing linearization techniques (notably RLT-based methods) for solving 0-1 QCQPs with the new class of valid cuts, which we refer to as Minimum Triangle (MINT) inequalities. These MINT cuts are derived based on the relationship that yij = min{xi,xj} at any feasible solution (and hence, at optimality), and we prove that these super-linear cuts are tighter than existing triangle inequalities, thereby leading to improved lower bounds at each node of the branch-and-bound tree. Furthermore, we extend the logic used in defining these minimum triangle inequalities to construct a novel variable fixing and affiliated branching strategy (in a branch-and-bound procedure) that identifies a feasible solution relatively early on in the search process while expending a very minimal computational cost.
The derived MINT inequalities in concert with the newly designed variable fixing and branching strategy gives rise to a specialized branch-and-bound algorithm that we refer to as the Minimum Triangle Algorithm (MINT Algorithm), and we demonstrate the efficacy of this algorithm in finding a feasible solution (and subsequently, the optimal solution) for various classes of QP test instances obtained from the literature. Our computational results show that the number of nodes required to obtain the (global) optimum is greatly reduced, and overall, the MINT algorithm performs exceedingly well in comparison with existing methods.
Besides adding MINT inequalities to RLT relaxations, we also introduce a polynomial-time scheme to generate higher rank-order semidefinite cutting planes that serve to tighten convex relaxations of (discrete and continuous) nonconvex quadratically constrained quadratic programs (QCQPs) and significantly improve lower bounds. Suitably defined row-and-column based operations are used to speed up the process of generating these cuts, and computational comparisons across different types of relaxations show the efficacy of these new cutting plane strategies.
Finally, noting that 0-1 QCQPs can be transformed into an equivalent 0-1 mixed-integer program (MIP), in our final contribution, we focus on constructing a second-order cone programming (SOCP) procedure to get tight lower bounds on the underlying 0-1 MIP. This SOCP relaxation method combines the RLT relaxation technique with the p-norm cone programming procedure from Burer and Chen [24], and in the illustrative example, we show that the lower bound reaches the optimal value, which in turn dramatically reduces the computational time taken to determine an optimal solution. In our computations, we test the level-1 SOCP relaxation on several 0-1 QP instances, and the results indicate that even the SOCP level-1 relaxation is a viable alternative to generating tight lower bounds for the difficult class of 0-1 QCQP problems. |
| first_indexed | 2024-10-01T06:04:44Z |
| format | Thesis |
| id | ntu-10356/72726 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:04:44Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | ntu-10356/727262023-03-11T18:00:05Z Enhancing convexification techniques for solving nonconvex quadratic programming problems Qi, Xiaofei Tai Kang School of Mechanical and Aerospace Engineering Duan Fei DRNTU::Engineering::Industrial engineering::Operations research At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory. With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades. As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc. Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree. The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound. Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound. We begin by enhancing existing linearization techniques (notably RLT-based methods) for solving 0-1 QCQPs with the new class of valid cuts, which we refer to as Minimum Triangle (MINT) inequalities. These MINT cuts are derived based on the relationship that yij = min{xi,xj} at any feasible solution (and hence, at optimality), and we prove that these super-linear cuts are tighter than existing triangle inequalities, thereby leading to improved lower bounds at each node of the branch-and-bound tree. Furthermore, we extend the logic used in defining these minimum triangle inequalities to construct a novel variable fixing and affiliated branching strategy (in a branch-and-bound procedure) that identifies a feasible solution relatively early on in the search process while expending a very minimal computational cost. The derived MINT inequalities in concert with the newly designed variable fixing and branching strategy gives rise to a specialized branch-and-bound algorithm that we refer to as the Minimum Triangle Algorithm (MINT Algorithm), and we demonstrate the efficacy of this algorithm in finding a feasible solution (and subsequently, the optimal solution) for various classes of QP test instances obtained from the literature. Our computational results show that the number of nodes required to obtain the (global) optimum is greatly reduced, and overall, the MINT algorithm performs exceedingly well in comparison with existing methods. Besides adding MINT inequalities to RLT relaxations, we also introduce a polynomial-time scheme to generate higher rank-order semidefinite cutting planes that serve to tighten convex relaxations of (discrete and continuous) nonconvex quadratically constrained quadratic programs (QCQPs) and significantly improve lower bounds. Suitably defined row-and-column based operations are used to speed up the process of generating these cuts, and computational comparisons across different types of relaxations show the efficacy of these new cutting plane strategies. Finally, noting that 0-1 QCQPs can be transformed into an equivalent 0-1 mixed-integer program (MIP), in our final contribution, we focus on constructing a second-order cone programming (SOCP) procedure to get tight lower bounds on the underlying 0-1 MIP. This SOCP relaxation method combines the RLT relaxation technique with the p-norm cone programming procedure from Burer and Chen [24], and in the illustrative example, we show that the lower bound reaches the optimal value, which in turn dramatically reduces the computational time taken to determine an optimal solution. In our computations, we test the level-1 SOCP relaxation on several 0-1 QP instances, and the results indicate that even the SOCP level-1 relaxation is a viable alternative to generating tight lower bounds for the difficult class of 0-1 QCQP problems. Doctor of Philosophy (MAE) 2017-10-26T10:39:49Z 2017-10-26T10:39:49Z 2017 Thesis Qi, X. (2017). Enhancing convexification techniques for solving nonconvex quadratic programming problems. Doctoral thesis, Nanyang Technological University, Singapore. http://hdl.handle.net/10356/72726 10.32657/10356/72726 en 151 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Industrial engineering::Operations research Qi, Xiaofei Enhancing convexification techniques for solving nonconvex quadratic programming problems |
| title | Enhancing convexification techniques for solving nonconvex quadratic programming problems |
| title_full | Enhancing convexification techniques for solving nonconvex quadratic programming problems |
| title_fullStr | Enhancing convexification techniques for solving nonconvex quadratic programming problems |
| title_full_unstemmed | Enhancing convexification techniques for solving nonconvex quadratic programming problems |
| title_short | Enhancing convexification techniques for solving nonconvex quadratic programming problems |
| title_sort | enhancing convexification techniques for solving nonconvex quadratic programming problems |
| topic | DRNTU::Engineering::Industrial engineering::Operations research |
| url | http://hdl.handle.net/10356/72726 |
| work_keys_str_mv | AT qixiaofei enhancingconvexificationtechniquesforsolvingnonconvexquadraticprogrammingproblems |