圓錐規(guī)劃問題的光滑牛頓方法

遲曉妮, 汪洋, 劉博

(1.桂林電子科技大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院/廣西密碼學(xué)與信息安全重點實驗室,廣西 桂林 541004; 2.桂林電子科技大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院/廣西自動檢測技術(shù)與儀器重點實驗室,廣西 桂林 541004; 3.桂林電子科技大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院/廣西高校數(shù)據(jù)分析與計算重點實驗室,廣西 桂林 541004)

圓錐規(guī)劃問題的光滑牛頓方法

遲曉妮1, 汪洋2, 劉博3

(1.桂林電子科技大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院/廣西密碼學(xué)與信息安全重點實驗室,廣西 桂林 541004; 2.桂林電子科技大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院/廣西自動檢測技術(shù)與儀器重點實驗室,廣西 桂林 541004; 3.桂林電子科技大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院/廣西高校數(shù)據(jù)分析與計算重點實驗室,廣西 桂林 541004)

給出求解圓錐規(guī)劃問題的一種新光滑牛頓方法.基于圓錐互補函數(shù)的一個新光滑函數(shù),將圓錐規(guī)劃問題轉(zhuǎn)化成一個非線性方程組,然后用光滑牛頓方法求解該方程組.該算法可從任意初始點開始,且不要求中間迭代點是內(nèi)點.運用歐幾里得代數(shù)理論,證明算法具有全局收斂性和局部超線性收斂速度.數(shù)值算例表明算法的有效性.

圓錐規(guī)劃;光滑牛頓方法;光滑函數(shù);局部超線性收斂

1 引言

對任意x,y∈Rn,(x,y)表示(xT,yT)T,x=(x0,x1)∈R×Rn?1表示‖.‖表示歐氏范數(shù),I是(n?1)階單位矩陣.n-維圓錐的定義[1]為

由文獻[2]知圓錐與二階錐之間的代數(shù)關(guān)系:對任意x,s∈Rn,

有[3]

其中

且H?1是H的逆矩陣.這里對偶錐,即

考慮圓錐規(guī)劃問題(CCP)[4]

其中A∈Rm×n,c∈Rn和b∈Rm.

CCP(2)的對偶問題[4]是

其中y∈Rm.

CCP是一類非光滑非對稱錐凸優(yōu)化問題,有非常重要而又廣泛的應(yīng)用背景,其研究問題涉及金融、控制、圖像處理和工程[5-7]等領(lǐng)域.如多指機器人最優(yōu)抓取操作和四足機器人動力分配優(yōu)化等問題.所以CCP的算法研究具有重要的理論意義和實際應(yīng)用價值.近年來,圓錐優(yōu)化問題備受關(guān)注,但由于圓錐是非對稱錐,給研究帶來了很多困難.2013年,Zhou和Chen[2]研究了圓錐的性質(zhì)和與圓錐相伴的譜分解.基于圓錐與二階錐的代數(shù)關(guān)系,Bai,Gao和Wang[3]給出求解凸二次圓錐規(guī)劃的內(nèi)點法.目前關(guān)于CCP的算法尚不多見.

本文基于文獻[8]的一個圓錐互補函數(shù),給出一個圓錐互補函數(shù)[8]的光滑函數(shù),并提出求解CCP的一個光滑牛頓方法.該算法對初始點沒有限制,且不要求中間迭代點是內(nèi)點.在每次迭代中,只需求解一個線性方程組和進行一次線搜索.運用歐幾里得約當(dāng)代數(shù)理論,證明算法是全局收斂并且是局部超線性收斂的.數(shù)值算例表明算法的有效性.，

2 預(yù)備知識

本節(jié)介紹與二階錐相伴的歐幾里得約當(dāng)代數(shù)[9].對任意 x=(x0,x1)∈R×Rn?1和s=(s0,s1)∈R×Rn?1,定義約當(dāng)積為:

其單位元e=(1,0,...,0)∈Rn.對任意x=(x0,x1)∈R×Rn?1,定義箭形矩陣為:

易知對任意 x,s∈Rn有 L(x)s=x?s.下給出二階錐中的向量譜分解[9].對任意 x= (x0,x1)∈R×Rn?1,其譜分解為

其中特征值

u(1)和u(2)是分別屬于特征值λ1和λ2的特征向量

如果 x10,則否則ω∈Rn?1是滿足‖ω‖=1的任意向量.

本文假設(shè)CCP(2)和(3)嚴格可行,即F0(P)×F0(D)?.CCP(2)和(3)的嚴格可行解集分別為:

而

