非光滑約束優(yōu)化的兩階段近似束方法

石露 劉逸

摘?要：基于兩階段束方法思想，利用近似函數(shù)值以及近似次梯度構(gòu)造割平面近似模型和線搜索條件，提出了一個(gè)非光滑約束優(yōu)化的兩階段近似束方法。算法最終具備全局收斂性。

關(guān)鍵詞：非光滑優(yōu)化;兩階段束方法;近似束方法;全局收斂性

中圖分類號：O221.2??文獻(xiàn)標(biāo)識碼：A

An?Approximate?Twophase?Bundle?Method

for?Nonsmooth?Constrained?Optimization

Shi?Lu?Liu?Yi

Xingjian?College?of?Science?and?Liberal?Arts，Guangxi?University?GuangxiNanning?530005

Abstract：Based?on?the?idea?of?twophase?bundle?method，an?approximate?twophase?bundle?method?is?proposed?by?using?the?approximate?function?values?and?approximate?subgradient?to?construct?the?cuttingplane?model?and?line?search?condition.Finally，the?algorithm?has?global?convergence.

Keywords：nonsmooth?optimization;twophase?bundle?method;approximate?bundle?method;global?convergence

1?概述

本文研究求解如下非光滑約束優(yōu)化問題：

minx∈瘙 綆

nf（x）

s.t.c（x）SymbolcB@

0（1）

其中f：瘙 綆

n→瘙 綆

為凸函數(shù)，且可能不可微。為陳述簡便，本文僅考慮c（x）是一個(gè)數(shù)量值函數(shù)，若實(shí)際問題有m個(gè)約束條件時(shí)，如cj（x）SymbolcB@

0，j=1，…，m，可取c（x）=max{cj（x），j=1，…，m}。

非光滑優(yōu)化存在于很多實(shí)際問題中，非光滑優(yōu)化也稱為不可微優(yōu)化，其研究起源于20世紀(jì)60年代。經(jīng)過半個(gè)多世紀(jì)的發(fā)展，非光滑優(yōu)化在理論與算法研究方面取得了比較豐富的成果，并廣泛應(yīng)用于求解實(shí)際問題，如機(jī)器學(xué)習(xí)、最優(yōu)控制、圖像信息處理、人工智能、經(jīng)濟(jì)系統(tǒng)等領(lǐng)域。束方法[1]是目前求解非光滑優(yōu)化問題最有效的方法之一。束方法可看作穩(wěn)定化的割平面法，由于每次算法迭代使用一組次梯度產(chǎn)生求解搜索方向的子問題，因此得名“束”。但目前大多束方法使用精確的函數(shù)值和精確次梯度構(gòu)造算法，而在某些問題中很難計(jì)算精確的函數(shù)值，例如拉格朗日松弛問題。

minx∈Xg（x），s.t.h（x）=0

其拉格朗日函數(shù)為L（x，μ）=g（x）+〈μ，h（x）〉，當(dāng)f（x）=maxx∈XL（x，μ）時(shí)，此時(shí)計(jì)算f的精確函數(shù)值和精確次梯度都有很大的困難。因此很多學(xué)者們利用近似函數(shù)值和近似次梯度等非精確數(shù)據(jù)構(gòu)造算法。文獻(xiàn)[2]對給定的誤差限，利用近似函數(shù)值和近似次梯度，結(jié)合鄰近束方法思想，給出一個(gè)非光滑無約束優(yōu)化的近似束方法。文獻(xiàn)[3]對文獻(xiàn)[2]的割平面近似模型進(jìn)行改善使其更加接近目標(biāo)函數(shù)。文獻(xiàn)[4]在文獻(xiàn)[2，3]的基礎(chǔ)上給出了對目標(biāo)函數(shù)近似程度更好的多面體函數(shù)，并將文獻(xiàn)[5]的束集修正策略推廣至非精確數(shù)據(jù)。文獻(xiàn)[6]基于文獻(xiàn)[2]的思想將非光滑優(yōu)化強(qiáng)次可行方向法推廣到非精確的情形，但仍需計(jì)算精確的約束函數(shù)值和梯度。

