一類擴(kuò)展的CDT問(wèn)題存在對(duì)偶間隙的充要條件

摘 ?要： 在這篇文章中，作者研究一類帶有兩個(gè)二次約束的CDT問(wèn)題，其中一個(gè)是單位球約束，一個(gè)是橢球約束。選取合適的通過(guò)最優(yōu)線段的超平面，在不分割可行域的情況下，通過(guò)二階錐重塑技術(shù)和半正定松弛的方法，得到了該CDT問(wèn)題的二階錐重塑問(wèn)題存在對(duì)偶間隙的充要條件，并給出了理論證明，為以后縮小甚至消除CDT問(wèn)題的對(duì)偶間隙做鋪墊。

關(guān)鍵詞： 二次約束二次優(yōu)化;CDT問(wèn)題;二階錐;半正定松弛

中圖分類號(hào)： O224 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.027

本文著錄格式：曲衍明. 一類擴(kuò)展的CDT問(wèn)題存在對(duì)偶間隙的充要條件[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 ?引言

在本文中我們考慮如下的擴(kuò)展的CDT問(wèn)題：

其中 。在1985年Celis， Dennis 和 Tapia [1] 首先提出了經(jīng)典的CDT問(wèn)題（ ），他們使用信賴域方法來(lái)解決非線性約束優(yōu)化問(wèn)題，而且這個(gè)問(wèn)題模型起到了驗(yàn)證信賴域步驟的模型的作用。最近，袁亞湘 ? 院士在2015年給出了關(guān)于CDT問(wèn)題的一個(gè)簡(jiǎn)要 ?介紹[2]。

袁亞湘院士在論文[3]中表明，使CDT問(wèn)題變得有趣又新奇的一個(gè)顯著特性是在全局最優(yōu)解方案中，拉格朗日函數(shù)的Hessian矩陣可能不一定是半

正定的，但是，它最多只能有一個(gè)負(fù)的特征值。他在論文[4]中還提出了一種具有凸目標(biāo)函數(shù)的經(jīng)典CDT問(wèn)題的算法。不久之后，張寅教授在論文[5]中提出了一個(gè)具有半正定最優(yōu)拉格朗日Hessian矩陣的經(jīng)典CDT問(wèn)題的算法。差不多十年后，陳雄達(dá)教授和袁亞湘院士在2001年在論文[6]中提出了一個(gè)充分條件，在該條件下經(jīng)典的CDT問(wèn)題將具有強(qiáng)對(duì)偶性。2006年，Beck和Eldar在論文[7]中使用復(fù)值方法為Chen-Yuan提出類似的充分條件，以解決擴(kuò)展的CDT問(wèn)題。此外，艾文寶和張樹(shù)中教授在2009年在論文[8]中提出了一個(gè)充要條件來(lái)描述擴(kuò)展的CDT問(wèn)題何時(shí)擁有強(qiáng)對(duì)偶性。

另一方面，許多研究人員研究了二階錐（SOC）重塑技術(shù)。據(jù)我們所知，Sturm和張樹(shù)中教授在2003年發(fā)表的文章[9]中首先使用SOC來(lái)重新設(shè)計(jì)一個(gè)優(yōu)化問(wèn)題，該問(wèn)題求解帶一個(gè)單位球約束和線性不等式約束的二次函數(shù)的最小值。他們證明了這種二階錐重塑的SDP松弛是一種精確的放縮，也就是說(shuō)，重塑是一種隱性的凸優(yōu)化問(wèn)題。最近，Burer，Anstreicher和Yang在文章[10][11]中將一些有效的SOC約束添加到具有單位球約束和幾個(gè)線性不等式約束的二次最小化問(wèn)題以加強(qiáng)其SDP松弛。他們證明，只有線性不等式約束是非交叉的，才能保持緊密性。對(duì)于具有兩個(gè)線性不等式約束的“交叉”情形，袁健華教授，王美玲博士，艾文寶教授等人在文章[12]中提出了一個(gè)充要的緊密性條件，而且他們?cè)?017年對(duì)于擴(kuò)展的CDT問(wèn)題給出了縮小對(duì)偶間隙的充要條件，對(duì)于經(jīng)典的CDT問(wèn)題給出了消除對(duì)偶間隙的充分條件。

1 ?理論基礎(chǔ)

3 ?結(jié)論

在本文中我們主要研究對(duì)象是擴(kuò)展的CDT問(wèn)題，主要運(yùn)用了二階錐重塑技術(shù)和半正定規(guī)劃的相關(guān)知識(shí)，通過(guò)選取一個(gè)合適的通過(guò)最優(yōu)線段的超平面，在不分割原問(wèn)題可行域的情況下，得到了一個(gè)引理，一個(gè)定理，給出了這一類CDT問(wèn)題的二階錐重塑問(wèn)題具有對(duì)偶間隙的一個(gè)充要條件。這個(gè)條件是為了以后能夠進(jìn)一步縮小甚至完全消除該類問(wèn)題的對(duì)偶間隙服務(wù)的，希望在后續(xù)的研究中能夠取得新的進(jìn)展。

參考文獻(xiàn)

[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.