TY - GEN
T1 - An alternating projection approach for nonconvex quadratically constrained quadratic programs
AU - Wan, Changhuang
AU - You, Sixiong
AU - Dai, Ran
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2019/1/6
Y1 - 2019/1/6
N2 - A quadratically constrained quadratic programming (QCQP) problem is to minimize a quadratic objective function subject to quadratic constraints where the objective and constraints are not necessary to be convex. Nonconvex QCQPs are generally NP-hard. Many engineering problems, such as optimal control, especially for polynomial optimal control prob-lems, can be equivalently formulated as QCQPs via the discretization technique. Semidefinite relaxation (SDR) is one of the existing methods to solve nonconvex QCQPs. By replacing the rank-one constraint with semidefinite constraint on the unknown matrix, SDR finds a lower bound of the primal optimal value for the QCQP. In this paper, a novel iterative algorithm com-bining the alternating projection and rank-one approximation technique is proposed to solve QCQPs. Furthermore, the global convergence proof of the proposed algorithm under certain conditions is provided based on the strong convexity property of the augmented Lagrangian. Finally, simulation results for the mixed-integer boolean quadratic programming problems and path-planning problems of an unmanned aerial vehicle with multiple avoidance zones are presented to verify the effectiveness and improved computational performance comparing to the results from the state-of-art methods. © 2019, American Institute of Aeronautics and Astronautics Inc, AIAA. All rights reserved.
AB - A quadratically constrained quadratic programming (QCQP) problem is to minimize a quadratic objective function subject to quadratic constraints where the objective and constraints are not necessary to be convex. Nonconvex QCQPs are generally NP-hard. Many engineering problems, such as optimal control, especially for polynomial optimal control prob-lems, can be equivalently formulated as QCQPs via the discretization technique. Semidefinite relaxation (SDR) is one of the existing methods to solve nonconvex QCQPs. By replacing the rank-one constraint with semidefinite constraint on the unknown matrix, SDR finds a lower bound of the primal optimal value for the QCQP. In this paper, a novel iterative algorithm com-bining the alternating projection and rank-one approximation technique is proposed to solve QCQPs. Furthermore, the global convergence proof of the proposed algorithm under certain conditions is provided based on the strong convexity property of the augmented Lagrangian. Finally, simulation results for the mixed-integer boolean quadratic programming problems and path-planning problems of an unmanned aerial vehicle with multiple avoidance zones are presented to verify the effectiveness and improved computational performance comparing to the results from the state-of-art methods. © 2019, American Institute of Aeronautics and Astronautics Inc, AIAA. All rights reserved.
UR - https://www.scopus.com/pages/publications/85083942599
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85083942599&origin=recordpage
U2 - 10.2514/6.2019-0654
DO - 10.2514/6.2019-0654
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781624105784
T3 - AIAA Scitech 2019 Forum
BT - AIAA Scitech 2019 Forum
PB - American Institute of Aeronautics and Astronautics
T2 - AIAA Scitech Forum, 2019
Y2 - 7 January 2019 through 11 January 2019
ER -