内点法的基本思想
单纯形法从顶点到顶点搜索最优解- 当初始点远离最优解时- 需要很长的搜索代价X 而内点法在可行域内部进行搜索迭代的算法X 设当前点 x0 是可行集 D 的一个相对内点- 根据 优化问题笔记 中的引理 1.2.1，设 x ? ∈ D x^*\in\mathcal{D} x?∈D,那么 S F D ( x ? ) \mathbf{SFD}(x^*) SFD(x?) 是一个闭集，且当 x ? ∈ r i ( D ) x^*\in\mathbf{ri}(\mathcal{D}) x?∈ri(D) 时，有 V P ∩ ? B ( 0 , 1 ) ? F D ( x ? ) V_{\mathcal{P}}\cap\partial B(0,1)\subset\mathbf{FD}(x^*) VP?∩?B(0,1)?FD(x?),因而 c l ( F D ( x ? ) ) ? S F D ( x ? ) ? U ( x ? ) ∩ ? B ( 0 , 1 ) ? V D ∩ ? B ( 0 , 1 ) \mathbf{cl}(\mathbf{FD}(x^{*}))\subset\mathbf{SFD}(x^{*})\subset\mathbf{U}(x^{*})\cap\partial B(0,1)\subset V_{\mathcal{D}}\cap\partial B(0,1) cl(FD(x?))?SFD(x?)?U(x?)∩?B(0,1)?VD?∩?B(0,1)中四个集合均相等.
因此，只要能找到 d ∈ V D d ∈ V_\mathcal{D} d∈VD?，并且 d d d 还是一个目标函数 f ( x ) f(x) f(x) 的下降方向，即 ? f ( x 0 ) T d ≤ 0 ?f(x_0)^T d ≤ 0 ?f(x0?)Td≤0，就可以朝着方向 d d d 进行搜索.
对于线性规划 { min ? f ( x ) = c T x + d s . t . A x = b , x ? 0 , \begin{cases}&\min f(x)=c^Tx+d\\ &\mathrm{s.t.}Ax=b,\\&x\succeq0,&\end{cases} ? ? ???minf(x)=cTx+ds.t.Ax=b,x?0,??,有 f ( x ) = c T x f(x)=c^Tx f(x)=cTx,因而 ? f ( x ) = c \nabla f(x)=c ?f(x)=c. 显然方向 ? c -c ?c 是 f f f 下降最快的方向.但它不一定是可行方向，为此，将方向 ? c -c ?c 投影到线性子空间 V D V_\mathcal{D} VD? 上，设该正交投影算子为： P : R n → V D . \begin{aligned}P:\mathbb{R}^n\to V_{\mathcal{D}}.\end{aligned} P:Rn→VD?.?那么有 ? f ( x 0 ) T P ( ? c ) = ? c T P c = ? c T P T P c = ∥ P c ∥ 2 2 ≤ 0. \nabla f(x_0)^TP(-c)=-c^TPc=-c^TP^TPc=\|Pc\|_2^2\leq0. ?f(x0?)TP(?c)=?cTPc=?cTPTPc=∥Pc∥22?≤0.这说明 P ( ? c ) P(-c) P(?c) 仍是下降方向，它同时又是可行方向，因而可以进行如下的迭代 x 0 → x 0 ? δ P c 使得 x 0 ? δ P c . \begin{aligned}x_0\to x_0-\delta Pc&&&\text{使得}&&x_0\succeq\delta Pc.\end{aligned} x0?→x0??δPc???使得??x0??δPc.? 进行上述的迭代首先需要找到初始点 $x_0，然后计算出 P c Pc Pc. 特别地，如果 P c = 0 Pc=0 Pc=0，则有 c ⊥ n u l l ( A ) c\perp\mathbf{null}(A) c⊥null(A),从而， ? d ∈ n u l l ( A ) \forall d\in\mathbf{null}(A) ?d∈null(A),有 c T d = 0 c^Td=0 cTd=0.这意味着朝着任意使得 x + δ d ∈ D x+\delta d\in\mathcal{D} x+δd∈D 的方向 d d d, 目标函数均不再下降.
等式约束凸优化问题的一般形式是 { min ? f ( x ) s . t A x = b , \begin{cases}\min f(x)\\\mathrm{s.t}\quad Ax=b,&\end{cases} {minf(x)s.tAx=b,??其中 A ∈ R m × n , b ∈ R m , f : R n → R A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m,f:\mathbb{R}^n\to\mathbb{R} A∈Rm×n,b∈Rm,f:Rn→R 是凸函数.对此类问题，当可行集不为空集时，Slater 条件成立，因而满足强对偶性.
其可行集为 D : = x ∈ R n ∣ A x = b \mathcal{D} := {x ∈ \mathbb{R}^n|Ax = b} D:=x∈Rn∣Ax=b 求解等式约束优化问题的典型方法是将约束优化问题化为无约束优化问题.
求解上述最优化问题的最自然的方法是所谓解空间变量法，其过程如下所示：
(4.1.1) 先求 A x = b Ax=b Ax=b 的一个特解 x 0 ; x_0; x0?;
(4.1.2) 然后求齐次线性方程组 A x = 0 Ax=0 Ax=0 的解空间 null(A) 的一组基，以其为列向量构成
矩阵 B B B,那么 D = { x 0 + B z ∣ z ∈ R n ? r } 其中 r : = r a n k ( A ) . \mathcal{D}=\{x_0+Bz|z\in\mathbb{R}^{n-r}\}\quad\text{其中}\quad r:=\mathbf{rank}(A). D={x0?+Bz∣z∈Rn?r}其中r:=rank(A).
(4.1.3) 求解无约束优化问题 min ? z ∈ R n ? r f ( x 0 + B z ) \min_{z\in\mathbb{R}^{n-r}}f(x_0+Bz) z∈Rn?rmin?f(x0?+Bz)得 z ? z^* z?, 由此获得等式凸优化问题 { min ? f ( x ) s . t A x = b , \begin{cases}\min f(x)\\\mathrm{s.t}\quad Ax=b,&\end{cases} {minf(x)s.tAx=b,??的解 x ? : = x 0 + B z ? . x^*:=x_0+Bz^*. x?:=x0?+Bz?.
注：求 x 0 x_{0} x0? 以及计算解空间矩阵 B B B 均可通过常规的 LU 分解或 QR 分解来实现.
对等式凸优化问题 { min ? f ( x ) s . t A x = b , \begin{cases}\min f(x)\\\mathrm{s.t}\quad Ax=b,&\end{cases} {minf(x)s.tAx=b,??当 D ≠ ? \mathcal{D} \ne ? D=? 时，Slater 条件成立，从而强对偶性成立，并且对偶问题可解.
该优化问题可以通过 对偶问题笔记(1) 中的 算法 2.1化为无约束优化问题 min ? x ∈ R n ( f ( x ) + ν ? T A x ) \min_{x\in\mathbb{R}^n}\left(f(x)+\nu^{*T}Ax\right) x∈Rnmin?(f(x)+ν?TAx)来求解，其中 ν ? ∈ R m ν^? ∈ \mathbb{R}^m ν?∈Rm 是对偶问题 max ? g ( ν ) , g ( ν ) : = inf ? x ∈ R n [ f ( x ) + ν ( A x ? b ) ] \max g(\nu),\quad g(\nu):=\inf_{x\in\mathbb{R}^n}[f(x)+\nu(Ax-b)] maxg(ν),g(ν):=x∈Rninf?[f(x)+ν(Ax?b)]的解，当然当上述对偶问题是容易求解时，这个方法才是比较可行的.
当目标函数
f
f
f 在
R
n
\mathbb{R}_n
Rn? 上可微时，根据强对偶性条件下的 KKT 条件的推论：设
(
λ
?
,
μ
?
)
∈
R
p
×
R
q
,
x
?
∈
r
i
(
Ω
)
(\lambda^*,\mu^*)\in\mathbb{R}^p\times\mathbb{R}^q, x^*\in\mathbf{ri}(\Omega)
(λ?,μ?)∈Rp×Rq,x?∈ri(Ω),且
{
f
i
}
i
=
0
p
\{f_i\}_{i=0}^p
{fi?}i=0p? 和
{
h
j
}
j
=
1
q
\{h_j\}_{j=1}^q
{hj?}j=1q? 均在
x
?
x^*
x? 处可微，那么，
L
(
x
?
,
λ
?
,
μ
?
)
=
inf
?
x
∈
Ω
L
(
x
,
λ
?
,
μ
?
)
L(x^*,\lambda^*,\mu^*)=\inf_{x\in\Omega}L(x,\lambda^*,\mu^*)
L(x?,λ?,μ?)=x∈Ωinf?L(x,λ?,μ?)蕴含
?
x
L
(
x
?
,
λ
?
,
μ
?
)
⊥
V
Ω
.
\nabla_xL(x^*,\lambda^*,\mu^*)\perp V_\Omega.
?x?L(x?,λ?,μ?)⊥VΩ?.可知
x
?
x^?
x? 是等式优化问题的解当且仅当存在
ν
?
∈
R
m
ν^? ∈ \mathbf{R}^m
ν?∈Rm，使得
A
x
?
=
b
,
?
f
(
x
?
)
+
A
T
ν
?
=
0.
\begin{align}Ax^*=b,\quad\nabla f(x^*)+A^T\nu^*=0.\end{align}
Ax?=b,?f(x?)+ATν?=0.??
这是一个含有 n + m n + m n+m 个未知量 ( x ? , ν ? ) (x^?, ν^?) (x?,ν?)， n + m n + m n+m 个方程的方程组，该等价条件可直接由优化问题笔记中下例
设
A
∈
R
m
×
n
,
b
∈
R
m
A\in\mathbb{R}^{m\times n},\quad b\in\mathbb{R}^m
A∈Rm×n,b∈Rm 使得集合
{
x
∈
R
n
∣
A
x
=
b
}
\{x\in\mathbb{R}^n|Ax=b\}
{x∈Rn∣Ax=b} 非空. 又设函数
f
:
R
n
→
R
f:\mathbb{R}^n\to\mathbb{R}
f:Rn→R 是可微的凸函数.那么，
x
?
∈
R
n
x^*\in\mathbb{R}^n
x?∈Rn 是等式约束凸优化问题
{
min
?
f
(
x
)
s
.
t
A
x
=
b
\begin{cases}\min f(x)\\\mathrm{s.t}\quad Ax=b\end{cases}
{minf(x)s.tAx=b?的解当且仅当
?
f
(
x
?
)
∈
r
a
n
(
A
T
)
,
A
x
?
=
b
.
\nabla f(x^*)\in\mathbf{ran}(A^T),\quad Ax^*=b.
?f(x?)∈ran(AT),Ax?=b.推出.并且方程的前一部分是
m
m
m 个线性方程组，而后一部分当
?
f
(
x
)
?f(x)
?f(x) 是非线性函数时是难于计算的.
当 f ( x ) f(x) f(x) 是二次凸函数时， ? f ( x ) ?f(x) ?f(x) 是线性的，此时根据(1)即 x ? x^? x? 是等式凸优化问题 { min ? f ( x ) s . t A x = b \begin{cases}\min f(x)\\\mathrm{s.t}\quad Ax=b\end{cases} {minf(x)s.tAx=b?的解当且仅当存在 ν ? ∈ R m ν^? ∈ \mathbf{R}^m ν?∈Rm，使得 A x ? = b , ? f ( x ? ) + A T ν ? = 0. Ax^*=b,\quad\nabla f(x^*)+A^T\nu^*=0. Ax?=b,?f(x?)+ATν?=0.优化问题可以通过求解如下 m + n m + n m+n 阶线性方程组而求得精确解.
命题 5.1 设
A
∈
R
m
×
n
,
b
∈
R
m
,
G
∈
S
+
n
,
q
∈
R
n
,
r
∈
R
A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m,G\in\mathbb{S}_+^n,\quad q\in\mathbb{R}^n,\quad r\in\mathbb{R}
A∈Rm×n,b∈Rm,G∈S+n?,q∈Rn,r∈R. 那么
x
?
∈
R
n
x^*\in\mathbb{R}^n
x?∈Rn 是等式约束二次凸规划问题
{
min
?
f
(
x
)
=
1
2
x
T
G
x
+
q
T
x
+
r
s.t
A
x
=
b
\begin{align} \begin{cases}\min f(x)=\frac12x^TGx+q^Tx+r\\\text{s.t}\quad Ax=b\end{cases}\end{align}
{minf(x)=21?xTGx+qTx+rs.tAx=b???的解当且仅当存在
ν
?
∈
R
m
\nu^*\in\mathbb{R}^m
ν?∈Rm,使得
[
G
A
T
A
0
]
[
x
?
ν
?
]
=
[
?
q
b
]
.
\begin{align}\begin{bmatrix}G&A^T\\A&0\end{bmatrix}\begin{bmatrix}x^*\\\nu^*\end{bmatrix}=\begin{bmatrix}-q\\b\end{bmatrix}.\end{align}
[GA?AT0?][x?ν??]=[?qb?].??
证. 因为
?
f
(
x
)
=
G
x
+
q
?f(x) = Gx + q
?f(x)=Gx+q 代入(1)，整理便得(3).
注： 称(3)为优化问题(2)的 EEh 系统，而称(3)的系数矩阵为(2)的
KKT 矩阵，下面给出该矩阵非奇异的一个条件.
命题 5.2 设 A ∈ R m × n A\in\mathbb{R}^{m\times n} A∈Rm×n 是行满秩的，那么上述 K K T KKT KKT 矩阵非奇异当且仅当 n u l l ( G ) ∩ n u l l ( A ) = { 0 } null(G) \cap null( A)=\{ 0\} null(G)∩null(A)={0}.
证.若 n u l l ( G ) ∩ n u l l ( A ) ≠ { 0 } null(G) \cap null( A)\neq\{ 0\} null(G)∩null(A)={0},则存在 x ≠ 0 x\neq0 x=0.使得 A x = 0 Ax=0 Ax=0 且 G x = 0 Gx=0 Gx=0,从而 [ G A T A 0 ] [ x 0 ] = 0. \begin{bmatrix}G&A^T\\[0.3em]A&0\end{bmatrix}\begin{bmatrix}x\\[0.3em]0\end{bmatrix}=0. [GA?AT0?][x0?]=0.所以 KKT 矩阵是奇异的.
反之，设 KKT 矩阵是奇异的，则存在 ( x T , y T ) T ≠ 0 (x^T,y^T)^T\neq0 (xT,yT)T=0, 使得 [ G A T A 0 ] [ x y ] = 0. \begin{bmatrix}G&A^T\\[0.3em]A&0\end{bmatrix}\begin{bmatrix}x\\[0.3em]y\end{bmatrix}=0. [GA?AT0?][xy?]=0.即 G x + A T y = 0 , A x = 0. Gx+A^Ty=0,\quad Ax=0. Gx+ATy=0,Ax=0.
上述第一式左乘 x T x^T xT 可以得到 x T G x + x T A y = 0 x^TGx+x^TAy=0 xTGx+xTAy=0，并利用第二式 A x = 0 Ax=0 Ax=0,则 x T A = 0 x^TA=0 xTA=0，可得： x T G x = ? x T A T y = 0 x^TGx=-x^TA^Ty=0 xTGx=?xTATy=0. 由于 G G G 是对称半正定矩阵，故 G x = 0 Gx=0 Gx=0.再代入第一式，得 A T y = 0 A^Ty=0 ATy=0, 由于 A T A^T AT 是列满秩的，故 y = 0 y=0 y=0. (这是因为 如果 A x = 0 Ax=0 Ax=0，且 A A A的列向量组线性无关，则 A x = 0 Ax=0 Ax=0 只有零解.)从而 x ≠ 0 x\neq0 x=0,且 A x = G x = 0 Ax=Gx=0 Ax=Gx=0.这说明 n u l l ( G ) ∩ n u l l ( A ) ≠ { 0 } . \mathbf{null}(G)\cap\mathbf{null}(A)\neq\{0\}. null(G)∩null(A)={0}.
设
f
:
R
n
→
R
f:\mathbb{R}^n\to\mathbb{R}
f:Rn→R 是二次可微的凸函数，则
?
2
f
(
x
)
\nabla^2f(x)
?2f(x) 半正定. 我们从可行集
D
:
=
{
x
∈
\mathcal{D}:=\{x\in
D:={x∈
R
n
∣
A
x
=
b
}
\mathbb{R}^n|Ax=b\}
Rn∣Ax=b} 中取–个初始点
x
0
x_0
x0?,做二次 Taylor 近似：
f
(
x
0
+
d
)
≈
f
~
(
x
0
+
d
)
:
=
f
(
x
0
)
+
?
f
(
x
0
)
T
d
+
1
2
d
T
?
2
f
(
x
0
)
d
.
\begin{aligned}f(x_0+d)\approx\tilde{f}(x_0+d):=f(x_0)+\nabla f(x_0)^Td+\frac{1}{2}d^T\nabla^2f(x_0)d.\end{aligned}
f(x0?+d)≈f~?(x0?+d):=f(x0?)+?f(x0?)Td+21?dT?2f(x0?)d.?然后求解等式约束二次凸规划问题
min
?
d
∈
R
n
f
~
(
x
0
+
d
)
?
s
.
t
?
A
(
x
0
+
d
)
=
b
.
\min_{d\in\mathbb{R}^n}\tilde{f}(x_0+d)\quad\mathrm{~s.t~}\quad A(x_0+d)=b.
d∈Rnmin?f~?(x0?+d)?s.t?A(x0?+d)=b.据命题 5.1可知
d
0
∈
R
n
d_0 ∈ \mathbb{R}^n
d0?∈Rn 是该问题的解当且仅当存在
ν
0
∈
R
m
ν_0 ∈ \mathbb{R}_m
ν0?∈Rm?，使得
[
?
2
f
(
x
0
)
A
T
A
0
]
[
d
0
ν
0
]
=
[
?
?
f
(
x
0
)
0
]
.
\begin{align}\begin{bmatrix}\nabla^2f(x_0)&A^T\\A&0\end{bmatrix}\begin{bmatrix}d_0\\\nu_0\end{bmatrix}=\begin{bmatrix}-\nabla f(x_0)\\0\end{bmatrix}.\end{align}
[?2f(x0?)A?AT0?][d0?ν0??]=[??f(x0?)0?].??
假设对任意的
x
∈
R
n
x\in\mathbb{R}^n
x∈Rn,有
{
z
∈
R
n
∣
?
2
f
(
x
)
z
=
A
z
=
0
}
=
{
0
}
\{z\in\mathbb{R}^n|\nabla^2f(x)z=Az=0\}=\{0\}
{z∈Rn∣?2f(x)z=Az=0}={0}, 那么 KKT 矩阵
[
?
2
f
(
x
0
)
A
T
A
0
]
\begin{aligned}\begin{bmatrix}\nabla^2f(x_0)&A^T\\A&0\end{bmatrix}\end{aligned}
[?2f(x0?)A?AT0?]?
是非奇异的. 于是(4)存在唯一解
d
0
,
ν
0
.
d_0,\nu_0.
d0?,ν0?. 令
x
1
:
=
x
0
+
d
0
x_1:=x_0+d_0
x1?:=x0?+d0?
重复上述步骤直至满足停止条件便可求得等式凸优化问题
{
min
?
f
(
x
)
s
.
t
A
x
=
b
\begin{cases}\min f(x)\\\mathrm{s.t}\quad Ax=b\end{cases}
{minf(x)s.tAx=b?的解的近似解，而这一方法称为求解等式约束凸优化问题的 Newton法，称上述
d
0
d_0
d0? 为 Newton方向.
由(4)可知
?
2
f
(
x
0
)
d
0
+
A
T
ν
0
=
?
?
f
(
x
0
)
,
?
A
d
0
=
0
\nabla^2f(x_0)d_0+A^T\nu_0=-\nabla f(x_0),\:Ad_0=0
?2f(x0?)d0?+ATν0?=??f(x0?),Ad0?=0.所以
?
δ
>
0
\forall\delta>0
?δ>0, 有
A
(
x
0
+
δ
d
0
)
=
A
x
0
=
b
,
?
f
(
x
0
)
T
d
0
=
?
d
0
T
?
2
f
(
x
0
)
d
0
≤
0.
A(x_0+\delta d_0)=Ax_0=b,\quad\nabla f(x_0)^Td_0=-d_0^T\nabla^2f(x_0)d_0\leq0.
A(x0?+δd0?)=Ax0?=b,?f(x0?)Td0?=?d0T??2f(x0?)d0?≤0.第一式说明
x
0
+
δ
d
0
∈
D
x_0+\delta d_0\in\mathcal{D}
x0?+δd0?∈D,即
d
0
d_0
d0? 是可行方向. 第二式说明，它是下降方向.