故由強對偶理論[4]可知,CCP(2)和(3)都存在最優(yōu)解且其最優(yōu)值相等.此外,若(x?,y?,s?)是CCP(2)和(3)的最優(yōu)解當(dāng)且僅當(dāng)(x?,y?,s?)滿足如下最優(yōu)性條件:

3 光滑牛頓方法

本節(jié)基于圓錐互補問題的一個光滑函數(shù),給出求解CCP(2)和(3)的一個新光滑牛頓方法.由文獻[7]知函數(shù)

將(6)式進行光滑化得到

其中μ∈R.

定理 3.1對任意的一個光滑函數(shù).

證明類似定理2.4[10]的證明,略去.

令z:=(μ,x,y,s)∈R++×Rn×Rm×Rn,定義函數(shù)

本節(jié)基于圓錐互補函數(shù)的光滑函數(shù)(8),將CCP(2)和(3)的最優(yōu)性條件(5)轉(zhuǎn)化成一個非線性方程組Φ(z)=0.當(dāng)μ＞0時,在每步迭代中應(yīng)用光滑牛頓方法求解方程組Φ(z)=0.令 μ↓0時,可得 CCP最優(yōu)性條件 (5)的解.記 z?:=(μ?,x?,y?,s?),當(dāng) μ?=0時,顯然Φ(z?)=0?(x?,y?,s?)是CCP(2)和(3)的解.

定理 3.2設(shè)A行滿秩,且Φ(z)由(9)式定義,則下列結(jié)論成立.

(i)Φ(z)是全局Lipshitz連續(xù)且強半光滑,且在任意z=(μ,x,y,s)∈R++×Rn×Rm×Rn處連續(xù)可微,其雅可比矩陣為

其中

(ii)對任意z=(μ,x,y,s)∈R++×Rn×Rm×Rn,Φ′(z)可逆.

證明由定理2.3[3]的證明,易知(i)成立.

(ii)令Δz:=(Δμ,Δx,Δy,Δs)∈R×Rn×Rm×Rn是Φ′(z)零空間中任一向量,只需證Δz=0.由(10)式知,

由(11)式和(13)式得

在(14)式的左右兩邊同時左乘L(w),有

由D(μ,x,s)和E(μ,x,s)的定義及H是對角陣有

又因為

由引理3.1[11]得到L(w)D(μ,x,s)和L(w)E(μ,x,s)都是正定矩陣必可逆,且

的對稱部分正定.在(15)式兩邊同時左乘△xT[L(w)E(μ,x,s)]?1有

又由(11)式和(12)式得ΔxTΔs=?ΔxTATΔy=?(AΔx)TΔy=0,從而有

又[L(w)D(μ,x,s)][L(w)E(μ,x,s)]的對稱部分正定,從而

定義函數(shù)Ψ:R+×Rn×Rm×Rn→R+為

算法3.1(求解CCP的光滑牛頓方法)

步2 解線性方程組

求得搜索方向Δzk:=(Δμk,Δxk,Δyk,Δsk)∈R×Rn×Rm×Rn.

步3 令lk是滿足下列不等式的最小非負整數(shù)l

確定步長λk=δlk.

步4 令zk+1:=zk+λkΔzk,k:=k+1.轉(zhuǎn)步1.

定義集合

其中ρ(z)由(20)式定義.

定理 3.3設(shè)A行滿秩,且{zk=(μk,xk,yk,sk)}是算法3.1生成的序列,則算法3.1是適定的.

證明當(dāng)μ＞0由定理 3.2知Φ′(z)可逆,故步2是適定的.由引理5[13]的證明能得出步3適定.證畢.

引理 3.1設(shè){zk=(μk,xk,yk,sk)}是算法3.1產(chǎn)生的迭代序列,則對任意k≥0有以下結(jié)論成立.

(i){ρ(zk)}是一個單調(diào)遞減序列;

(ii)對任意k≥0有 μk＞0和zk∈Γ.

證明 (i)由(20)式知{ρ(zk)}是一個單調(diào)遞減序列.

(ii)用數(shù)學(xué)歸納法證明.假設(shè)μk＞0.由定理3.3知對任意

Φ′(z)可逆.由(21)式得

由引理 4.2[13]知對于任意μ＞0有e?μ?1≥?μ,從而

又由μ0＞0和λk∈(0,1)可得對任意k≥0有μk≥0.

由ρ(zk)的定義(20)得ρ(z0)≤γ＜1,即μ0≥μ0ρ(z0),所以z0∈Γ.假設(shè)μk≥ρ(zk)μ0.

則由(30)式和(i)得

故對任意k≥0有zk∈Γ.

4 收斂性分析

下面分析算法3.1的全局收斂性和局部超線性收斂速度.