兩階段束方法[7]是一類不可行束方法，算法能接受任意初始點(diǎn)，在階段一通過使約束函數(shù)值減小搜索一個(gè)可行迭代點(diǎn)，若產(chǎn)生可行迭代點(diǎn)，則進(jìn)入階段二即可行下降階段，在保證迭代點(diǎn)可行的條件下，使目標(biāo)函數(shù)值減小，從而得到問題的最優(yōu)解。

本文在文獻(xiàn)[1，2，4，7]的基礎(chǔ)上，提出一個(gè)近似的兩階段束方法，該算法利用近似的函數(shù)值和近似次梯度構(gòu)造原問題的割平面近似模型以及線搜索條件，算法最終收斂到全局最優(yōu)解。

2?算法設(shè)計(jì)

凸函數(shù)f在x處的—次微分[7]為：

f（x）={g∈瘙 綆

n|f（y）f（x）+〈g，y-x〉-，y∈瘙 綆

n}

其中≥0。集合f（x）的元素g為函數(shù)f在x處的—次梯度。記問題（1）的可行集為：

X={x∈瘙 綆

n|c（x）SymbolcB@

0}

對任意給定的x∈瘙 綆

n，定義改善函數(shù)[7]：

Hx（y）=max{f（y）-f（x），c（y）}，y∈瘙 綆

n

當(dāng)x∈X時(shí)，Hx（x）=0，若Hx（y）<Hx（x），則有Hx（y）<Hx（x）且c（y）<0。

引理2.1[7]?設(shè)問題（1）滿足Slater約束規(guī)格，即可行集X非空，則以下三個(gè)命題等價(jià)。

（a）0∈Hx-（x-）;

（b）min{Hx-（y）：y∈瘙 綆

n}=Hx-（x-）=0;

（c）x-是問題（1）的最優(yōu)解。

設(shè)yi（i=1，…，k）為算法產(chǎn)生的試探點(diǎn)列，εi0為相應(yīng)的誤差限，假設(shè)fεi（yi），cεi（yi）和gif，gic分別為目標(biāo)函數(shù)和約束函數(shù)在點(diǎn)yi處的近似函數(shù)值和近似次梯度，且滿足下列不等式：

f（yi）-εiSymbolcB@

fεi（yi）SymbolcB@

f（yi），c（yi）-εiSymbolcB@

cεi（yi）SymbolcB@

c（yi）（2）

f（x）fεi（yi）+〈gif，x-yi〉，c（x）cεi（yi）+〈gic，x-yi〉，x∈瘙 綆

n（3）

易證gif∈εif（yi），gic∈εic（yi）。

在yi處，定義f，c的近似線性化為：

fi（x）=fεi（yi）+〈gif，x-yi〉，ci（x）=cεi（yi）+〈gic，x-yi〉

根據(jù)（3）式，可得：

fi（x）SymbolcB@

f（x），ci（x）SymbolcB@

c（x），x∈瘙 綆

n（4）

根據(jù)文[4]，可定義f，c的如下割平面近似模型：

f^k（x）=maxi∈Ik{fi（x）}=fεk（xk）+maxi∈Ik{〈gif，x-xk〉-αik}+εk，

c^k（x）=maxi∈Ik{ci（x）}=cεk（xk）+maxi∈Ik{〈gic，x-xk〉-βik}+εk。

其中Ik={1，2，…，k}，且：

αik=fεk（xk）-[fεi（yi）+〈gi，xk-yi〉]+εk，

βik=cεk（xk）-[cεi（yi）+〈gic，xk-yi〉]+εk（5）

稱為近似線性化誤差，由（2）式和（3）式易知αik0，βik0。對任意的x∈瘙 綆

n，有f（x）f^k（x），c（x）c^k（x），稱f^k（x），c^k（x）分別為f（x）和c（x）的下近似函數(shù)。在算法中采用某種更新準(zhǔn)則，使誤差限序列εii∈Ik單調(diào)不增，因此當(dāng)前誤差限εk是最小的，由文獻(xiàn)[4]易知，本文構(gòu)造的割平面近似模型比文獻(xiàn)[2，3]的更接近原函數(shù)。

