多用戶最優(yōu)化的兩種對偶方法

向 福

(重慶師范大學數(shù)學學院，重慶401331)

0 引言

論述了一般形式的多用戶在網(wǎng)絡(luò)資源管理上出現(xiàn)的問題，如在通信網(wǎng)絡(luò)中的速率分配.一個多用戶問題是一個約束最優(yōu)化問題結(jié)合N個用戶的一個有限集，每個用戶i有一個凸的成本函數(shù)fi(xi)，僅依賴于它的決策變量xi，決策向量xi，i=1，2，…，N通常受線性不等式(x1，x2，…，xN)≤bj，j=1，2，…，N 的有限系統(tǒng)約束.實際上多用戶問題是一個形式化的凸最優(yōu)化問題，且具有如下形式:

其中Xi是用戶第i個決策變量xi的約束集.在許多應(yīng)用中，比起成本函數(shù)，用戶的抵消函數(shù)更特殊化，在這種情況下，多用戶問題是一個凸最大化問題.在多用戶最優(yōu)化中，問題信息是分布式的.特別地，假定用戶i僅知道自身的成本函數(shù)fi(xi)和約束集Xi，用戶i可以修改它自身的決策向量xi，但可能查看其他用戶的決策變量(xj)j≠i.它往往是算法參數(shù)的選擇.

1 符號和初步結(jié)果

傳統(tǒng)地，多用戶問題(1)的特點是只有通過一個可分離的目標函數(shù)的用戶決策變量耦合.一般地，客觀上不需要可分離，并且用戶決策共同由凸約束集限制.考慮推廣到規(guī)范的具有形如式(2)多用戶優(yōu)化問題:

其中，N是用戶數(shù)，fi(xi)是用戶i的成本函數(shù)且依賴于決策變量xi∈Rni，Xi∈Rni是用戶i的約束集;函數(shù)c(x)是一個依賴于用戶決策的節(jié)成本函數(shù)，即x=(x1，x2，…，xN)∈Rn，其中n=

要求函數(shù)fi:和c:Rn→R是凸的和連續(xù)可微的，dj:對每一個j是連續(xù)可微的凸函數(shù).記不等式約束 dj(x)≤0，j=1，2，…，m 為 d(x)≤0，d(x)=(d1(x)，d2(x)，…，dm(x))T.假定用戶約束集 Xi非空、凸的、閉的，記f*和X*是問題的最優(yōu)值和最有解集.

假設(shè)2 集X是閉的、凸的、有界的，函數(shù)fi(xi)，i=1，2，…，N，和c(x)是連續(xù)可微的，定義梯度映射

假設(shè)3 梯度映射F(x)是在集X上具有約束L的李普希茲連續(xù)的，即對所有x，y∈X，都有

假設(shè)4 對每一個j，梯度?dj(x)在X上具有李普希茲連續(xù)，且Lj＞0，即

2 正規(guī)劃原始－對偶方法

2.1 原 理

考慮其正規(guī)化，得到在原始和對偶空間上的正規(guī)化拉格朗日函數(shù).特別地，對v＞0和ε＞0，將Lv，ε記作正規(guī)化拉格朗日函數(shù)，給定

梯度映射?xLv，ε(x，λ)有如下定義

確定一個包含對偶最優(yōu)解的緊集，可以通過觀察正規(guī)拉格朗日函數(shù)Lv，ε來完成，作為兩步正規(guī)化結(jié)論:一是正規(guī)初始問題(2)，二是正規(guī)它的拉格朗日函數(shù).特別地，對v＞0，正規(guī)化問題(2)由如下給定:

其相應(yīng)的對偶問題是

觀察對 0≤v≤v'，有，推斷.所以，緊集Dv是嵌套的，并且它們的交是非空緊集D，其中包含初始問題的最優(yōu)對偶解.

假設(shè)Slater條件成立并且集合X是非空的，使得構(gòu)造這樣的緊集是可能的.特別地，假定嵌套的緊凸集族，v≥0，滿足關(guān)系(9)并已經(jīng)確定.在這種情況下，確定 zv，ε=(xv，ε，λv，ε)∈X × Dv的變分不等式，使得

所有z=(x，λ)∈X×Dv，和變分不等式(4)有相同的解集，其中λ受若干隨機變量約束.

2.2 原始對偶方法

現(xiàn)在考慮通過原始對偶方法求解變分不等式(10)，此方法用戶可以選擇原始步長和對偶步長.特別是，考慮下面的算法:其中αi＞0是用戶i的原始步長，τ＞0是對偶步長.

定理1 在假設(shè)2－假設(shè)4成立條件下，設(shè) z{}k是由式(11)迭代產(chǎn)生的序列.則下面的不等式成立

其中，α＞0及τ＞0分別是原始步長和對偶步長.在推論1中，序列 z{ }k，zk=(xk，λk)，是收斂的.

推論1 在假設(shè)2－假設(shè)4成立條件下，設(shè) z{}k是式(12)迭代產(chǎn)生的序列，則成立不等式

2.3 正規(guī)化對偶方法

考慮用正規(guī)化處理拉格朗日子問題的不精確解.對于不精確解，可以拓寬誤差界限.不精確性是確立構(gòu)建分布式網(wǎng)絡(luò)方案，要求在一個固定的時間范圍內(nèi)的初始解.在標準對偶框架工作中，對每一個λ∈Rm+，拉格朗日子問題的解x(λ)∈X由解(X，?xL(x，λ))給定，滿足不等式

其中向量xt記式(13)的解.

引理1 在假設(shè)2成立的條件下，λ不變時，函數(shù)－d(x(λ))強制于，其中 M=max‖?d(x)‖.dx∈X

為了證明對偶問題的收斂結(jié)果，對于相應(yīng)的拉格朗日子問題的精確解，定理2可以說明.

定理2 在假設(shè)1和假設(shè)2成立條件下，設(shè)步長τ滿足

3 結(jié)論

應(yīng)用對偶方法可能要求最優(yōu)初始解對每一個對偶限制步長.一個正規(guī)化對偶方法的自然收縮依賴于精確的初始解.進一步，對于得到解的邊界誤差和拉格朗日乘子也是上界不可行的.最后，在拓展了這些結(jié)果的情況下，每個用戶可自主地選擇其正規(guī)化參數(shù).

［1］KWLLY F P，MAULLOO A K，TAN D K H.Rate control for communication networks:Shadow prices，proportional fairness and stability［J］.Operation Research Society，1998(16):237-252

［2］王力，周宗福.一類變系數(shù)混合時滯細胞神經(jīng)網(wǎng)絡(luò)的指數(shù)穩(wěn)定性和周期解［J］.重慶工商大學學報:自然科學版，2010，27(5):427-430

［3］NESTEROV Y.Smooth minimization of nonsmooth functions［J］.Mathematical Program，2005，103(1):127-152

［4］彭燕妮.基于遺傳算法的MPLS網(wǎng)絡(luò)優(yōu)化研究［J］.重慶工商大學學報:自然科學版，2005，22(5):37-40

［5］ZAWA H U.Iterative methods in concave programming，in Studies in Linear and Nonlinear Programming［M］.Standford University Press，1958