Semidefinite programming relaxations of nonconvex quadratic optimization
Semidefinite programming relaxations of nonconvex quadratic optimization
复制标题
DOI：
10.1007/978-1-4615-4381-7_13
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Y. Nesterov;Henry Wolkowicz;Y. Ye
中科院分区：
文献类型：
--
作者：
Y. Nesterov;Henry Wolkowicz;Y. Ye
二次约束二次规划，记为Q2 p，是一个重要的建模工具，例如：用于硬组合优化问题，第12章;和非线性规划中的SQP方法，第20章。这些问题一般来说很难解决。因此，使用诸如拉格朗日松弛的松弛。拉格朗日松弛的对偶是SDP松弛。因此，SDP使我们能够有效地解决拉格朗日松弛，并找到很好的近似解，这些硬，可能非凸，Q2 p。这一领域最近产生了大量的研究。这导致了许多强大而优雅的定理，描述了从解决这些Q2 p的松弛获得的边界的强度/性能。对于简单的Q2 P情况下的一个二次约束（信赖域子问题）强对偶持有，即使目标函数和约束可能是非凸的，乐。存在零对偶性间隙并且获得对偶性。此外，必要和充分的（加强）二阶最优性条件和有效的算法存在。然而，这些很好的对偶结果已经失败的两个信赖域子问题（CDT问题）。
Quadratically constrained quadratic programs, denoted Q2 p, are an important modelling tool, eg: for hard combinatorial optimization problems, Chapter 12; and SQP methods in nonlinear programming, Chapter 20. These problems are too hard to solve in general. Therefore, relaxations such as the Lagrangian relaxation are used. The dual of the Lagrangian relaxation is the SDP relaxation. Thus SDP has enabled us to efficiently solve the Lagrangian relaxation and find good approximate solutions for these hard, possibly nonconvex, Q2p. This area has generated a lot of research recently. This has resulted in many strong and elegant theorems that describe the strength/performance of the bounds obtained from solving relaxations of these Q2p. For the simple Q2Pcase of one quadratic constraint (the trust region subproblem) strong duality holds, even though both the objective function and constraint may be nonconvex, Le. there is a zero duality gap and the dual is attained. In addition, necessary and sufficient (strengthened) second order optimality conditions and efficient algorithms exist. However, these nice duality results already fail for the two trust region subproblem (CDT problem).