半無限極大極小離散化問題的一個(gè)非單調(diào)SQCQP算法

楊永亮, 王福勝, 甄 娜

(太原師范學(xué)院 數(shù)學(xué)系, 山西 晉中 030619)

0 引 言

極大極小(Minimax)優(yōu)化問題[1-3]是一類重要的優(yōu)化問題, 目前已取得豐富的研究成果. 半無限極大極小問題作為其特殊形式廣泛應(yīng)用于工程設(shè)計(jì)、 最優(yōu)控制、 金融工程等領(lǐng)域. 由于其特殊的結(jié)構(gòu), 大多數(shù)傳統(tǒng)方法不再適用, 離散化方法[4-5]是求解該類問題的重要數(shù)值方法之一.

半無限極大極小問題具有如下形式:

(1)

其中: 指標(biāo)集Y={1,2,…,m};f:n×Y→和g:n×[0,1]→關(guān)于x連續(xù)可微. 將[0,1]離散成有限集：Ω={0,1/q,2/q,…,(q-1)/q,1}, 其中q反映了離散水平,q越大離散水平越好. 基于離散化方法求解原問題(1)可歸結(jié)為求解一系列具有如下形式的半無限極大極小離散化問題：

(2)

本文主要考慮具有固定離散水平q的極大極小優(yōu)化問題(2). 序列二次約束二次規(guī)劃(SQCQP)算法[6-7]是繼序列二次規(guī)劃(SQP)算法后又一類求解約束優(yōu)化問題的重要方法, 每一步迭代只需求解一個(gè)二次約束二次規(guī)劃(QCQP)子問題, 子問題的近似程度比二次規(guī)劃(QP)子問題更高, 迭代次數(shù)比SQP算法更少, 不需要任何修正方向即可克服Maratos效應(yīng), 因此得到廣泛關(guān)注. 由于求解一般QCQP子問題無法保證得到的下降方向是可行的, 因此為了解決該問題, 常見的方法是將子問題得到的下降方向與找到的可行方向相結(jié)合以得到可行下降方向, 或?qū)υ陆捣较蜻M(jìn)行修正, 但這兩種方法都會(huì)增加計(jì)算工作量. 針對(duì)該不足, 文獻(xiàn)[5]提出了一類模松弛強(qiáng)次可行算法, 該類算法具有初始點(diǎn)可以任取, 且只需要求解一個(gè)子問題即可得到可行下降方向的優(yōu)點(diǎn). 在模松弛強(qiáng)次可行方向法中常利用單調(diào)線搜索得到步長, 其缺點(diǎn)是當(dāng)?shù)c(diǎn)“陷入很窄的峽谷時(shí)”, 常會(huì)導(dǎo)致小步長或出現(xiàn)鋸齒現(xiàn)象, 而非單調(diào)線搜索技術(shù)可有效克服這些缺點(diǎn). 受Zhang等[8]非單調(diào)技術(shù)的啟發(fā), 本文構(gòu)造一個(gè)新的非單調(diào)線搜索, 并將其應(yīng)用于算法構(gòu)造中. 基于文獻(xiàn)[4-5,7-8], 本文充分利用模松弛強(qiáng)次可行算法的思想和非單調(diào)技術(shù)的優(yōu)勢, 給出一個(gè)半無限極大極小離散化問題的非單調(diào)SQCQP算法.

1 算法描述

定義問題(2)的可行集為F={x∈n:g(x,ω)≤0,ω∈Ω}, 求解問題(2)等價(jià)于求解如下問題:

(3)

(4)

為敘述方便, 記

Ω-(x)={ω∈Ω|g(x,ω)≤0},Ω+(x)={ω∈Ω|g(x,ω)>0},

Ω-(xk)={ω∈Ω|g(xk,ω)≤0},Ω+(xk)={ω∈Ω|g(xk,ω)>0},

構(gòu)造QCQP子問題:

(5)