記穩(wěn)定中心為xk，定義H的割平面近似模型為：

Hˇxk（y）=max{f^k（x）-fεk（xk）-εk，c^k（x）-εk}

易得Hxk（y）H^xk（y）。

定義束集：

Bk={（yi，fεi（yi），cεi（yi），gif，gic，αik，βik，i∈Ik}

利用Bk構(gòu)造以下子問題產(chǎn)生新的試探點(diǎn)yk+1：

minx∈瘙 綆

n?Hˇxk（y）+12γ‖y-xk‖2（6）

其中鄰近參數(shù)γ>0。令y=xk+d，u=Hˇxk（y），根據(jù)兩階段束方法的思想，令c-（xk）+=max{0，cε（xk）}，則問題（6）可轉(zhuǎn)化為以下子問題：

minu∈瘙 綆

，d∈瘙 綆

n?u+12γ‖d‖2

s.t.?（gif）Td-αik-c-（xk）+SymbolcB@

u，i∈Jk，

（gic）Td-βik+cε（xk）-c-（xk）+SymbolcB@

u，i∈Jk（7）

設(shè)（dk，uk）為問題（7）的最優(yōu)解，其KKT乘子為λki，μki，i∈Jk，根據(jù)KKT條件有如下引理成立。

引理2.2?dk=-1γgk，uk=（-1γ‖gk‖2+α^k）（8）

其中：

gk=∑i∈Jkλkigif+∑i∈Jkμkigic，（9）

α^k=∑i∈Jkλkiαik+∑i∈Jkμkiβik+∑i∈Jkμki（-cε（xk））+c-（xk）+（10）

因?yàn)椋?，0）為問題（7）的一個(gè)可行解，所以有ukSymbolcB@

0。若uk=0，由引理2.1和2.2可推出xk是問題（1）的最優(yōu)解。若uk<0，令yk+1=xk+dk，給定參數(shù)m∈（0，1），下面給出新的線搜索條件。

若：

cε（xk）>0且cεk+1（yk+1）+εk+1SymbolcB@

cε（xk）+muk（11）

或：

cεk+1（yk+1）+εk+1SymbolcB@

0且fεk+1（yk+1）+εk+1SymbolcB@

fε（xk）+muk（12）

成立，則更新穩(wěn)定中心，令xk+1=yk+1，稱為有效步;否則，穩(wěn)定中心保持不變，令xk+1=xk，稱為無效步。根據(jù)（2）式，由（1112）式也可推出文獻(xiàn)[7]兩階段束方法的線搜索條件，因此本文算法的收斂性分析類似文獻(xiàn)[7]。

下面給出算法的具體步驟。

算法2.1

步驟1（初始化）選取初始迭代點(diǎn)x1∈瘙 綆

n，初始誤差限ε10，令I(lǐng)1={1}，y1=x1，fε1（y1）=fε1（x1），cε1（y1）=cε1（x1），B1={（y1，fε1（y1），cε1（y1），g1f，g1c，ε1，ε1）}。

設(shè)置參數(shù)0<m<m-<1，δ>0，令k：=1。

步驟2（求解QP子問題）求解子問題（7）得到最優(yōu)解（dk，vk）以及乘子λki，i∈Ik。

步驟3（更新誤差限）若εk>-（m--m）uk3，置εk=εk2，并返回步驟2;否則，令εk+1=εk，轉(zhuǎn)步驟3。

步驟4（終止準(zhǔn)則）如果|uk|SymbolcB@

δ，算法終止;否則，轉(zhuǎn)步驟5。

步驟5（線搜索）若（11）式或（12）式成立，令yk+1=xk+d，xk+1=yk+1（有效步）;否則令xk+1=xk（無效步）。計(jì)算fεk+1（yk+1），cεk+1（yk+1），gk+1f，gk+1c。