定理 4.1設(shè)A行滿秩且{zk=(μk,xk,yk,sk)}是算法3.1生成的序列,則{zk}的任一聚點z?:=(μ?,x?,y?,s?)都是Φ(z)=0的解,從而(x?,y?,s?)是CCP(2)和(3)的解.

證明不失一般性,設(shè)由(22)知Ψ(zk)單調(diào)遞減有下界,故

若 Ψ(z?)=0,則結(jié)論成立.反證法,設(shè) Ψ(z?)＞ 0,由 zk∈Γ和 ρ(zk)的定義知 μ?≥γμ0min{1,Ψ(z?)}＞0.由定理 3.2知 Φ′(z?)存在且可逆,故存在 z?的一個閉鄰域 N(z?),使得對任意 z∈N(z?)有 μ∈R++,所以 Φ′(z)可逆.對任意 z∈N(z?),令 Δz= (Δμ,Δx,Δy,Δs)是方程組Φ(z)+Φ′(z)Δz=eμρ(z)的唯一解.故由引理5[13]的證明知存在一個常數(shù)∈(0,1),使得對任意有

定理 4.2(局部超線性收斂)若A行滿秩,z?是算法3.1產(chǎn)生的序列{zk}的任意聚點,且任意V ∈?Φ(z?)非奇異,則{zk}收斂到{z?},即

證明由定理4.1知z?是Ψ(z)=0的一個解，由于V ∈?Φ(z?)非奇異.由命題3.1[14]當(dāng)zk充分接近z?有

由定理3.2知Φ(·)全局Lipshitz連續(xù)且在z?點強半光滑,則對于zk充分接近z?有

由(21),(25),(26)和(27)式,得

由定理4.1[15]的證明知,當(dāng)zk充分接近z?時有

由定理3.2知Φ(·)全局Lipshitz連續(xù),故由(28)式和(29)式知當(dāng)zk充分接近z?時得

因而由算法3.1的步3知,當(dāng)zk充分接近z?時有

由 (28)和(30)式得

又由定理4.1和(20)式得,當(dāng)zk充分接近z?時

由(21),(29)和(31)式知當(dāng)k充分大時有

因為對于任意μ＞0,e?μ?1≤?μe?μ,兩邊同乘以?eμ變?yōu)棣獭躤μ?1,故

所以

故由(26),(29),(31)和(33)式得

證畢.

5 數(shù)值算例

運用Matlab(R2012a)編程,在Intel(R)Xeon(R)CPU E3-1226 v3@3.30GHz 4GB內(nèi)存, Windows 10操作系統(tǒng)的計算機上做數(shù)值算例,測試算法3.1的數(shù)值效果.試驗測試問題是隨機生成規(guī)模m(n=2m)從100到500的CCP.對每種規(guī)模問題產(chǎn)生10個問題進行求解.

運用算法3.1求解隨機生成的CCP.算法3.1當(dāng)ρ=1時為局部二次收斂其余參數(shù)取值為μ0=0.01,δ=0.75,σ=0.45,γ=0.65.當(dāng)‖Φ(z)‖≤10?8算法3.1停止.Iter指平均迭代次數(shù),ACPU指平均CPU時間.

首先隨機生成一個行滿秩的矩陣A∈Rm×n和向量x∈int Cnθ,s∈int(Cnθ)?,y∈Rm.令b=Ax和c=ATy+s.由于CCP(2)和(3)嚴格可行,故CCP(2)和(3)存在最優(yōu)解且其最優(yōu)值相等.然后分別選旋轉(zhuǎn)角表5.1中以x0=e∈Rn,y0=0∈Rm為初始點,給出用算法3.1求解不同旋轉(zhuǎn)角的和不同規(guī)模的CCP的Iter和ACPU.數(shù)值結(jié)果表明算法3.1在求解不同規(guī)模的CCP時,隨著問題規(guī)模變大所需CPU時間會增加,迭代次數(shù)受問題規(guī)模和旋轉(zhuǎn)角的影響較小.

對每一個給定的θ值,均隨機生成10個問題并運用不同的初始點進行求解.當(dāng)時,CCP即為二階錐規(guī)劃問題(SOCCP).表5.2給出運用算法3.1求解不同初始點和不同ρ取值的SOCCP所需的CPU時間和迭代次數(shù).數(shù)值結(jié)果表明,不同初始點和不同ρ值對算法3.1求解CCP所需的CPU時間和迭代次數(shù)影響不大.表5.3給出運用算法3.1與Qi-Sun-Zhou算法[12]求解SOCCP的CPU時間和迭代次數(shù).數(shù)值算例結(jié)果表明算法3.1通常比Qi-Sun-Zhou算法所需的迭代次數(shù)和CPU時間都少.

