求解約束多目標(biāo)優(yōu)化問題的一種Barzilai-Borwein投影梯度法研究

摘 要：基于Barzilai-Borwein規(guī)則使用不同的平衡因子來調(diào)節(jié)目標(biāo)函數(shù)之間的平衡性，減少多目標(biāo)投影梯度算法受目標(biāo)函數(shù)之間不平衡的影響，提出了一種Barzilai-Borwein投影梯度法（BBPMG法）。在一定的假設(shè)條件下，BBPGM法具有良好的收斂性。同時(shí)對BBPGM法進(jìn)行大量的數(shù)值試驗(yàn)，結(jié)果表明BBPGM法具有更好的數(shù)值性能。

關(guān)鍵詞：約束多目標(biāo)優(yōu)化問題；投影梯度算法；Barzilai-Borwein規(guī)則；收斂性

中圖分類號：O221" " " 文獻(xiàn)標(biāo)識碼：A" " "文章編號：1674-0033（2024）06-0016-07

引用格式：張丹，劉寶鈺.求解約束多目標(biāo)優(yōu)化問題的一種Barzilai-Borwein投影梯度法研究[J].商洛學(xué)院學(xué)報(bào)，2024，38（6）：16-22.

A Study on Barzilai Borwein Projection Gradient Algorithmfor Solving Constrained Multi-objective Optimization Problems

ZHANG Dan， LIU Bao-yu

（National Center for Applied Mathematics in Chongqing， Chongqing Normal University， Shapingba" 401331， Chongqing）

Abstract： Based on Barzilai-Borwein rule， this study proposes a Barzilai-Borwein projection gradient method （BBPGM） that uses different balancing factors to adjust the balance among objective functions， thereby reducing the impact of imbalance between objective functions on the multiobjective projection gradient algorithm. Under certain assumptions， the BBPGM method exhibits good convergence properties. A large number of numerical experiments are also conducted on the BBPGM method， and the results show that the BBPGM method has better numerical performance.

Key words： constrained multiobjective optimization problems; projective gradient algorithm; Barzilai-Borwein rule; convergence

考慮帶約束的凸多目標(biāo)優(yōu)化問題（MOP）：

Min" G（x）=（g1（x），g2（x），…，gm（x））T（1）

s.t." " x∈C（2）

其中C是Rn中的非空閉凸子集，gi（x）（i=1，2，…，m）都是至少二階連續(xù)可微的凸實(shí)值函數(shù)。

Graa Drummond等[1]首次提出了經(jīng)典投影梯度方法的擴(kuò)展。基于文獻(xiàn)[1]，Bello-Cruz[2]針對于目標(biāo)函數(shù)有可能非光滑時(shí)的情況提出了投影次梯度方法?；谖墨I(xiàn)[2]，Brito等[3]提出了一種松弛投影次梯度方法。Bento等[4]利用加權(quán)技術(shù)來降低迭代成本。Morovati等[5]指出了Armijo單調(diào)線搜索會(huì)導(dǎo)致相對較小的步長從而減慢收斂速度，于是擴(kuò)展了Barzilai-Borwein規(guī)則來求解多目標(biāo)優(yōu)化問題。針對文獻(xiàn)[5]中的問題，Grippo 等[6]提出了極大型非單調(diào)線搜索，Zhang 等[7]提出了平均型非單調(diào)線搜索。基于文獻(xiàn)[7]，Zhao等[8]證明了多目標(biāo)優(yōu)化的平均型非單調(diào)投影梯度法的線性收斂性。Fazzio等[9]引入非單調(diào)線搜索技術(shù)提出了一種新的非單調(diào)線搜索技術(shù)。Wang等[10]在投影梯度算法里融入記憶動(dòng)量項(xiàng)改進(jìn)搜索方向。針對目標(biāo)函數(shù)之間的不平衡，Chen等[11]對無約束問題提出了Barzilai-Borwein下降方法。帶約束多目標(biāo)優(yōu)化問題中目標(biāo)函數(shù)之間的不平衡同樣減慢收斂速度，無約束方法對于直接處理約束條件具有一定的局限性，可能導(dǎo)致無法找到滿足約束的解。 而投影梯度法能夠有效處理約束條件，利用投影確保解滿足約束條件，這使得投影梯度算法成為解決帶約束多目標(biāo)優(yōu)化問題的一種經(jīng)典而有效的方法。相比于以往的非單調(diào)策略和公共步長策略，本文基于文獻(xiàn)[5]中的Barzilai-Borwein規(guī)則，結(jié)合投影梯度法處理約束條件，對帶約束多目標(biāo)優(yōu)化問題的所有目標(biāo)函數(shù)使用非公共步長策略來調(diào)節(jié)目標(biāo)函數(shù)之間的平衡性。

