5.7 約束優(yōu)化最優(yōu)性理論應(yīng)用實(shí)例
5.7.1 仿射空間的投影問題
考慮優(yōu)化問題
min
?
x
∈
R
n
1
2
∣
∣
x
?
y
∣
∣
2
2
,
s
.
t
.
A
x
=
b
\min_{x{\in}R^n}\frac{1}{2}||x-y||_2^2,\\ s.t.{\quad}Ax=b
x∈Rnmin?21?∣∣x?y∣∣22?,s.t.Ax=b
其中
A
∈
R
m
×
n
,
b
∈
R
m
,
y
∈
R
n
A{\in}R^{m \times n},b{\in}R^m,y{\in}R^n
A∈Rm×n,b∈Rm,y∈Rn為給定的矩陣和向量，這里不妨設(shè)矩陣A是行滿秩的，這個問題可以看成仿射平面
{
x
∈
R
n
∣
A
x
=
b
}
\{x{\in}R^n|Ax=b\}
{x∈Rn∣Ax=b}的投影問題
對于等式約束，我們引入拉格朗日乘子
λ
∈
R
m
\lambda{\in}R^m
λ∈Rm，構(gòu)造拉格朗日函數(shù)
L
(
x
,
λ
)
=
1
2
∣
∣
x
?
y
∣
∣
2
+
λ
T
(
A
x
?
b
)
L(x,\lambda)=\frac{1}{2}||x-y||^2+\lambda^T(Ax-b)
L(x,λ)=21?∣∣x?y∣∣2+λT(Ax?b)
因?yàn)橹挥蟹律浼s束，估
S
l
a
t
e
r
Slater
Slater條件滿足，
x
?
x^*
x?為一個全局最優(yōu)解，當(dāng)且僅當(dāng)存在
λ
?
∈
R
m
\lambda^*{\in}R^m
λ?∈Rm使得
{
x
?
?
y
+
A
T
λ
=
0
A
x
?
=
b
\left\{ \begin{matrix} x^*-y+A^T\lambda=0\\ Ax^*=b \\ \end{matrix} \right.
{x??y+ATλ=0Ax?=b?
由上述KKT條件第一式，等號左右兩邊同時左乘
A
A
A可得
A
x
?
?
A
y
+
A
A
T
λ
=
0
Ax^*-Ay+AA^T\lambda=0
Ax??Ay+AATλ=0
注意到
A
x
?
=
b
Ax^*=b
Ax?=b以及
A
A
T
AA^T
AAT是可逆矩陣，因此可以解出乘子
λ
=
(
A
A
T
)
?
1
(
A
y
?
b
)
\lambda=(AA^T)^{-1}(Ay-b)
λ=(AAT)?1(Ay?b)
代入回去可以得到
x
?
=
y
?
A
T
(
A
A
T
)
?
1
(
A
y
?
b
)
x^*=y-A^T(AA^T)^{-1}(Ay-b)
x?=y?AT(AAT)?1(Ay?b)
5.7.2 線性規(guī)劃問題
考慮線性規(guī)劃問題
min
?
x
∈
R
n
c
T
x
,
s
.
t
.
A
x
=
b
,
x
≥
0
(5.7.1)
\min_{x{\in}R^n}{\quad}c^Tx,\\ s.t.{\quad}Ax=b,\\ x{\ge}0\tag{5.7.1}
x∈Rnmin?cTx,s.t.Ax=b,x≥0(5.7.1)
其中
A
∈
R
m
×
n
,
b
∈
R
m
,
c
∈
R
n
A{\in}R^{m \times n},b{\in}R^m,c{\in}R^n
A∈Rm×n,b∈Rm,c∈Rn分別為給定的矩陣和向量
拉格朗日函數(shù)可以寫為
L
(
x
,
s
,
v
)
=
c
T
x
+
v
T
(
A
x
?
b
)
?
s
T
x
=
?
b
T
v
+
(
A
T
v
?
s
+
c
)
T
x
,
s
≥
0
L(x,s,v)=c^Tx+v^T(Ax-b)-s^Tx\\ =-b^Tv+(A^Tv-s+c)^Tx,s{\ge}0
L(x,s,v)=cTx+vT(Ax?b)?sTx=?bTv+(ATv?s+c)Tx,s≥0
其中
s
∈
R
n
,
v
∈
R
m
s{\in}R^n,v{\in}R^m
s∈Rn,v∈Rm，由于線性規(guī)劃是凸問題且滿足
S
l
a
t
e
r
Slater
Slater條件的，因此對于任意一個全局最優(yōu)解
x
?
x^*
x?，我們有如下KKT條件
{
c
+
A
T
v
?
?
s
?
=
0
,
A
x
?
=
b
x
?
≥
0
s
?
≥
0
s
?
x
?
=
0
(5.7.2)
\left\{ \begin{matrix} c+A^Tv^*-s^*=0,\\ Ax^*=b \\ x^*{\ge}0\\ s^*{\ge}0\\ s^*x^*=0 \end{matrix} \right.\tag{5.7.2}
?
?
??c+ATv??s?=0,Ax?=bx?≥0s?≥0s?x?=0?(5.7.2)
我們設(shè)原始問題和對偶問題最優(yōu)解函數(shù)值分別為
p
?
p^*
p?和
d
?
d^*
d?，則根據(jù)
p
?
p^*
p?取值情況，有如下三種可能
（1）如果
?
∞
<
p
?
<
+
∞
(
有界
)
-\infty<p^*<+\infty(有界)
?∞<p?<+∞(有界)，那么原始問題可行而且存在最優(yōu)解，由
S
l
a
t
e
r
Slater
Slater條件知強(qiáng)對偶原理成立，因此有
d
?
=
p
?
d^*=p^*
d?=p?，即對偶問題也是可行的且存在最優(yōu)解
（2）如果
p
?
=
?
∞
p^*=-\infty
p?=?∞，那么原始問題可行，但目標(biāo)函數(shù)值無下界，由弱對偶原理知
d
?
≤
p
?
=
?
∞
d^*{\le}p^*=-\infty
d?≤p?=?∞，即
d
?
=
?
∞
d^*=-\infty
d?=?∞，因?yàn)閷ε紗栴}是對目標(biāo)函數(shù)極大化，所以此時對偶問題不可行
（3）如果
p
?
=
+
∞
p^*=+\infty
p?=+∞，那么原始問題無可行解，注意到
S
l
a
t
e
r
Slater
Slater條件對原始問題不成立，此時對偶問題既可能是函數(shù)值無界（
d
?
=
+
∞
d^*=+\infty
d?=+∞）也可能無可行解（
d
?
=
?
∞
d^*=-\infty
d?=?∞），我們說，不可能出現(xiàn)
?
∞
<
d
?
<
+
∞
-\infty<d^*<+\infty
?∞<d?<+∞的情形，這是因?yàn)槿绻麑ε紗栴}可行且存在最優(yōu)解，那么可對對偶問題應(yīng)用強(qiáng)對偶原理，進(jìn)而導(dǎo)出原始問題也存在最優(yōu)解，這矛盾了
5.7.3 基追蹤
min
?
x
∈
R
n
∣
∣
x
∣
∣
1
,
s
.
t
.
A
x
=
b
(5.7.3)
\min_{x{\in}R^n}||x||_1,\\ s.t.{\quad}Ax=b\tag{5.7.3}
x∈Rnmin?∣∣x∣∣1?,s.t.Ax=b(5.7.3)
利用分解
x
i
=
x
i
+
?
x
i
?
x_i=x_i^+-x_i^-
xi?=xi+??xi??，其中
x
i
+
=
m
a
x
{
x
i
,
0
}
,
x
i
?
=
max
?
{
?
x
i
,
0
}
x_i^+=max\{x_i,0\},x_i^-=\max\{-x_i,0\}
xi+?=max{xi?,0},xi??=max{?xi?,0}分別表示
x
x
x的正部和負(fù)部，問題5.7.3的一種等價形式可以寫成
min
?
∑
i
x
i
+
+
x
i
?
,
s
.
t
.
A
x
+
?
A
x
?
=
b
,
x
+
,
x
?
≥
0
\min{\sum_i}x_i^++x_i^-,\\ s.t.{\quad}Ax^+-Ax^-=b,\\ x^+,x^-{\ge}0
mini∑?xi+?+xi??,s.t.Ax+?Ax?=b,x+,x?≥0
進(jìn)一步的，令
y
=
[
x
i
+
,
x
i
?
]
T
∈
R
2
n
y=[x_i^+,x_i^-]^T{\in}R^{2n}
y=[xi+?,xi??]T∈R2n，我們將問題5.7.3轉(zhuǎn)化為如下線性規(guī)劃問題
min
?
y
∈
R
2
n
1
T
y
,
s
.
t
.
[
A
,
?
A
]
y
=
b
,
y
≥
0
\min_{y{\in}R^{2n}}1^Ty,\\ s.t.{\quad}[A,-A]y=b,\\ y{\ge}0
y∈R2nmin?1Ty,s.t.[A,?A]y=b,y≥0
其中
1
=
(
1
,
1
,
?
?
,
1
)
T
∈
R
2
n
1=(1,1,\cdots,1)^T{\in}R^{2n}
1=(1,1,?,1)T∈R2n
那么根據(jù)一般線性規(guī)劃的最優(yōu)性條件，等價于求解
{
1
+
[
A
,
?
A
]
T
v
?
?
s
?
=
0
,
[
A
,
?
A
]
y
?
=
b
y
?
≥
0
s
?
≥
0
s
?
y
?
=
0
(5.7.4)
\left\{ \begin{matrix} 1+[A,-A]^Tv^*-s^*=0,\\ [A,-A]y^*=b \\ y^*{\ge}0\\ s^*{\ge}0\\ s^*y^*=0 \end{matrix} \right.\tag{5.7.4}
?
?
??1+[A,?A]Tv??s?=0,[A,?A]y?=by?≥0s?≥0s?y?=0?(5.7.4)
同樣的，我們也可以直接推導(dǎo)5.7.3的最優(yōu)性條件，拉格朗日函數(shù)為
L
(
x
,
v
)
=
∣
∣
x
∣
∣
1
+
v
T
(
A
x
?
b
)
L(x,v)=||x||_1+v^T(Ax-b)
L(x,v)=∣∣x∣∣1?+vT(Ax?b)
x
?
x^*
x?為全局最優(yōu)解當(dāng)且僅當(dāng)存在
v
?
∈
R
m
v^*{\in}R^m
v?∈Rm使得
{
0
∈
?
∣
∣
x
?
∣
∣
1
+
A
T
v
?
,
A
x
?
=
b
(5.7.5)
\left\{ \begin{matrix} 0{\in}\partial||x^*||_1+A^Tv^*,\\ Ax^*=b \\ \end{matrix} \right.\tag{5.7.5}
{0∈?∣∣x?∣∣1?+ATv?,Ax?=b?(5.7.5)
最優(yōu)性條件5.7.4和5.7.5本質(zhì)上是等價的文章來源：http://www.zghlxwxcb.cn/news/detail-722677.html
5.7.4 最大割問題的半定規(guī)劃松弛以及非凸分解模型
第三章說明了最大割問題的半定規(guī)劃松弛問題。如下
max
?
<
C
,
X
>
,
s
.
t
.
X
i
i
=
1
,
i
=
1
,
2
,
?
?
,
n
,
X
?
0
(5.7.6)
\max{\quad}<C,X>,\\ s.t.{\quad}X_{ii}=1,i=1,2,\cdots,n,\\ X{\succeq}0\tag{5.7.6}
max<C,X>,s.t.Xii?=1,i=1,2,?,n,X?0(5.7.6)
該問題是一個凸優(yōu)化問題，并且Slater約束品性成立，對于等式約束，我們引入拉格朗日乘子
μ
i
R
,
i
=
1
,
2
,
?
?
,
n
\mu_{i}R,i=1,2,\cdots,n
μi?R,i=1,2,?,n；對于半正定約束，根據(jù)對偶錐，我們引入拉格朗日乘子
Λ
∈
S
+
n
\Lambda{\in}\mathcal{S}_+^n
Λ∈S+n?，拉格朗日函數(shù)為
L
(
X
,
μ
,
Λ
)
=
<
C
,
X
>
+
∑
i
=
1
n
μ
i
(
X
i
i
?
1
)
?
T
r
(
X
Λ
)
L(X,\mu,\Lambda)=<C,X>+\sum_{i=1}^n\mu_i(X_{ii}-1)-Tr(X\Lambda)
L(X,μ,Λ)=<C,X>+i=1∑n?μi?(Xii??1)?Tr(XΛ)
根據(jù)約束優(yōu)化問題的最優(yōu)性條件
{
C
+
D
i
a
g
(
u
?
)
?
Λ
?
=
0
,
X
i
i
?
=
1
X
?
≥
0
Λ
?
≥
0
T
r
(
X
?
Λ
?
)
=
0
\left\{ \begin{matrix} C+Diag(u^*)-\Lambda^*=0,\\ X_{ii}^*=1 \\ X^*{\ge}0\\ \Lambda^*{\ge}0\\ Tr(X^*\Lambda^*)=0 \end{matrix} \right.
?
?
??C+Diag(u?)?Λ?=0,Xii??=1X?≥0Λ?≥0Tr(X?Λ?)=0?
這個轉(zhuǎn)化成跡就是因?yàn)?span id="n5n3t3z" class="katex--inline">
X
和
Λ
X和\Lambda
X和Λ的半正定性，上述條件
T
r
(
X
?
Λ
?
)
=
0
Tr(X^*\Lambda^*)=0
Tr(X?Λ?)=0可以等價地用
X
?
Λ
?
X^*\Lambda^*
X?Λ?代替
下面的非凸分解模型還沒看明白。。。以后有機(jī)會回來補(bǔ)文章來源地址http://www.zghlxwxcb.cn/news/detail-722677.html
到了這里，關(guān)于最優(yōu)化：建模、算法與理論（最優(yōu)性理論2的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
