楊永亮, 王福勝, 甄 娜

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

0 引 言

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

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

(1)

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

1 算法描述

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

(3)

(4)

為敘述方便, 記

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

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

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

(5)

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

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

假設(shè):

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

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

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

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

2) (zk,dk)是子問題(5)的最優(yōu)解當且僅當其為子問題(5)的一個KKT點.

引理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問題的一個Fritz John點;

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

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

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

其中:δ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) 初始化. 取適當大的正整數(shù)q(一般q≥100)將區(qū)間[0,1]離散成有限集Ω, 選取參數(shù)r,r0,rω(ω∈Ω),θ∈(0,1),τ,δ1∈(0,1/2),δ2>0,t∈(0,1),η≥0. 選取初始點x0∈n, 對稱正定矩陣對稱半正定, 并令k∶=0.

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

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

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

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

2 收斂性分析

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

2) 矩陣序列{Hk}一致正定, 即存在兩個正數(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}的每個極限點x*處都滿足擴展的MFCQ條件, 即存在一個向量d∈n, 使得xg(x*,d)Td≤0, ?ω∈Ω0(x*).

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

由于子問題(5)積極約束集ω0是指標集Ω的子集, 即存在一個無限指標集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)的第一個約束、 假設(shè)(H1)和引理2可知, 存在一個常數(shù)M(取M>0), 使得

(21)

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

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

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

(22)

首先證明乘子序列

(23)

(24)

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

(25)

(26)

(27)

(28)

(29)

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

(30)

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

3 數(shù)值實驗

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

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

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