1" 預(yù)備知識

本文中記Rn為n維歐氏空間，[Rn][+]={x∈Rn：xi≥0，i∈{1，2，…，n}}記為Rn中的非負(fù)象限，然后記[Rn][++]={x∈Rn：xi≥0，i∈{1，2，…，n}}為Rn中的正象限。對Rn中的任意兩個(gè)向量x和y，其中x：=（x1，x2，…，xn）T，y：=（y1，y2，…，yn）T，x和y的內(nèi)積定義為〈x，y〉，x的歐式范數(shù)定義為||x||=，Rn中的偏序關(guān)系用符號?和?表示，x?y當(dāng)且僅當(dāng)y-x∈[Rn][+]，x?y當(dāng)且僅當(dāng)y-x∈[Rn][++]。

引理1" 如果G（x）每一個(gè)分量函數(shù)gi（x）（i=1，2，…，m）是凸函數(shù)，則[gi（x）][△]在有界集上是有界的。

定義1 C是Rn中的非空子集。若對于所有的x∈C，存在k和一個(gè)可求和的序列δk?R+使得||xk+1-x||≤||xk-x||+δk，?k≥k，則稱序列｛xk｝擬-Fejér收斂于C。

引理2 如果｛xk｝在非空集合C是擬-Fejér收斂的，則

1）｛xk｝是有界的。

2）如果｛xk｝的一個(gè)聚點(diǎn)x∈C，則 [limxk=x][k→∞]。

2" Barzilai-Borwein投影梯度算法（BBPGM算法）

步驟0：選擇參數(shù)0lt;κ1≤[ξ0][i]≤κ2，x0∈C為初始點(diǎn)。令k=0。

步驟1：計(jì)算[u0][i]=[gi（x0）][△]。如果[min||[u0][i]||][1≤i≤m]=0， 則停止。否則，取η0=[max][1≤i≤m][||[u0][i]||]。計(jì)算搜索方向υ0：

υ0=[argmin

υ∈C-xk]{υ2+[max

1≤i≤m]〈，υ〉}。

如果υ0=0，則停止。否則，轉(zhuǎn)步驟5。

步驟2：取[uk][i]=[gi（xk）][△]。如果[min||[uk][i]||][1≤i≤m]=0，則停止。否則，計(jì)算ηk=[max

1≤i≤m]{1，||[uk][i]||}。

步驟3：更新[ξk][i]，記sk-1=xk-xk-1，yk-1=[gi（xk）][△]-[gi（xk-1）][△]。

[ξk][i]=min{

，max{

，

}}，〈[sk-1，yk-1][i]〉gt;0

min{

，max{

，

}}，" " "〈[sk-1，yk-1][i]〉lt;0

，" " " " " " " " " " " " " " " " "〈[sk-1，yk-1][i]〉=0

步驟4：計(jì)算搜索方向υk。

υk：=[argmin

υ∈C-xk]｛υ2+[max

1≤i≤m]〈，υ〉｝。

如果υk=0，則停止。否則，轉(zhuǎn)步驟5。

步驟5：xk+1：=xk+υk。

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

為了證明BBPGM算法的收斂性，需要重要的引理3。

引理3" xk是由BBPGM算法生成的序列。如果υk是由步驟4計(jì)算得到的搜索方向，則存在 [λk][i]≥0和[λk][i]=1，使得