注1在式(5)中引入一個(gè)重要項(xiàng)-εkz2, 是為了確保當(dāng)dk→0時(shí)有zk→0. 子問題(5)的最后一個(gè)不等式約束并沒有消去因子σk, 主要是為了方便表達(dá)其相應(yīng)乘子的有界性假設(shè). 沒有消去η, 是為了保證問題(3)和(4)較弱的假設(shè).

設(shè)(zk,dk)是子問題(5)的一個(gè)KKT(Karush-Kuhn-Tucker)點(diǎn), 存在乘子μk∈,νk∈,uk∈n滿足如下KKT條件:

假設(shè):

(H1) 對(duì)任意的y∈Y,ω∈Ω, 函數(shù)f(·,y)和g(·,ω)均連續(xù)可微;

(H2) 對(duì)任意的x∈n, Mangasarian-Fromovitz約束規(guī)格成立(簡稱MFCQ成立), 即存在d∈n, 使得xg(x,ω)Td<0, 對(duì)所有的ω∈Ω成立.

引理1[7]若假設(shè)(H1)成立, 則:

1) QCQP子問題(5)總有一個(gè)最優(yōu)解;

2) (zk,dk)是子問題(5)的最優(yōu)解當(dāng)且僅當(dāng)其為子問題(5)的一個(gè)KKT點(diǎn).

引理1表明QCQP子問題有良好的性質(zhì).

引理2[7]若假設(shè)(H1),(H2)成立, (zk,dk)是子問題(5)的最優(yōu)解, 則:

1)r0zk+(dk)THkdk/2≤0,zk≤0;

2)zk=0 ?dk=0;

3)zk=0 ?xk是QCQP問題的一個(gè)Fritz John點(diǎn);

4) 如果xk?F, 則zk<0;

5) 若dk≠0, 則zk<0,dk為問題(2)在xk處的強(qiáng)次可行下降方向.

本文在Zhang等[8]提出的非單調(diào)準(zhǔn)則的基礎(chǔ)上進(jìn)行改進(jìn), 得到修正的非單調(diào)線性搜索準(zhǔn)則如下：

其中:δ1∈(0,1/2),δ2>0,t∈(0,1),αk為{1,t1,t2,…}中滿足式(12)的最大值;ηk-1∈[ηmin,ηmax],ηmin∈[0,1),ηmax∈[ηmin,1]為參數(shù).

算法1

步驟1) 初始化. 取適當(dāng)大的正整數(shù)q(一般q≥100)將區(qū)間[0,1]離散成有限集Ω, 選取參數(shù)r,r0,rω(ω∈Ω),θ∈(0,1),τ,δ1∈(0,1/2),δ2>0,t∈(0,1),η≥0. 選取初始點(diǎn)x0∈n, 對(duì)稱正定矩陣對(duì)稱半正定, 并令k∶=0.

步驟2) 求解QCQP子問題. 對(duì)當(dāng)前的迭代點(diǎn)xk, 求解QCQP子問題得到一個(gè)KKT點(diǎn)對(duì)(xk,dk,μk,vk,uk). 如果zk=0, 則xk是問題(3)的一個(gè)穩(wěn)定點(diǎn), 停止.

步驟3) 線搜索. 由新的非單調(diào)線搜索(12)得到步長αk.

更新QCQP子問題的參數(shù)σk為σk+1.

步驟5) 令k=k+1, 返回步驟2).

2 收斂性分析

下面分析算法的全局收斂性, 若算法經(jīng)過有限次的迭代終止于xk點(diǎn), 則xk是問題(2)的一個(gè)Fritz John點(diǎn). 假設(shè)算法1產(chǎn)生一個(gè)無窮點(diǎn)列{xk}, 下面證明{xk}的每個(gè)聚點(diǎn)x*都是問題(2)的一個(gè)KKT點(diǎn), 為此做如下假設(shè)：

2) 矩陣序列{Hk}一致正定, 即存在兩個(gè)正數(shù)a和b, 使得a‖d‖2≤dTHkd≤b‖d‖2, ?d∈n;

