一類擴展的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.