[λk][i]〈，υk〉=[max

1≤i≤m]〈，υk〉和

〈υk+[λk][i]，υ-υk〉≥0，?υ∈C-xk。

3" BBPGM算法的收斂性分析

命題1" 對于所有k∈N，有xk∈C。

證明：利用數(shù)學(xué)歸納法。因?yàn)镃是一個(gè)非空閉凸集，x0∈C，υ0∈C-x0，所以x1=x0+υ0∈C。假設(shè)xk∈C，由于υk∈C-xk，xk+1=xk+υk∈C。所以對于所有k∈N，有xk∈C。

命題2" 對于所有的k∈N，有

1）||υk||≤成立。

2）||xk+1-xk||≤成立。

證明：1）因?yàn)棣詋是由步驟4計(jì)算得到的搜索方向，則存在[λk][i]≥0和[λk][i]=1使得

〈υk+[λk][i]，υ-υk〉≥0，?υ∈C-xk。

因?yàn)閤k∈C，所以0∈C-xk。令υ=0，那么

||υk||2≤-〈[λk][i]，υk〉≤

[λk][i]||[uk][i]||||υk||≤

||υk||

所以有||υk||≤。

2）因?yàn)棣詋=xk+1-xk，所以||xk+1-xk||≤。

命題3 對于所有的k∈N，如果υk：=

[argmin

υ∈C-xk]｛υ2+[max

1≤i≤m]〈，υ〉｝對于任意的y∈C存在[λk][i]≥0和[λk][i]=1使得

〈υk，xk-y〉≤〈[λk][i]，y-xk〉+。

證明：υk是由步驟 4計(jì)算得到的搜索方向，則存在[λk][i]≥0和[λk][i]=1使得

[λk][i]〈，υk〉=[max

1≤i≤m]〈，υk〉

和

〈υk+[λk][i]，υ-υk〉≥0，?υ∈C-xk。

那么對于任意的y∈C，

〈υk，xk-y〉≤

-||υk||2+〈[λk][i]，y-xk〉-〈[λk][i]，υk〉≤

〈[λk][i]，y-xk〉+[λk][i]||[uk][i]||||υk||≤

〈[λk][i]，y-xk〉+[ξk][i]||υk||≤

〈[λk][i]，y-xk〉+。

命題4 對于所有的k∈N，任意y∈C存在 [λk][i]≥0和[λk][i]=1使得

||xk+1-y||2≤+||xk-y||2+

[λk][i][ξk][i]gi（y）-gi（xk）。

證明：對于任意 y∈C。

||xk+1-y||2=||xk+1-xk+xk-y||2=

||xk+1-xk||2+||xk-y||2+2〈xk+1-xk，xk-y〉=

||υk||2+||xk-y||2+2〈υk，υk-y〉≤

+||xk-y||2+2〈[λk][i]，y-xk〉≤

+||xk-y||2+[λk][i][ξk][i]gi（y）-gi（xk）。

假設(shè)1" 輔助集合T：={y∈C：?[k][～]∈N使得G（y）?G（xk），?k≥[k][～]}是非空的。

引理 4" 如果假設(shè)1成立，則{xk}是有界的。

證明：由于xk∈C，?k∈N。則對任意y∈T，有G（y）?G（xk），?k≥[k][～]成立。則k≥[k][～]和y∈T，可以有||xk+1-y||2≤+||xk-y||2，因?yàn)閷τ谌我獾膋≥1，有l(wèi)t;∞所以xk在T是擬-Fejér收斂的，所以{xk}是有界的。

定理1" 若假設(shè)1成立，則由BBPGM算法生成的序列xk的所有聚點(diǎn)都是原問題的弱有效解。

證明：對于任意的k=0，1，…，N，有

+||xk-y||2-||xk+1-y||2≥

[λk][i][ξk][i]gi（xk）-gi（y）≥[min

1≤i≤m]｛[ξk][i]g（xk）-gi（y）｝。（3）

將式（3）從k=0，1，…，N相加得到

