论辅助问题原则的应用
摘要
辅助问题原理(APP)源于分解-协调方法的一般理论,为一级方法和两级方法建立了一个全面的框架。本文专门介绍了 APP 两级方法的成果,以便有效地应用于一些工程问题。
关键字优化算法、分解/协调方法、辅助问题原理。
1.导言
在并行/分布式计算环境中,可以有效地解决大规模优化问题。事实证明,去分区协调方法对利用这种环境非常有用;从这种方法衍生出的方法可分为单级或定点方法(子问题之间没有明确的协调行动)和双级方法(子问题通过在协调级更新的价格而得到解决)。
辅助问题原理(APP,参考文献 1-2)源自分解-协调方法的一般理论。它为单层和双层方法建立了一个全面的框架,并将许多已知算法作为特例纳入其中。在合理的假设条件下,APP 已经建立了收敛性证明,特别是对于两级方法。
利用众所周知的变量复制技术,总是可以得到一个优化问题,其可行性集可以很容易地分解为可行性子集的笛卡尔乘积,某些线性相等的情况除外。这样就很容易将问题分解成仅由线性相等关系耦合的子问题,这就是应用 APP 两级方法的完美候选方案。在某些应用中,例如电力系统的优化问题,会遇到一些变量重复出现的困难,这些变量总是以差分形式出现,我们把它们称为
Δ
Δ
Delta \Delta 变量。在之前的一篇论文(参考文献 3)中,我们已经设想了一种合适的方法来为
Δ
Δ
Delta \Delta 变量建模,以便进行后续的重复/分解,这样就可以直接应用 APP 的两级方法。
本文将针对具有
Δ
Δ
Delta \Delta 变量的 APP 得出具体结果,以改进其迭代方案的特性。我们首先回顾了变量复制技术及其在 APP 中的应用,然后展示了
Δ
Δ
Delta \Delta 变量的建模。接下来,我们利用这种建模的特殊性,获得了一种特定形式的迭代方案,该方案具有一些相关的特点,例如可以轻松地制定子问题的可行性约束条件,并对
Δ
Δ
Delta \Delta 变量进行独立处理。针对大规模电力系统优化问题的研究结果表明了新形式迭代方案的有效性。关于包含这些变量的 APP 方法收敛的充分条件的证明见附录(第 6 节)。
2.变量和 APP 的重复
任何优化问题都可以用一般形式表示
min
f
(
x
)
,
s.t.
g
(
x
)
=
0
,
h
(
x
)
≥
0
,
min
f
(
x
)
,
s.t.
g
(
x
)
=
0
,
h
(
x
)
≥
0
,
{:[min,f(x)","],[" s.t. ",g(x)=0","],[,h(x) >= 0","]:} \begin{array}{ll}
\min & f(x), \\
\text { s.t. } & g(x)=0, \\
& h(x) \geq 0,
\end{array}
其中,
x
x
x x 是变量的
m
m
m m 向量,
f
(
x
)
f
(
x
)
f(x) f(x) 是表示优化目标的标量函数,
g
(
x
)
g
(
x
)
g(x) g(x) 和
h
(
x
)
h
(
x
)
h(x) h(x) 是
s
s
s s 向量,
s
<
m
s
<
m
s < m s<m 和
t
t
t t 是定义了向量
x
x
x x 的可行性约束的相等和不等式约束的向量函数。一般来说,
f
(
x
)
f
(
x
)
f(x) f(x) 和
g
(
x
)
g
(
x
)
g(x) g(x) 或
h
(
x
)
h
(
x
)
h(x) h(x) 的任何分量可能是线性或非线性的,并且可能取决于向量
x
x
x x 的部分或全部分量。 2.1.变量重复。假设问题(1)的形式为
min
f
(
x
1
,
x
2
,
y
)
,
s.t.
g
1
(
x
1
,
y
)
=
0
,
g
2
(
x
2
,
y
)
=
0
,
h
1
(
x
1
,
y
)
≥
0
,
h
2
(
x
2
,
y
)
≥
0
,
min
f
x
1
,
x
2
,
y
,
s.t.
g
1
x
1
,
y
=
0
,
g
2
x
2
,
y
=
0
,
h
1
x
1
,
y
≥
0
,
h
2
x
2
,
y
≥
0
,
{:[min,f(x_(1),x_(2),y)","],[" s.t. ",g_(1)(x_(1),y)=0","],[,g_(2)(x_(2),y)=0","],[,h_(1)(x_(1),y) >= 0","],[,h_(2)(x_(2),y) >= 0","]:} \begin{array}{ll}
\min & f\left(x_{1}, x_{2}, y\right), \\
\text { s.t. } & g_{1}\left(x_{1}, y\right)=0, \\
& g_{2}\left(x_{2}, y\right)=0, \\
& h_{1}\left(x_{1}, y\right) \geq 0, \\
& h_{2}\left(x_{2}, y\right) \geq 0,
\end{array}
其中
x
=
[
x
1
T
,
x
2
T
,
y
T
]
T
,
g
=
{
g
1
,
g
2
}
,
h
=
{
h
1
,
h
2
}
,
x
=
x
1
T
,
x
2
T
,
y
T
T
,
g
=
g
1
,
g
2
,
h
=
h
1
,
h
2
,
x=[x_(1)^(T),x_(2)^(T),y^(T)]^(T),quad g={g_(1),g_(2)},quad h={h_(1),h_(2)}, x=\left[x_{1}^{T}, x_{2}^{T}, y^{T}\right]^{T}, \quad g=\left\{g_{1}, g_{2}\right\}, \quad h=\left\{h_{1}, h_{2}\right\},
和
dim
{
x
1
}
=
m
1
,
dim
{
x
2
}
=
m
2
,
dim
{
y
}
=
m
y
dim
x
1
=
m
1
,
dim
x
2
=
m
2
,
dim
{
y
}
=
m
y
dim{x_(1)}=m_(1),quad dim{x_(2)}=m_(2),quad dim{y}=m_(y) \operatorname{dim}\left\{x_{1}\right\}=m_{1}, \quad \operatorname{dim}\left\{x_{2}\right\}=m_{2}, \quad \operatorname{dim}\{y\}=m_{y} ,
dim
{
g
1
}
=
s
1
,
dim
{
g
2
}
=
s
2
,
dim
{
h
1
}
=
t
1
,
dim
{
h
2
}
=
t
2
dim
g
1
=
s
1
,
dim
g
2
=
s
2
,
dim
h
1
=
t
1
,
dim
h
2
=
t
2
dim{g_(1)}=s_(1),quad dim{g_(2)}=s_(2),quad dim{h_(1)}=t_(1),quad dim{h_(2)}=t_(2) \operatorname{dim}\left\{g_{1}\right\}=s_{1}, \quad \operatorname{dim}\left\{g_{2}\right\}=s_{2}, \quad \operatorname{dim}\left\{h_{1}\right\}=t_{1}, \quad \operatorname{dim}\left\{h_{2}\right\}=t_{2} .
在子集
y
y
y y 不为空的相关情况下(
m
y
≠
0
m
y
≠
0
m_(y)!=0 m_{y} \neq 0 ),可行性约束子集
{
g
1
,
h
1
}
,
{
g
2
,
h
2
}
g
1
,
h
1
,
g
2
,
h
2
{g_(1),h_(1)},{g_(2),h_(2)} \left\{g_{1}, h_{1}\right\},\left\{g_{2}, h_{2}\right\} 是耦合的。在这种情况下,利用变量重复技术,总是可以得到一个新的优化问题,等价于 (2),其理想特性是可行性约束子集是解耦的,原来的耦合通过所谓的一致性约束来执行。它是以增加维度为代价得到的:新优化问题定义在维度为
m
+
m
y
m
+
m
y
m+m_(y) m+m_{y} 的空间中,并添加了
m
y
m
y
m_(y) m_{y} 线性一致性约束。
简而言之,优化问题 (2) 的目标函数采用了一致的新表述,现在用函数
J
J
J J 表示,可写成
min
J
(
u
1
,
u
2
)
≡
min
J
(
x
1
,
x
2
,
y
12
,
y
21
)
,
s.t.
g
1
(
u
1
)
≡
g
1
(
x
1
,
y
12
)
=
0
,
g
2
(
u
2
)
≡
g
2
(
x
2
,
y
21
)
=
0
,
h
1
(
u
1
)
≡
h
1
(
x
1
,
y
12
)
≥
0
,
h
2
(
u
2
)
≡
h
2
(
x
2
,
y
21
)
≥
0
,
Θ
(
u
1
,
u
2
)
≡
y
12
−
y
21
=
0
,
min
J
u
1
,
u
2
≡
min
J
x
1
,
x
2
,
y
12
,
y
21
,
s.t.
g
1
u
1
≡
g
1
x
1
,
y
12
=
0
,
g
2
u
2
≡
g
2
x
2
,
y
21
=
0
,
h
1
u
1
≡
h
1
x
1
,
y
12
≥
0
,
h
2
u
2
≡
h
2
x
2
,
y
21
≥
0
,
Θ
u
1
,
u
2
≡
y
12
−
y
21
=
0
,
{:[min,J(u_(1),u_(2))-=min J(x_(1),x_(2),y_(12),y_(21))","],[" s.t. ",g_(1)(u_(1))-=g_(1)(x_(1),y_(12))=0","],[,g_(2)(u_(2))-=g_(2)(x_(2),y_(21))=0","],[,h_(1)(u_(1))-=h_(1)(x_(1),y_(12)) >= 0","],[,h_(2)(u_(2))-=h_(2)(x_(2),y_(21)) >= 0","],[,Theta(u_(1),u_(2))-=y_(12)-y_(21)=0","]:} \begin{array}{ll}
\min & J\left(u_{1}, u_{2}\right) \equiv \min J\left(x_{1}, x_{2}, y_{12}, y_{21}\right), \\
\text { s.t. } & g_{1}\left(u_{1}\right) \equiv g_{1}\left(x_{1}, y_{12}\right)=0, \\
& g_{2}\left(u_{2}\right) \equiv g_{2}\left(x_{2}, y_{21}\right)=0, \\
& h_{1}\left(u_{1}\right) \equiv h_{1}\left(x_{1}, y_{12}\right) \geq 0, \\
& h_{2}\left(u_{2}\right) \equiv h_{2}\left(x_{2}, y_{21}\right) \geq 0, \\
& \Theta\left(u_{1}, u_{2}\right) \equiv y_{12}-y_{21}=0,
\end{array}
其中
u
1
u
1
u_(1) u_{1} 和
u
2
u
2
u_(2) u_{2} 是
u
1
=
[
x
1
y
12
]
,
u
2
=
[
x
2
y
21
]
u
1
=
x
1
y
12
,
u
2
=
x
2
y
21
u_(1)=[[x_(1)],[y_(12)]],quadu_(2)=[[x_(2)],[y_(21)]] u_{1}=\left[\begin{array}{l}
x_{1} \\
y_{12}
\end{array}\right], \quad u_{2}=\left[\begin{array}{l}
x_{2} \\
y_{21}
\end{array}\right]
y
12
y
12
y_(12) y_{12} 是优化变量的
m
y
m
y
m_(y) m_{y} 向量,代表第一个子集
y
y
y y 中的重叠变量
u
1
,
y
21
u
1
,
y
21
u_(1),y_(21) u_{1}, y_{21} 是第二个子集
u
2
u
2
u_(2) u_{2} 中相同变量
y
y
y y 的
m
y
m
y
m_(y) m_{y} 向量,
Θ
(
u
1
,
u
2
)
Θ
u
1
,
u
2
Theta(u_(1),u_(2)) \Theta\left(u_{1}, u_{2}\right) 是一致性约束的
m
y
m
y
m_(y) m_{y} 向量函数。问题 (3) 的简洁写法是
min
u
1
∈
U
1
u
2
∈
U
2
J
(
u
1
,
u
2
)
,
s.t.
Θ
(
u
1
,
u
2
)
=
0
,
min
u
1
∈
U
1
u
2
∈
U
2
J
u
1
,
u
2
,
s.t.
Θ
u
1
,
u
2
=
0
,
{:[min_({:[u_(1)inU_(1)],[u_(2)inU_(2)]:}),J(u_(1),u_(2))","],[" s.t. ",Theta(u_(1),u_(2))=0","]:} \begin{array}{cl}
\min _{\substack{u_{1} \in U_{1} \\
u_{2} \in U_{2}}} & J\left(u_{1}, u_{2}\right), \\
\text { s.t. } & \Theta\left(u_{1}, u_{2}\right)=0,
\end{array}
其中
U
1
=
{
u
1
:
g
1
(
u
1
)
=
0
,
h
1
(
u
1
)
≥
0
}
,
U
2
=
{
u
2
:
g
2
(
u
2
)
=
0
,
h
2
(
u
2
)
≥
0
}
.
U
1
=
u
1
:
g
1
u
1
=
0
,
h
1
u
1
≥
0
,
U
2
=
u
2
:
g
2
u
2
=
0
,
h
2
u
2
≥
0
.
{:[U_(1)={u_(1):g_(1)(u_(1))=0,h_(1)(u_(1)) >= 0}","],[U_(2)={u_(2):g_(2)(u_(2))=0,h_(2)(u_(2)) >= 0}.]:} \begin{aligned}
U_{1} & =\left\{u_{1}: g_{1}\left(u_{1}\right)=0, h_{1}\left(u_{1}\right) \geq 0\right\}, \\
U_{2} & =\left\{u_{2}: g_{2}\left(u_{2}\right)=0, h_{2}\left(u_{2}\right) \geq 0\right\} .
\end{aligned}
在公式 (5) 中,公式 (3) 的可行性约束
{
g
i
,
h
i
}
,
i
=
1
,
2
g
i
,
h
i
,
i
=
1
,
2
{g_(i),h_(i)},i=1,2 \left\{g_{i}, h_{i}\right\}, i=1,2 被视为隐含在可行集
U
i
,
i
=
1
,
2
U
i
,
i
=
1
,
2
U_(i),i=1,2 U_{i}, i=1,2 中;唯一的显式约束
Θ
Θ
Theta \Theta 是表示重复变量一致性的等式,具有两级 APP 方法对显式等式约束问题所要求的简单形式(参考文献 1-2)。
在将可行性约束集划分为
n
n
n n 子集的一般情况下,问题 (5) 可以用以下形式表示
min
u
i
∈
U
i
i
=
1
,
…
,
n
J
(
u
1
,
…
,
u
n
)
,
s.t.
Θ
i
j
(
u
i
,
u
j
)
=
0
,
i
,
j
=
1
,
…
,
n
and
j
>
i
.
min
u
i
∈
U
i
i
=
1
,
…
,
n
J
u
1
,
…
,
u
n
,
s.t.
Θ
i
j
u
i
,
u
j
=
0
,
i
,
j
=
1
,
…
,
n
and
j
>
i
.
{:[min_({:[u_(i)inU_(i)],[i=1","dots","n]:}),J(u_(1),dots,u_(n))","],[" s.t. ",Theta_(ij)(u_(i),u_(j))=0","quad i","j=1","dots","n" and "j > i.]:} \begin{array}{cl}
\min _{\substack{u_{i} \in U_{i} \\
i=1, \ldots, n}} & J\left(u_{1}, \ldots, u_{n}\right), \\
\text { s.t. } & \Theta_{i j}\left(u_{i}, u_{j}\right)=0, \quad i, j=1, \ldots, n \text { and } j>i .
\end{array}
2.2.辅助问题原理(APP)。在 APP 中,考虑的是具有弱凸目标函数的问题 (7),并使用了增量拉格朗日法(参考文献 2)。将增量拉格朗日中任何不可分割的项线性化,从而得到一个近似值,该近似值对变量空间的任何分解都是可加的;添加严格凸项,得到辅助问题,其解可与原始问题的解相一致。有关 APP 的更多详情,请读者参阅参考文献 12。
根据 APP,问题(7)可以用以下两级迭代方案求解
[
⟨
⋅
,
⋅
⟩
[
⟨
⋅
,
⋅
⟩
[(:*,*:) [\langle\cdot, \cdot\rangle 代表标量积]:
min
u
i
∈
U
i
i
=
1
,
…
,
n
{
K
(
u
1
,
…
,
u
n
)
+
∑
i
=
1
n
⟨
ϵ
J
u
i
′
(
u
1
k
,
…
,
u
n
k
)
−
K
u
i
′
(
u
1
k
,
…
,
u
n
k
)
,
u
i
⟩
+
ϵ
∑
i
=
1
n
∑
j
=
i
+
1
n
⟨
p
i
j
k
+
c
Θ
i
j
(
u
i
k
,
u
j
k
)
,
Θ
i
j
(
u
i
,
u
j
)
⟩
}
⇒
u
1
k
+
1
,
…
,
u
n
k
+
1
,
p
i
j
k
+
1
=
p
i
j
k
+
ρ
Θ
i
j
(
u
i
k
+
1
,
u
j
k
+
1
)
,
i
,
j
=
1
,
…
,
n
and
j
>
i
.
min
u
i
∈
U
i
i
=
1
,
…
,
n
K
u
1
,
…
,
u
n
+
∑
i
=
1
n
ϵ
J
u
i
′
u
1
k
,
…
,
u
n
k
−
K
u
i
′
u
1
k
,
…
,
u
n
k
,
u
i
+
ϵ
∑
i
=
1
n
∑
j
=
i
+
1
n
p
i
j
k
+
c
Θ
i
j
u
i
k
,
u
j
k
,
Θ
i
j
u
i
,
u
j
⇒
u
1
k
+
1
,
…
,
u
n
k
+
1
,
p
i
j
k
+
1
=
p
i
j
k
+
ρ
Θ
i
j
u
i
k
+
1
,
u
j
k
+
1
,
i
,
j
=
1
,
…
,
n
and
j
>
i
.
{:[min_({:[u_(i)inU_(i)],[i=1","dots","n]:}){[K(u_(1),dots,u_(n))+sum_(i=1)^(n)(:epsilonJ_(u_(i))^(')(u_(1)^(k),dots,u_(n)^(k))-K_(u_(i))^(')(u_(1)^(k),dots,u_(n)^(k)),u_(i):)],[+epsilonsum_(i=1)^(n)sum_(j=i+1)^(n)(:p_(ij)^(k)+cTheta_(ij)(u_(i)^(k),u_(j)^(k)),Theta_(ij)(u_(i),u_(j)):)]}],[=>u_(1)^(k+1)","dots","u_(n)^(k+1)","],[p_(ij)^(k+1)=p_(ij)^(k)+rhoTheta_(ij)(u_(i)^(k+1),u_(j)^(k+1))","quad i","j=1","dots","n" and "j > i.]:} \begin{aligned}
& \min _{\substack{u_{i} \in U_{i} \\
i=1, \ldots, n}}\left\{\begin{array}{l}
K\left(u_{1}, \ldots, u_{n}\right)+\sum_{i=1}^{n}\left\langle\epsilon J_{u_{i}}^{\prime}\left(u_{1}^{k}, \ldots, u_{n}^{k}\right)-K_{u_{i}}^{\prime}\left(u_{1}^{k}, \ldots, u_{n}^{k}\right), u_{i}\right\rangle \\
+\epsilon \sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle p_{i j}^{k}+c \Theta_{i j}\left(u_{i}^{k}, u_{j}^{k}\right), \Theta_{i j}\left(u_{i}, u_{j}\right)\right\rangle
\end{array}\right\} \\
& \Rightarrow u_{1}^{k+1}, \ldots, u_{n}^{k+1}, \\
& p_{i j}^{k+1}=p_{i j}^{k}+\rho \Theta_{i j}\left(u_{i}^{k+1}, u_{j}^{k+1}\right), \quad i, j=1, \ldots, n \text { and } j>i .
\end{aligned}
这里,函数
K
(
u
1
,
…
,
u
n
)
K
u
1
,
…
,
u
n
K(u_(1),dots,u_(n)) K\left(u_{1}, \ldots, u_{n}\right) 是所谓的核心函数,
k
k
k k 是迭代计数器,
p
i
j
p
i
j
p_(ij) p_{i j} 是与重复变量的一致性约束
Θ
i
j
Θ
i
j
Theta_(ij) \Theta_{i j} 相关联的拉格朗日乘数向量。在第
k
k
k k 次迭代中,第一层(辅助)问题 (8a) 得到解决:注意,它没有明确的约束条件;由此得到的变量值用于第二层问题 ( 8 b ),在此得到拉格朗日乘数
p
i
j
p
i
j
p_(ij) p_{i j} 的新值。
迭代方案 (8) 的(全局)收敛性在以下条件下得到保证(参考文献 2):
U
i
,
i
=
1
,
…
,
n
U
i
,
i
=
1
,
…
,
n
U_(i),i=1,dots,n U_{i}, i=1, \ldots, n