步驟6（擴(kuò)充束集）若為有效步，令αk+1k+1=βk+1k=εk+1，利用（5）式更新αik+1，βik+1，i∈Ik;若為無效步，令αik+1=αik，βik+1=βik，i∈Ik，利用（5）式計(jì)算αk+1k+1，βk+1k+1。令I(lǐng)k+1=Ik∪{k+1}，且：

Bk+1={（yi，fεi（yi），cεi（yi），gif，gic，αik+1，βik+1），i∈Ik+1}

令k：=k+1，轉(zhuǎn)步驟1。

類似文獻(xiàn)[4]和文獻(xiàn)[7]可得如下引理成立。

引理2.3?（i）gk∈αkHxk（xk）;

（ii）若|uk|SymbolcB@

δ，則有Hxk（y）Hxk（xk）-δ‖y-xk‖-δ，y∈瘙 綆

n。

證明?根據(jù)（2）～（3）式以及（8）～（10）式，結(jié)合H的定義，可證明引理成立，證明類似文獻(xiàn)[8]的引理2.3。

3?算法的全局收斂性

令終止參數(shù)δ=0，下面分析算法2.1的全局收斂性。

引理3.1[7]?令ωk=12γ‖γdk‖2+α^k，則ωk是以下問題的最優(yōu)值：

minλki，μki，i∈Ik?12γ‖∑i∈Ikλkigif+∑i∈Ikμkigic‖2+

∑i∈Ikλkiαik+∑i∈Ikμkiβik-∑i∈Ikμkicε（xk）+c-（xk）+

s.t.∑i∈Ikλki+∑i∈Ikμki=1，λki0，μki0，i∈Ik

引理3.2[7]?設(shè)n維向量d，g及常數(shù)η∈（0，1），C，ω，ρ，α^和α滿足：

ω=12γ‖γd‖2+α^，u=-（γ‖d‖2+α^）

-α+〈g，d〉ηu，Cmax{‖γd‖，‖g‖γ，α^，1}

令ω-=min{Q（ρ），ρ∈[0，1]}，其中Q（ρ）=12γ‖（1-ρ）（-γd）+ρg‖2+（1-ρ）α^+ρα，則ω-SymbolcB@

ω-（1-η）2ω2/（8C2）。

引理3.3?若算法的有效步有限，則存在一個(gè)無限指標(biāo)集K，使得uk→0，k∈K。

證明?根據(jù)（2）～（3）式，引理3.1—3.2，類似文獻(xiàn)[6]定理2.1的情形2，可得引理成立。

引理3.4?若算法的有效步無限，且f在可行集X上有下界，設(shè)有效步指標(biāo)集為K-，則：

∑k∈K-（-uk）<+SymboleB@

證明?根據(jù)（2）～（3）式，類似于文獻(xiàn)[8]引理2.4的證明，可得引理成立。

基于上述引理，可以得到如下全局收斂性定理。

定理3.1?設(shè)算法2.1產(chǎn)生無限迭代點(diǎn)列xk，則：

（i）若算法的有效步有限，則存在一個(gè)無限指標(biāo)集K，使得算法產(chǎn)生的試探點(diǎn)序列ykk∈K收斂到最后一個(gè)穩(wěn)定中心，且最后一個(gè)穩(wěn)定中心為問題（1）的一個(gè)最優(yōu)解;

（ii）若算法在第k次迭代時(shí)在步驟2和步驟3之間無限次循環(huán)，則xk是問題（1）的一個(gè)最優(yōu)解;

（iii）若算法的有效步無限，且存在k～，使得xk～∈X，則當(dāng)f在X上有下界時(shí)，xk收斂到問題（1）的一個(gè)最優(yōu)解。

證明?（1）若算法的有效步有限，根據(jù)引理3.3可知，則存在一個(gè)無限指標(biāo)集K，使得uk→0，k∈K。根據(jù)（8）—（10）式可知limk∈Kdk=limk∈Kgk=limk∈Kα^k=0。設(shè)存在正整數(shù)l>0使得xl為最后一個(gè)穩(wěn)定中心，則對任意的k>l有xk=xl，根據(jù)引理2.3可知0∈Hxl（xl），再結(jié)合引理2.1可知，最后一個(gè)穩(wěn)定中心xl為問題（1）的一個(gè)最優(yōu)解。