+||x0-y||2-||xN+1-y||2≥

[min

1≤i≤m]{[ξk][i]gi（xk）-gi（y）}，

令N→∞，并且存在Bgt;0使得3lt;B，則

[min

1≤i≤m]｛[ξk][i]g（xk）-gi（y）｝≤

||x0-y||2+≤

||x0-y||2+3≤

||x0-y||2+Blt;+∞。

對于任意的?k∈N，都存在一個(gè)Lgt;0，使得ηk≤L。定義γk：=[min

1≤i≤m]{gi（xk）-gi（y）}，則存在其一個(gè)子列｛[γi][k]｝，使得[lim

k→∞][γi][k]≤0。證明γk所有的聚點(diǎn)都是非正的，利用反證法，如果不成立，則存在gt;0及｛γk｝的子列｛[γi][k]｝使得[γi][k]≥對于任意的k∈N都成立?？梢詷?gòu)造一個(gè)｛γk｝的子列｛[γi][k]｝，其中jk滿足：j0=min{n≥0：γn≥}，j2k+1=min{n≥j2k：γn≤}和j2k+2=min{n≥j2k+1：γn≤}，此時(shí)[γj][2k]-[γj][2k+1]≥。因?yàn)閷τ?k∈N，||υk||≤，所以

γk-γk+1=[min

1≤i≤m]{gi （xk）-gi（y）}-[min

1≤i≤m]{gi（xk+1）-gi（y）}=

[min

1≤i≤m]｛gi （xk）-gi（y）｝-[min

1≤i≤m]{ gi（xk+1）-gi（xk）+gi（xk）-gi（y）}≤

[min

1≤i≤m]｛gi （xk）-gi（y）｝-[min

1≤i≤m]{gi（xk+1）-gi（xk）}-[min

1≤i≤m]{gi（xk）-gi（y）}=

[max

1≤i≤m]{gi（xk）-gi（xk+1）}≤[max

1≤i≤m]||[uk][i]||||（xk-xk+1）||≤。

又因?yàn)?/p>