(H4)f(x,y)在水平集l0={x∈n|f(x,y)≤f(x0,y)}內(nèi)有下界, 函數(shù)在包含l0的開凸集S上Lipschitz連續(xù), 即存在常數(shù)l>0, 使得

(H5) 問題(2)在{xk}的每個(gè)極限點(diǎn)x*處都滿足擴(kuò)展的MFCQ條件, 即存在一個(gè)向量d∈n, 使得xg(x*,d)Td≤0, ?ω∈Ω0(x*).

定義子問題(5)的積極約束集[4]ω0如下：

由于子問題(5)積極約束集ω0是指標(biāo)集Ω的子集, 即存在一個(gè)無限指標(biāo)集K, 使得

(15)

證明： 由KKT條件(7)可知,

(16)

式(16)表明0≤μk≤1, 故序列{μk}有界.

引理4[8]算法產(chǎn)生的序列{xk}滿足：

FY(xk)≤Ck,

(17)

Qk+1≤k+2.

(18)

證明: 由非單調(diào)線搜索規(guī)則式(12)知,

由遞推式(13),(14), 有

由ηmax<1可知,

(20)

由子問題(5)的第一個(gè)約束、 假設(shè)(H1)和引理2可知, 存在一個(gè)常數(shù)M(取M>0), 使得

(21)

由式(19)～(21)可知,

定理1若假設(shè)(H1)～(H3),(H5)成立, 則算法1或有限步終止于QCQP問題的一個(gè)Fritz John點(diǎn), 或產(chǎn)生一個(gè)無窮迭代序列{xk}, 使得其每個(gè)聚點(diǎn)x*都是子問題(5)的一個(gè)KKT點(diǎn).

證明： 類似文獻(xiàn)[7]中定理3.3.1的證明. 若算法1有限步終止于第k步, 則由步驟2)和引理2可知,xk是問題(2)的一個(gè)Fritz John點(diǎn). 首先假設(shè)算法1產(chǎn)生一個(gè)無限迭代序列{xk}, 且x*是{xk}的一個(gè)聚點(diǎn). 由引理5和式(15), 不失一般性, 設(shè)存在一個(gè)無限指標(biāo)集K, 使得

(22)

首先證明乘子序列

(23)

(24)

在式(23)中對(duì)k∈K′和k→∞取極限, 并結(jié)合假設(shè)(H3),(H4)及引理3, 有

(25)

(26)

(27)

(28)

(29)

μ*rφ(x*)θ=0.

(30)

根據(jù)式(29)可知(μ*,u*)≠0, 進(jìn)而由假設(shè)(H5)和式(26)～(30)可知μ*>0, 故由式(30)可得φ(x*)=0, 再結(jié)合式(26)～(30)可知x*是問題(2)的一個(gè)KKT點(diǎn).

3 數(shù)值實(shí)驗(yàn)

下面對(duì)算法1的有效性進(jìn)行數(shù)值實(shí)驗(yàn), 在MATLAB 2016a上編程實(shí)現(xiàn), 利用文獻(xiàn)[1]中算例P1,P2,P3:

表1 兩種算法的數(shù)值結(jié)果

由表1可見, 在選擇相同的初始點(diǎn), 離散水平q=100的情形下, 將采用非單調(diào)線搜索技術(shù)的SQCQP算法1與傳統(tǒng)采用Armijo線搜索的SQP算法2進(jìn)行比較, 算法1在迭代次數(shù)和計(jì)算時(shí)間上有明顯優(yōu)勢, 同時(shí)迭代求解問題使用的約束個(gè)數(shù)也略有減少. 因此, 非單調(diào)類SQCQP算法在計(jì)算成本方面明顯低于傳統(tǒng)的SQP算法, 計(jì)算效率也得到提高. 在精度要求較低的情況下, 非單調(diào)類SQCQP算法能在提高計(jì)算效率的同時(shí)縮減計(jì)算成本, 有一定的有效性和可行性, 在較大規(guī)模非線性半無限規(guī)劃問題的求解中有一定的應(yīng)用價(jià)值.