（2）若算法在第k次迭代時(shí)在步驟2和步驟3之間無限次循環(huán)，由εk>-（m--m）uk3且εk0可εk→0，又因?yàn)棣舓>-（m--m）uk3，m--m>0，則有uk>-3εkm--m，結(jié)合uk的非負(fù)性可推出uk→0。因此根據(jù)引理2.3可得0∈Hxk（xk），再由引理2.1可得知xk為問題（1）的最優(yōu)解。

（3）若算法的有效步無限，設(shè)有效步指標(biāo)集為K-，由引理3.4知∑k∈K-（-uk）<+SymboleB@

，從而有uk→0，k∈K-，根據(jù)（8）—（10）式可推出limk∈Kdk=limk∈Kgk=limk∈Kα^k=0，結(jié)合引理2.3可證明序列xk有界，令x-為xkK-的一個(gè)聚點(diǎn)，則x-是問題（1）的最優(yōu)解。證明類似文獻(xiàn)[9]定理4.1（ii）的證明。

結(jié)語

針對某些函數(shù)的精確函數(shù)值難以計(jì)算的問題，本文利用近似的函數(shù)值和近似次梯度構(gòu)造原函數(shù)的割平面近似模型以及線搜索條件，結(jié)合兩階段束方法的思想，提出一個(gè)非光滑約束優(yōu)化的兩階段近似束方法，該方法能接受任意初始點(diǎn)，若初始點(diǎn)在可行域外，算法會在階段一尋找可行迭代點(diǎn)，一旦產(chǎn)生可行迭代點(diǎn)，接著進(jìn)入階段二即可行下降階段，算法最終具備全局收斂性。

參考文獻(xiàn)：

[1]Schramm?H，Zowe?J.A?version?of?the?bundle?idea?for?minimizing?a?nonsmooth?function：Conceptual?idea，convergence?analysis，numerical?results[J].SIAM?Journal?on?Optimization，1992，2：121152.

[2]Kiwiel?K?C.An?algorithm?for?nonsmooth?convex?minimization?with?errors[J].Mathematics?of?Computation，1985，171（45）：173180.

[3]Shen?J，Xia?Z?Q，Pang?L?P.A?proximal?bundle?method?with?inexact?data?for?convex?nondifferentiable?minimization[J].Nonlinear?Analysis，2007，66（9）：20162027.

[4]石露，高揚(yáng)，劉逸.非光滑無約束優(yōu)化帶束集修正的近似束方法[J].南寧師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2020，37（4）：3340.

[5]Demyanov?A?V，F(xiàn)uduli?A，Miglionico?G.A?bundle?modification?strategy?for?convex?minimization[J].European?Journal?of?Operational?Research，2007，180（1）：3847.

[6]唐春明，律金曼.基于非精確數(shù)據(jù)的非光滑優(yōu)化強(qiáng)次可行方向法[J].廣西科學(xué)，2016，23（5）：404408.

[7]Kiwiel?K?C.Methods?of?descent?for?nondifferentiable?optimization[M].Berlin：SpringerVerlag，1985.

[8]石露，唐春明，簡金寶.非光滑約束優(yōu)化帶束集修正的兩階段束方法[J]，數(shù)學(xué)進(jìn)展，2021，50（5）：742758.

[9]Jian，J.B.，Tang，C.M.and?Shi，L.，A?feasible?point?method?with?bundle?modification?for?nonsmooth?convex?constrained?optimization，Acta?Math.Appl.SINE.，2018，34（2）：254273.

基金項(xiàng)目：廣西大學(xué)行健文理學(xué)院科研項(xiàng)目（No.Y2018ZKK03）;廣西高校中青年教師科研基礎(chǔ)能力提升項(xiàng)目（No.2020KY54013）

作者簡介：石露（1987—?），女，廣西玉林人，碩士，講師，主要從事光滑優(yōu)化和非光滑優(yōu)化等最優(yōu)化算法、數(shù)學(xué)教學(xué)等方面的研究。