论辅助问题原则的应用
摘要 辅助问题原理（APP）源于分解-协调方法的一般理论，为一级方法和两级方法建立了一个全面的框架。本文专门介绍了 APP 两级方法的成果，以便有效地应用于一些工程问题。
关键字优化算法、分解/协调方法、辅助问题原理。
1.导言 在并行/分布式计算环境中，可以有效地解决大规模优化问题。事实证明，去分区协调方法对利用这种环境非常有用；从这种方法衍生出的方法可分为单级或定点方法（子问题之间没有明确的协调行动）和双级方法（子问题通过在协调级更新的价格而得到解决）。
辅助问题原理（APP，参考文献 1-2）源自分解-协调方法的一般理论。它为单层和双层方法建立了一个全面的框架，并将许多已知算法作为特例纳入其中。在合理的假设条件下，APP 已经建立了收敛性证明，特别是对于两级方法。
利用众所周知的变量复制技术，总是可以得到一个优化问题，其可行性集可以很容易地分解为可行性子集的笛卡尔乘积，某些线性相等的情况除外。这样就很容易将问题分解成仅由线性相等关系耦合的子问题，这就是应用 APP 两级方法的完美候选方案。在某些应用中，例如电力系统的优化问题，会遇到一些变量重复出现的困难，这些变量总是以差分形式出现，我们把它们称为
Δ
Δ
Delta \Delta
Δ
Δ
Delta \Delta 本文将针对具有
Δ
Δ
Delta \Delta
Δ
Δ
Delta \Delta
Δ
Δ
Delta \Delta 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\}
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}
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 在将可行性约束集划分为
n
n
n n
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
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