從表5.1-5.3的數(shù)值結(jié)果看出,運用算法3.1求解CCP所需的CPU時間和迭代次數(shù)較少,且相對穩(wěn)定.從而表明算法3.1的有效性.

表5.1 運用算法3.1求解不同規(guī)模和旋轉(zhuǎn)角的CCP的數(shù)值結(jié)果.

表5.2 運用算法3.1求解不同初始點和不同ρ取值的SOCCP的數(shù)值結(jié)果.

表5.3 算法3.1和Qi-Sun-Zhou算法的性能比較.

[1]Dattorro J.Convex Optimization and Euclidean Distance Geometry[M].California:Meboo Publishing, 2005.

[2]Zhou J C,Chen J S.Properties of circular cone and spectral factorization associated with circular cone[J]. Journal of Nonlinear and Convex Analysis,2013,14(4):1504-1509.

[3]Chi X N,Liu S Y.A one-step smoothing Newton method for second-order cone programming[J].Journal of Computational and Applied Mathematics,2009,223:114-123.

[4]Bai Y Q,Ma P F,Zhang J.A polynomial-time interior-point method for circular cone programming based on kernel functions[J].Journal of Industrial and Management Optimization,2016,12(2):739-756.

[5]Li Z J,Ge S Z,Sam,etal.Contact-force distribution optimization and control for quadruped robots using both gradient and adaptive neural networks[J].IEEE Transactions on Neural Networks,2014,25(8):1460-1473.

[6]Ko C H,Chen J S.Optimal grasping manipulation for multifingered robots using semismooth Newton method[J].Mathematical Problems in Engineering,2013,2013(3):206-226.

[7]Bomze I.Copositive optimization-Recent developments and applications[J].European Journal of Operational Research,2012,216(3):509-520.

[8]Miao X H,Guo S J,Qi N,etal.Constructions of complementarity functions and merit functions for circular cone complementarity problem[J].Computation Optimization Applications,2016,63:495-522.

[9]Alizadeh F,Goldfarb D.Second-order cone programming[J].Mathematical Programming,2003,95:3-51.

[10]Chi X N,Liu S Y.A non-interior continuation method for second-order cone programming[J].Optimization 2009,58(8):965-979.

[11]Fukushima M,Luo Z,Tseng P.Smoothing functions for second-order-cone complementarity problems[J]. SIAM Journal on Optimization,2002,12:436-460.

[12]Qi L Q,Sun D F,Zhou G L.A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities[J].Mathematical Programming,2000,87:1-35.

[13]Jiang H.Smoothed Fischer-Burmeister equation methods for the complementarity problem[J].Department of Mathematics,1997,153:3-4.

[14]Qi L Q,Sun J.A nonsmooth version of Newton’s method[J].Mathematical Programming,1993,58(1):353-367.

[15]Qi L Q.Convergence analysis of some algorithms for solving nonsmooth equations[J].Mathematics of Operations Research,1993,18(1):227-244.

A smoothing Newton algorithm for circular cone programming

Chi Xiaoni1,Wang Yang2,Liu Bo3
(1.School of Mathematics and Computing Science,Guangxi Key Laboratory of Cryptography and Information Security,Guilin University of Electronic Technology,Guilin 541004,China; 2.School of Mathematics and Computing Science,Guangxi Key Laboratory of Automatic Detection Technology and Instrument,Guilin University of Electronic Technology,Guilin 541004,China; 3.School of Mathematics and Computing Science,Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation,Guilin University of Electronic Technology,Guilin 541004,China)

A new smoothing Newton method is presented for solving circular cone programming in this paper. Based on a new smoothing function of circular cone complementary function,the circular cone programming is reformulated as a nonlinear system of equations,and then a smoothing Newton method is given to solve this nonlinear system of equations.The proposed algorithm may start from any initial point,and the intermediate points don’t need to be interior points.We prove that the algorithm has the global convergence and local superlinear convergence by the Euclidean algebra theory.The numerical results illustrate the validity of the algorithm.

circular cone programming,smoothing Newton method,smoothing function, local superlinear convergence

O221

A

1008-5513(2017)02-0111-11

10.3969/j.issn.1008-5513.2017.02.001

2017-02-28.

國家自然科學(xué)基金(11401126,71461005,11661002);國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)計劃項目(201610595037);廣西自然科學(xué)基金(2016GXNSFBA380102,2014GXNSFFA118001);廣西密碼學(xué)與信息安全重點實驗室研究課題(GCIS201618);廣西自動檢測技術(shù)與儀器重點實驗室基金(YQ15112,YQ16112).

遲曉妮(1979-),副教授,研究方向:最優(yōu)化理論與算法.

2010 MSC:90C25