一类扩展的CDT问题存在对偶间隙的充要条件

摘  要： 在这篇文章中，作者研究一类带有两个二次约束的CDT问题，其中一个是单位球约束，一个是椭球约束。选取合适的通过最优线段的超平面，在不分割可行域的情况下，通过二阶锥重塑技术和半正定松弛的方法，得到了该CDT问题的二阶锥重塑问题存在对偶间隙的充要条件，并给出了理论证明，为以后缩小甚至消除CDT问题的对偶间隙做铺垫。

关键词： 二次约束二次优化;CDT问题;二阶锥;半正定松弛

中图分类号： O224    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.04.027

本文著录格式：曲衍明. 一类扩展的CDT问题存在对偶间隙的充要条件[J]. 软件，2019，40（4）：124127

【Abstract】： In this paper， the author study a class of CDT problem with two quadratic constraints， one of which is the unit ball constraint and the other is the ellipsoid constraint. Try to find the appropriate hyperplane through the optimal line segment without dividing the feasible region. By using the second-order cone recombination technique and the SDP relaxation method， the necessary and sufficient conditions for the existence of the dual gap in the second-order cone reformulating problem of the CDT problem are obtained， and the theoretical proof is given which is paved to reduce or even eliminate the dual gap of the CDT problem.

【Key words】： Quadratically constrained quadratic programming; CDT problem; Second-order cone; SDP relaxation

0  引言

在本文中我們考虑如下的扩展的CDT问题：

其中 。在1985年Celis， Dennis 和 Tapia [1] 首先提出了经典的CDT问题（ ），他们使用信赖域方法来解决非线性约束优化问题，而且这个问题模型起到了验证信赖域步骤的模型的作用。最近，袁亚湘   院士在2015年给出了关于CDT问题的一个简要  介绍[2]。

袁亚湘院士在论文[3]中表明，使CDT问题变得有趣又新奇的一个显著特性是在全局最优解方案中，拉格朗日函数的Hessian矩阵可能不一定是半

正定的，但是，它最多只能有一个负的特征值。他在论文[4]中还提出了一种具有凸目标函数的经典CDT问题的算法。不久之后，张寅教授在论文[5]中提出了一个具有半正定最优拉格朗日Hessian矩阵的经典CDT问题的算法。差不多十年后，陈雄达教授和袁亚湘院士在2001年在论文[6]中提出了一个充分条件，在该条件下经典的CDT问题将具有强对偶性。2006年，Beck和Eldar在论文[7]中使用复值方法为Chen-Yuan提出类似的充分条件，以解决扩展的CDT问题。此外，艾文宝和张树中教授在2009年在论文[8]中提出了一个充要条件来描述扩展的CDT问题何时拥有强对偶性。

另一方面，许多研究人员研究了二阶锥（SOC）重塑技术。据我们所知，Sturm和张树中教授在2003年发表的文章[9]中首先使用SOC来重新设计一个优化问题，该问题求解带一个单位球约束和线性不等式约束的二次函数的最小值。他们证明了这种二阶锥重塑的SDP松弛是一种精确的放缩，也就是说，重塑是一种隐性的凸优化问题。最近，Burer，Anstreicher和Yang在文章[10][11]中将一些有效的SOC约束添加到具有单位球约束和几个线性不等式约束的二次最小化问题以加强其SDP松弛。他们证明，只有线性不等式约束是非交叉的，才能保持紧密性。对于具有两个线性不等式约束的“交叉”情形，袁健华教授，王美玲博士，艾文宝教授等人在文章[12]中提出了一个充要的紧密性条件，而且他们在2017年对于扩展的CDT问题给出了缩小对偶间隙的充要条件，对于经典的CDT问题给出了消除对偶间隙的充分条件。

1  理论基础

3  结论

在本文中我们主要研究对象是扩展的CDT问题，主要运用了二阶锥重塑技术和半正定规划的相关知识，通过选取一个合适的通过最优线段的超平面，在不分割原问题可行域的情况下，得到了一个引理，一个定理，给出了这一类CDT问题的二阶锥重塑问题具有对偶间隙的一个充要条件。这个条件是为了以后能够进一步缩小甚至完全消除该类问题的对偶间隙服务的，希望在后续的研究中能够取得新的进展。

参考文献

[1] Celis M R， Dennis J E， Tapia R A. A trust region strategy for nonlinear equality constrained optimization.[J]. Numerical Optimization， 1985： 71-82.

[2] Yuan Y X. Recent advances in trust region algorithms[J]. Mathematical Programming， 2015， 151（1）： 249-281.

[3] Yuan， Y. On a subproblem of trust region algorithms for constrained optimization.Math. Programming 47 （1990）， no. 1， （Ser. A）， 53-63.

[4] Ya-Xiang Y. A DUAL ALGORITHM FOR MINIMIZING A QUATDRATIC FUNCTION WITH TWO QUADRATIC CONSTRAINTS[J]. Journal of Computational Mathematics， 1991， 9（4）： 348-359.

[5] Zhang Y. Computing a Celis-Dennis-Tapia trust-region step for equality constrained optimization[J]. Mathematical Programming， 1992， 55（1-3）： 109-124.

[6] Xiongda Chen Y Y. On Maxima Of Dual Function Of The Cdt Subproblem[J]. Journal of Computational Mathematics， 2001， 19（2）： 113-124.

[7] Beck A， Eldar Y C. Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints[J]. SIAM Journal on Optimization， 2006， 17（3）： 844-860.

[8] Ai W， Zhang S. Strong Duality for the CDT Subproblem： A Necessary and Sufficient Condition[J]. SIAM Journal on Optimization， 2009， 19（4）： 1735-1756.

[9] Zhang S S. On Cones of Nonnegative Quadratic Functions[J]. Mathematics of Operations Research， 2003， 28（2）： 246-267.

[10] Burer S， Anstreicher K M. Second-Order-Cone Constraints for Extended Trust-Region Subproblems[J]. SIAM Journal on Optimization， 2011， 23（1）： 432-451.

[11] Burer S， Yang B. The trust region subproblem with non- intersecting linear constraints[J]. Mathematical Programming， 2015， 149（1-2）： 253-264.

[12] Yuan J H， Wang M L， Ai W B， et al. A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts[J]. Science China Mathematics， 2016， 59（6）：1127-1140.

[13] Yuan J， Wang M， Ai W， et al. New Results on Narrowing the Duality Gap of the Extended Celis--Dennis--Tapia Problem [J]. SIAM Journal on Optimization， 2017， 27（2）： 890-909.