[發明專利]一種用于選址問題的魯棒優化模型求解方法

有效

• 申請號: 201810293335.5
• 申請日: 2018-04-04
• 公開（公告）號: CN108665089B
• 公開（公告）日: 2022-04-15
• 發明（設計）人: 游科友;謝佩;宋士吉;吳澄
• 申請（專利權）人: 清華大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 廖元秋

1.一種用于選址問題的魯棒優化模型求解方法，其特征在于，該方法包括以下步驟：

1)建立用于選址問題的魯棒凸優化模型，并轉化為對應的參數約束模型；具體步驟如下：

1-1)建立用于選址問題的魯棒凸優化模型；

設有N個服務對象，N≥2，為任意服務對象i∈{1，...，N}選擇最優的服務中心的位置建立基于選址問題的魯棒凸優化模型表達式如下：

s.t.||q_i-x_i||≤δ_i (1)

在給定服務中心的位置后，表示服務對象的最壞情況下的總代價，式(1)的目標就是最小化最壞情況的總代價；

其中，x_i為服務對象i的量測位置坐標；q_i為服務對象i的實際位置坐標；δ_i為服務對象i量測位置和實際位置偏差的上界；c_i為服務對象i與服務中心的距離代價系數；x為服務中心選址的位置；

1-2)將步驟1-1)建立的魯棒凸優化模型轉化為對應的參數約束模型；

引入松弛變量t₁，...，t_N，將式(1)轉化為如下所示的無限約束優化模型：

引入如下符號：

c＝[0，0，c₁，c₂，...，c_N]^T

t＝[t₁，t₂，...，t_N]^T

θ＝[x；t]^T

q＝[q₁；...；q_N]^T

f_i(θ，q)＝||x-q_i||-t_i

Q＝B(x₁，δ₁)×…×B(x_N，δ_N)

其中，B(x_i，δ_i)(i＝1，...，N)表示中心坐標為x_i，半徑為δ_i的球，×表示笛卡爾積，則式(2)轉化為如下所示的參數約束模型：

其中，是參數q的不確定集合，為凸函數，

2)將步驟1)得到的參數約束模型轉化為近似模型，決定不確定集采樣的樣本個數，將約束條件分配到進程上并構建進程之間的通信的權重矩陣；具體步驟如下：

2-1)將步驟1)得到的參數約束模型轉化為近似模型；

假設參數是以相互獨立的均勻分布采樣自不確定集合Q，建立如式(3)所示模型經不確定參數采樣的近似模型如下：

其中，N_bin表示不確定集采樣的樣本個數；

如式(4)所示的近似模型將如式(5)所示的包含無窮個不確定帶參數約束構成的集合減弱為如式(6)所示的包含有限約束構成的集合：

Θ_scenario＝{θ|f(θ，q⁽ⁱ⁾)≤0，i＝1，...，N_bin，q⁽ⁱ⁾∈Q}， (6)

其中，Θ_robust為魯棒可行集，Θ_scenario是參數采樣后的約束構成的集合即情景魯棒可行集；

2-2)決定不確定集采樣的樣本個數；

給定式(3)中的決策變量記表示該決策變量在不確定參數集合下的不可行概率；若存在參數∈，δ∈(0，1)，使得概率不等式成立，則樣本個數滿足：

其中，e＝2.718為自然底數；

2-3)將約束條件分配到進程上；

設總共有m個進程，將N_bin個約束劃分到每個進程上，令進程j處理n_j個約束，則n₁+…+n_m＝N_bin；

對于進程1≤j≤m，引入函數向量：

則每個進程處理的約束表達式如下：

f_j(θ)≤0，j＝1，...，N_bin (8)

2-4)構建進程之間的通信的權重矩陣；

用圖來刻畫進程之間的通信連接關系，其中表示m個進程，；對于任意兩個進程邊(i，j)∈ε當且僅當i從j直接獲取信息；若邊(i，j)∈ε，則對該邊賦予權值a_ij＞0；若邊則對該邊賦予權值a_ij＝0；對所有的邊賦予對應權值后，形成權重矩陣A＝[a_ij]；

3)對步驟2)的近似模型求解，得到選址問題的最優解；

令圖是強連通的，即對于任意存在p個進程使得邊(i，i₁)，(i₁，i₂)，...，(i_p-1，i_p)，(i_p，j)∈ε；分別針對無向圖和有向圖兩類通信網絡提出兩種分布式優化算法，具體如下：

3-1)針對無向圖網絡的分布式原始對偶次梯度算法；

對于無向圖，(i，j)∈ε當且僅當(j，i)∈ε，對于任意一個進程i，記它的鄰居構成的集合為對于函數f(θ)，記f₊(θ)＝max{0，f(θ)}為f的非負部分，并記0_n表示n維的零向量；如式(4)所示的模型與下面模型形式等價：

對式(9)中第一行等式約束引入拉格朗日乘子對第二行等式約束引入拉格朗日乘了分布式地更新θ_j及λ_j，γ_j，將使θ_j同時收斂到如式(4)所示模型的最優解；具體步驟如下：

3-1-1)初始化：對每個進程初始化輪次k＝0，解的狀態θ_j＝0_N+2，約束對應的拉格朗日乘子分別初始化為λ_j＝0_N+2及

3-1-2)局部信息交換：對于每個進程首先將其當前狀態θ_i傳遞給它的鄰居進程；當進程i從其鄰居進程收到θ_j后計算然后再將預更新的對偶變量回傳給它的鄰居進程

3-1-3)局部變量更新：當每個進程收到回傳的預更新對偶變量之后，每個進程按照如下方式更新變量：

λ_j←λ_j+ζb_j，

γ_j←γ_j+ζg_j(θ_j)，

其中，s_j是g_j在θ_j處的次梯度，即ρ是一個正的懲罰因子，ζ取步長

3-1-4)結束一次迭代，設置k＝k+1；

3-1-5)重復步驟3-1-2)至3-1-4)，直至k≥k₀，迭代求解結束，其中k₀是預先設置的最大迭代步數；求解完畢后，每個θ_j的前兩維表示選址位置的坐標，后N維表示N個服務對象的代價函數，得到選址問題的最優解；

3-2)針對有向圖網絡的分布式Polyak隨機投影算法；

對于任意一個進程i，記它的入鄰居進程集合為出鄰居集合為具體步驟如下

3-2-1)初始化：對每個進程設置迭代輪次k＝0，解的狀態θ_j＝0_N+2；

3-2-2)局部信息交換：每個進程j∈v將變量θ_j傳遞給對應的出鄰居；

3-2-3)局部變量更新：每個進程接收到對應的入鄰居發送的向量后采用如下方式更新變量：

計算

以均勻分布隨機選取ω_j∈{1，...，n_j}

其中，d_j是在v_j處的次梯度，ζ為滿足如下條件的步長：

3-2-4)結束一次迭代，設置k＝k+1；

3-2-5)重復步驟3-1-2)至3-1-4)，直至k≥k₀，迭代求解結束，其中k₀是預先設定的最大迭代次數；求解完畢后，每個θ_j的前兩維表示選址位置的坐標，后N維表示N個服務對象的代價函數，得到選址問題的最優解。