[min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）｝=

[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）｝+

[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）｝≥

[min

1≤i≤m]{[ξk][i]gi（xn）-gi（y）}+

[][｛k|γk≤0｝][min

1≤i≤m]{[ξk][i]gi（xk）-gi（y）}≥

+[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gigi（xn）-gi（y）}。

所以

+∞gt;[min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）}≥

+[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）}≥ （γn-γn+1）+[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）}=

（[γj][2k]-[γj][2k+1]）+[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）}。

分兩種情況進(jìn)行分析。如果集合｛k|γk≤0｝是有限的。那么

S=[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi （xk）-gi（y）｝

是有限的，則

（[γj][2k]-[γj][2k+1]）+

[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi （xk）-gi（y）｝≥

-+S=+∞矛盾。如果集合｛k|γk≤0｝是無限的。因?yàn)?∞=[ξk][i]，以存在kgt;0使得

[min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）｝≥

-，?k≥k。

定義S：=[][｛kgt;k|yk≤0｝]（[γj][2k]-[γj][2k+1]）+

[][｛kgt;k|yk≤0｝][min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）｝是有限的，則

（[γj][2k]-[γj][2k+1]）+

[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）｝≥

[][｛0≤k|γk≤0｝]（ [γj][2k]-[γj][2k+1] ） +[][｛k|γk≤0｝][min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）｝=

[][｛0≤k≤k|yk≤0｝]" " +" [][｛k≤k|yk≤0｝]" [min

1≤i≤m]" "｛" " [ξk][i]gi" （xk）-gi （y）｝+

[][｛0≤k≤k|yk≤0｝]

+

[min

1≤i≤m] ｛ [ξk][i]gi （xk）-gi （y）｝≥

S+

[][｛kgt;k|yk≤0｝]（[γj][2k]-[γj][2k+1]+[min

1≤i≤m]｛[ξk][i]gi（xk）-gi（y）｝）≥

S+[][｛kgt;k|yk≤0｝]（-）=+∞矛盾，所以｛γk｝的所有聚點(diǎn)都是非正的。假設(shè)x*是｛xk｝的一個(gè)聚點(diǎn)，則存在｛xk｝的子列｛[xl][k]｝使得[lim

k→∞][xl][k]→x*∈C。如果x*不是弱有效解，則存在 [x]∈C使得G（ [x]）?G（x*）。令y= [x]，則

[lim

k→∞][γl][k]=[lim

k→∞][min

1≤i≤m]{gi（[xl][k]）-gi（ [x]）}→

[min

1≤i≤m]{gi（x*）-gi（ [x]）}≤0，

這與G（ [x]）?G（x*）矛盾。所以不存在x∈C使得G（x）?G（x*），即x*是弱有效解。

4" BBPGM算法的收斂率

利用效用函數(shù)u0（xk）證明收斂率，其中u0（xk）=[max

y∈C][min

1≤i≤m]{gi（xk）-gi（y）}。

假設(shè)2 對于任意i∈{1，2，…， m}，水平集

{x∈C|gi（xk）≤[gi（x）]}是緊集。

假設(shè)3 存在[k][～]∈N使得對于任意的k≥[k][～]集合

Tk={x∈xk， xk+1，…， xk|G（x）?G（xk）}，?k∈|k，k|非空。

定理2 若假設(shè)2和假設(shè)3成立，則BBPGM算法至少具有O（）的收斂率。

證明：因?yàn)閷τ谌我鈑≥[k][～]，u0（xk）≥0，其中xk∈Tk。令M≥[k][～]。有

+||xk-y||2-||xk+1-y||2≥

[γk][i][ξk][i]gi（xk）-gi（y）≥

[min

1≤i≤m][ξk][i]gi（xk）-gi（y）（4）

將式（4）從k=[k][～]到k=M相加得到

+||xk-y||2≥

[min

1≤i≤m]{ [ξk][i]gi（xk）-gi（y）}≥

[min

1≤i≤m]{ [ξk][i]gi （xM）-gi（y）}。

記[C][～]={x∈C|gi（x）≤gi（xk）}。存在R0≥0使得對任意的y∈[C][～]，||xk-y||2≤R0，并且

[max

y∈C][min

1≤i≤m]{gi（xk）-gi（y）}≥0，[ξ0][i]gt;κ1gt;0，

≥[ξk][i]≥所以有

+R0≥[max

y∈C]（+||xk-y||2）≥

[max

y∈C][min

1≤i≤m]{[ξk][i]gi（xM）-gi（y）}=

[max

y∈C][min

1≤i≤m]{[ξk][i]gi（xM）-gi（y）}≥

u0（xM）。

又因?yàn)榇嬖贚gt;1使得ηk" ≤L對于k≥[k][～]成立，所以對于任意的k≥[k][～]有

u0（xM）≤≤

≤

≤

≤

≤

記G=gt;0，則u0（xk）≤即BBPGM算法至少具有O（）的收斂率。

5" 數(shù)值試驗(yàn)

相比于文獻(xiàn)[1]中的MPGM算法，BBPGM算法具有良好的收斂效果和更快的收斂速度。這些結(jié)果都是用 PYTHON 在 CPU 型號為13th Gen Intel（R） Core（TM） i5-1340P（1.90 GHz）和運(yùn)行內(nèi)存為16.0GB 的筆記本電腦上運(yùn)行的。

例1 [min

y∈R2]F（x）=f1（x），f2（x），

" " " " "s.t. x1≥x2，

" " " " " " " x1+x2gt;-1，

其中f1（x）=[x2][i]，f2（x）=（xi-1）2。BBPGM算法的參數(shù)設(shè)置為κ1=0.000 000 2，κ2=2 000 000，[ξ0][i]=1。通過PYTHON分別隨機(jī)生成100個(gè)初始點(diǎn)、500個(gè)初始點(diǎn)，再使用PYTHON的最小優(yōu)化器進(jìn)行優(yōu)化，分別繪制出帕累托前沿（圖1）。通過這個(gè)例子可以看出BBPGM算法具有良好的收斂效果。

將BBPGM算法與文獻(xiàn)[1]中的MPGM算法進(jìn)行比較，隨機(jī)生成200個(gè)初始點(diǎn)，用iter記錄算法的平均迭代次數(shù)，用CPU記錄算法的平均迭代時(shí)間，BBPGM算法表現(xiàn)出具有更快的迭代速度。其中n代表自變量維數(shù)，m代表目標(biāo)函數(shù)維數(shù)，xl代表自變量下界，xu代表自變量上界，如表1所示，BBPGM算法具有更快的收斂速度。

6" 結(jié)語

目標(biāo)函數(shù)之間的不平衡會(huì)導(dǎo)致投影梯度算法收斂速度緩慢?；贐arzilai-Borwein規(guī)則提出了一種求解帶約束多目標(biāo)優(yōu)化問題的Barzilai-Borwein投影梯度法，理論證明該算法具有良好的收斂性，試驗(yàn)表明算法具有更好的數(shù)值性能。對于目標(biāo)函數(shù)之間的不平衡這一類問題，后續(xù)工作考慮Barzilai-Borwein規(guī)則結(jié)合可變度量法，使用二階方法調(diào)節(jié)目標(biāo)函數(shù)之間的不平衡。

參考文獻(xiàn)：

[1]" GRAA DRUMMOND L G， IUSEM A. A projected gradient method for vector optimization problems [J].Computational Optimization and Applications，2004，28（1）：5-29.

[2]" BELLO CRUZ， J Y. A subgradient method for vector optimization problems[J].SIAM Journal on Optimization，2013，23（4）：2169-2182.

[3]" BRITO A S， CRUZ NETO J X， SANTOS P S M， et al." A relaxed projection method for solving multiobjective optimization problems [J].European Journal Operational Research，2017，256（1）：17-23.

[4]" BENTO G C， CRUZ NETO J X， SANTOS P S M， et al. A weighting subgradient algorithm for multiobjective optimization[J].Optimization Letters，2018，12（2）：399-410.

[5]" MOROVATI V， POURKARIMI L， BASIRZADEH H. Barzilai and Borwein's method for multiobjective optimization problems[J].Numerical Algorithms，2016，72（3）：539-604.

[6]" GRIPPO L， LAMPARIELLO F， LUCIDI S. A nonmonotone line search technique for newton's method[J].SIAM Journal on Numerical Analysis，1986，

23（4）：707-716.

[7]" ZHANG H C， HAGER W. A nonmonotone line search technique and its application to unconstrained optimization[J]. SIAM Journal on Optimization，2004，14（4）：1043-1056.

[8]" ZHAO X， YAO J C. Linear convergence of a nonmonotone

projected gradient method for multiobjective optimization[J]. Journal of Global Optimization，2022，82（3）：577-594.

[9]" FAZZIO N S， SCHUVERDT M L. Convergence analysis of a nonmonotone projected gradient method for multiobjective optimization problems [J].Optimization Letters，2019，13（4）：1365-1379.

[10] WANG J J， TANG L P，YANG X M. Spectral projected subgradient method with a 1-memory momentum term for constrained multiobjective optimization problem[J]. Journal of Global Optimization，2024，89（2）：277-302.

[11] CHEN J， TANG L P， YANG X M. A Barzilai-Borwein descent method for multiobjective optimization problems[J].European Journal of Operational Research，2023，311（1）：196-209.

[12]" FLIEGE J， GRAA DRUMMOND L M， SVAITER B F. Newton's method for multiobjective optimization[J].SIAM Journal on Optimization，2009，20（2）：602-626.

[13] JIN Y C， OLHOFER M， SENDHOFF B. Dynamic weighted aggregation for evolutionary multi-objective optimization： why does it work and how[C].GECCO.01 Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation，2001：1042-1049.

收稿日期：2024-06-11

基金項(xiàng)目：重慶師范大學(xué)研究生科研創(chuàng)新項(xiàng)目（YKC23037）

作者簡介：張丹，男，重慶彭水人，碩士研究生