Zoutendijk可行方向法
文章目录
1 基本问题
Zoutendijk可行性方法属于约束优化问题可行方向法中的一种。与之前无约束优化问题中的最速下降法、牛顿法相像。可行方向法:从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点，直到满足终止条件，得到最优解 x ∗ x^* x∗.
基 本 思 想 ： \large\color{#70f3ff}{\boxed{\color{brown}{基本思想：} }} 基本思想：
在给定一个可行点 x k x^k xk之后，用某种方法确定一个改进的可行方向 d k d^k dk,然后沿方向 d k d^k dk，求解一个有约束的线搜索问题,得极小点 x k + 1 x^{k+1} xk+1，令
x
k
+
1
=
x
k
+
α
k
d
k
(*)
x^{k+1}=x^{k}+\alpha_k d^k \tag{*}
xk+1=xk+αkdk(*)
如果仍不是最优解,则重复上述步骤.
不同的可行方向法的主要区别在于，选择可行方向的策略不同,大体上可以分为三类:
- 用求解一个 KaTeX parse error: Undefined control sequence: \bbox at position 1: \̲b̲b̲o̲x̲[cyan,2pt]{线性规划… 问题来确定,如Zoutendjk方法,Frank-Wolfe方法和Topkis-Veinott方法等;
- 利用KaTeX parse error: Undefined control sequence: \bbox at position 1: \̲b̲b̲o̲x̲[cyan,2pt]{投影矩阵…来直接构造一个改进的可行方向,如Rosen的梯度投影法和Rosen-Polak方法等;
- 利用KaTeX parse error: Undefined control sequence: \bbox at position 1: \̲b̲b̲o̲x̲[cyan,2pt]{既约梯度…,直接构造一个改进的可行方向,如Wolfe的既约梯度法及其各种改进,凸单纯形法.
可行方向法是通过直接处理约束问题，得到一个下降可行方向，从而产生一个收敛于线性约束优化问题的K-T点。一般地，求解约束优化问题要比求解无约束优化问题复杂、困难，因为在求解过程中，不仅要使目标函数值单调下降，而且还要保证迭代点满足约束条件。因此，在求解过程中，要求产生的迭代点的搜索方向为下降可行方向。由于这时的约束为线性函数，因而可通过利用线性代数的知识和无约束优化方法来设计一些有效算法。
2 线性约束情形
考虑线性约束问题
( P ) min f ( x ) s.t. A x ≥ b E x = e x ∈ R n (1) \begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\\text{s.t.} &~ ~ ~ Ax \geq b\\ &~ ~ ~ Ex = e\\ &~ ~ ~x ∈ R^n \end{aligned}\tag{1} (P) mins.t. f(x) Ax≥b Ex=e x∈Rn(1)
(1)利用起作用约束构造可行下降方向
定 理 1 \large\color{magenta}{\boxed{\color{brown}{定理1} }} 定理1设 x x x是问题 ( P ) (P) (P)的可行解,在点 x x x处有 A 1 x = b 1 , A 2 x > b 2 A_1x = b_1,A_2x >b_2 A1x=b1,A2x>b2,其中
A
=
[
A
1
A
2
]
,
b
=
[
b
1
b
2
]
A=\begin{bmatrix} A_1\\ A_2 \end{bmatrix}, b=\begin{bmatrix} b_1\\ b_2 \end{bmatrix}
A=[A1A2],b=[b1b2]
则非零向量
d
d
d为
x
x
x处的可行方向的充要条件是
A 1 d ≥ 0 , E d = 0 (2) A_1d≥0~~,~~ Ed =0\tag2 A1d≥0 , Ed=0(2)
【证明】必要性 设非零向量
d
d
d 是
x
ˉ
\bar{x}
xˉ 处的可行方向, 则存在
δ
>
0
,
\delta>\mathbf{0},
δ>0, 使得对任意
的
α
∈
(
0
,
δ
)
,
x
ˉ
+
α
d
\alpha \in(\mathbf{0}, \delta), \bar{x}+\alpha d
α∈(0,δ),xˉ+αd 仍是可行解。即
A
(
x
ˉ
+
α
d
)
≥
b
,
E
(
x
ˉ
+
α
d
)
=
e
A(\bar{x}+\alpha d) \geq b, E(\bar{x}+\alpha d)=e
A(xˉ+αd)≥b,E(xˉ+αd)=e
A
(
x
ˉ
+
α
d
)
=
(
A
1
A
2
)
(
x
ˉ
+
α
d
)
=
(
b
1
+
α
A
1
d
A
2
x
ˉ
+
α
A
2
d
)
≥
(
b
1
b
2
)
A(\bar{x}+\alpha d)=\left(\begin{array}{l}A_{1} \\ A_{2}\end{array} \right)(\bar{x}+\alpha d)=\left(\begin{array}{c}b_{1}+\alpha A_{1} d \\ A_{2} \bar{x}+\alpha A_{2} d\end{array}\right) \geq \left(\begin{array}{l}b_{1} \\ b_{2}\end{array}\right)
A(xˉ+αd)=(A1A2)(xˉ+αd)=(b1+αA1dA2xˉ+αA2d)≥(b1b2)
充分性同理可证
因为
α
>
0
,
\alpha >0,
α>0, 所以
A
1
d
≥
0.
A_{1} d \geq 0 .
A1d≥0. 而
E
(
x
ˉ
+
α
d
)
=
e
+
α
E
d
=
e
,
E(\bar{x}+\alpha d)=e+\alpha E d=e,
E(xˉ+αd)=e+αEd=e, 故
E
d
=
0.
E d=0 .
Ed=0.KaTeX parse error: Undefined control sequence: \bbox at position 1: \̲b̲b̲o̲x̲[cyan,2pt]{~~}
(1)根据无约束问题的KKT条件
∇
f
(
x
)
−
A
T
u
−
E
T
v
=
0
u
T
(
A
x
−
b
)
=
0
u
≥
0
A
x
≥
b
E
x
=
e
.
\begin{array}{ll} \nabla f(x)-A^{T} u-E^{T} v=0 & \\ u^{T}(A x-b)=0 \\ u \geq 0 & \quad \\ A x \geq b & \\ E x=e . & \end{array}
∇f(x)−ATu−ETv=0uT(Ax−b)=0u≥0Ax≥bEx=e.
可得
$$
\nabla f(x)-A_{1}^{T} u_{1}-E^{T} v=0 \
\quad u_{1} \geq 0, u_{2}=0\
\
A_{1} x=b_{1}, A_{2} x>b_{2}\
E x=e
KaTeX parse error: Can't use function '$' in math mode at position 2: $̲\large\color{#7…
∇f(x)^T d < 0,A_1d≥0~~,~~ Ed =0\tag3
$$
则d是x处的可行下降方向.
由（2）可以将求解（P）转化为求解线性规划问题：
(
P
S
)
min
∇
f
(
x
)
T
d
s.t.
A
1
d
≥
0
E
d
=
0
−
1
≤
d
j
≤
1
,
j
=
1
,
.
.
.
,
n
\begin{aligned} (PS) ~ ~ ~ \min &~ ~ ~ ∇f(x)^T d\\\text{s.t.} &~ ~ ~ A_1d≥0\\ &~ ~ ~ Ed =0\\ &~ ~ ~-1 \leq d_j \leq 1,j=1,...,n\end{aligned}
(PS) mins.t. ∇f(x)Td A1d≥0 Ed=0 −1≤dj≤1,j=1,...,n
其中为了能获得有限最优解,限制了方向
d
d
d的长度,即增加规范约束条件
−
1
≤
d
j
≤
1
,
j
=
1
,
.
.
.
,
n
-1 \leq d_j \leq 1,j=1,...,n
−1≤dj≤1,j=1,...,n
因 d = 0 d=0 d=0是问题(PS)的可行解,故目标函数的最优值必定小于或等于0.
定 理 2 \large\color{magenta}{\boxed{\color{brown}{定理2} }} 定理2设x是§的一个可行解，则 x x x是§的KKT点当且仅当(PS)目标函数的最优值为零,
- 若 ∇ f ( x ) T d < 0 ∇f(x)^T d < 0 ∇f(x)Td<0,则 d d d是问题§在x处的可行下降方向;
- 若 ∇ f ( x ) T d = 0 ∇f(x)^T d = 0 ∇f(x)Td=0,则 x x x是KKT点.
(2)确定一维搜索步长
在KaTeX parse error: \tag works only in display equations式的迭代中，为保证后继迭代点的可行性,考虑求解
(
P
α
)
min
f
(
x
k
+
α
d
k
)
s.t.
A
(
x
k
+
α
d
k
)
≥
b
E
(
x
k
+
α
d
k
)
=
e
α
≥
0
(4)
\begin{aligned} (P\alpha) ~ ~ ~ \min &~ ~ ~ f(x^{k}+\alpha d^k)\\\text{s.t.} &~ ~ ~ A(x^{k}+\alpha d^k)≥b\\ &~ ~ ~ E(x^{k}+\alpha d^k) =e\\ &~ ~ ~\alpha \geq 0\end{aligned}\tag 4
(Pα) mins.t. f(xk+αdk) A(xk+αdk)≥b E(xk+αdk)=e α≥0(4)
(4)中
E
(
x
k
+
α
d
k
)
=
e
E(x^{k}+\alpha d^k) =e
E(xk+αdk)=e 可去除，因为
d
k
d^{k}
dk 是可行下降方向，故
E
d
k
=
0
,
E d^{k}=0,
Edk=0, 即约束条件
E
(
x
k
+
α
d
k
)
=
E
x
k
+
α
E
d
k
=
E
x
k
=
e
E\left(x^{k}+\alpha d^{k}\right)=E x^{k}+\alpha E d^{k}=E x^{k}=e
E(xk+αdk)=Exk+αEdk=Exk=e
总是成立。
设在点
x
k
x^{k}
xk 处有
A
1
x
k
=
b
1
,
A
2
x
k
>
b
2
,
A_{1} x^{k}=b_{1}, A_{2} x^{k}>b_{2},
A1xk=b1,A2xk>b2, 其中
A
=
(
A
1
A
2
)
,
b
=
(
b
1
b
2
)
A=\left(\begin{array}{l} A_{1} \\ A_{2} \end{array}\right), b=\left(\begin{array}{l} b_{1} \\ b_{2} \end{array}\right)
A=(A1A2),b=(b1b2)
则约束条件
A
(
x
k
+
α
d
k
)
≥
b
A\left(x^{k}+\alpha d^{k}\right) \geq b
A(xk+αdk)≥b 可改写为
(
A
1
(
x
k
+
α
d
k
)
A
2
(
x
k
+
α
d
k
)
)
≥
(
b
1
b
2
)
\left(\begin{array}{l}A_{1}\left(x^{k}+\alpha d^{k}\right) \\ A_{2}\left(x^{k}+\alpha d^{k}\right)\end{array}\right) \geq\left(\begin{array}{l}b_{1} \\ b_{2}\end{array}\right)
(A1(xk+αdk)A2(xk+αdk))≥(b1b2),
d
d
d 是可行方向
⇔
A
1
d
≥
0
,
E
d
=
0
\Leftrightarrow A_{1} d \geq 0, E d=0
⇔A1d≥0,Ed=0
因为
d
k
d^{k}
dk 是可行下降方向,所以
A
1
d
k
≥
0
,
A_{1} d^{k} \geq 0,
A1dk≥0, 又
A
1
x
k
=
b
1
,
α
≥
0
A_{1} x^{k}=b_{1}, \alpha \geq 0
A1xk=b1,α≥0,
故不等式约束
A
1
(
x
k
+
α
d
k
)
≥
b
1
A_{1}\left(x^{k}+\alpha d^{k}\right) \geq b_{1}
A1(xk+αdk)≥b1 自然成立。
利用可行方向条件与起作用约束简化
(
P
α
)
(P\alpha)
(Pα),即
(
P
α
)
(P\alpha)
(Pα)满足
E
x
k
=
e
,
E
d
k
=
0
,
A
1
x
k
=
b
1
,
A
1
d
k
≥
0
,
A
2
x
k
>
b
2
Ex^k= e , Ed^k= 0, A_1x^k = b_1, A_1d^k≥0,~A_2x^k >b_2
Exk=e,Edk=0,A1xk=b1,A1dk≥0, A2xk>b2
化简为
$$
\begin{aligned} (P\alpha) ~ ~ ~ \min &~ ~ ~ f(x^{k}+\alpha d^k)\\text{s.t.} &~ ~ ~ A_2x^{k}+ \alpha A_2 d^k ≥b_2\
&~ ~ ~\alpha \geq 0\end{aligned}\tag 5
$$
$A_2x^{k}+ \alpha A_2 d^k ≥b_2 \rightarrow $ $ ~~~~ \alpha A_2 d^k ≥b_2-A_2x^{k}
,
令
, 令
,令\hat{b} =b_2-A_2x^{k} ,~~ \hat{d}= A_2 d^k$ .由于
A
2
x
>
b
2
A_2x >b_2
A2x>b2则
b
^
<
0
\hat{b}<0
b^<0.
化简为
$$
\begin{aligned} (P\alpha) ~ ~ ~ \min &~ ~ ~ f(x^{k}+\alpha d^k)\\text{s.t.} &~ ~ ~ \alpha \hat{d} ≥\hat{b}\
&~ ~ ~\alpha \geq 0\end{aligned}\tag 6
$$
分两种情况讨论(6):
(1)在
d
^
≥
0
\hat{d}≥0
d^≥0,这时对于
α
≥
0
\alpha \geq 0
α≥0,
α
d
^
≥
b
^
\alpha \hat{d} ≥\hat{b}
αd^≥b^式总成立;
(2)
d
^
≱
0
\hat{d}\ngeqslant0
d^0,这时
d
^
\hat{d}
d^至少有一个分量
d
i
^
<
0
\hat{d_i}<0
di^<0对于
α
≥
0
\alpha \geq 0
α≥0,使
α
d
^
≥
b
^
\alpha \hat{d} ≥\hat{b}
αd^≥b^式成立的
α
\alpha
α的上限为
m
i
n
{
b
i
^
d
i
^
,
d
i
^
<
0
}
min\left\{ \frac{\hat{b_i}}{\hat{d_i}}, \hat{d_i}<0\right\}
min{di^bi^,di^<0}
记
$$
\alpha_{max} = \left{\begin{matrix}
min\left{ \frac{\hat{b_i}}{\hat{d_i}}, \hat{d_i}<0\right} ,&当 \hat{d}\ngeqslant0\ +\infty ，&当\hat{d}≥0
\end{matrix}\right.
于
是
精
确
线
搜
索
为
:
于是精确线搜索为:
于是精确线搜索为:
\begin{aligned} (P\alpha_{max}) ~ ~ ~ \min &~ ~ ~ f(x^{k}+\alpha d^k)\\text{s.t.} &~ ~ ~
0\leq \alpha \leq \alpha_{max} \end{aligned}\tag 7
$$
算法步骤
-
选定初始容许点 x 0 x^{0} x0；允许误差 ε \varepsilon ε ,置 k = 0 k=0 k=0 。
-
把 A A A 分解为 A 1 , A 2 A_1,A_2 A1,A2，相应地把 b b b分解为 b 1 , b 2 b_1,b_2 b1,b2 ，使得 A 1 x k = b 1 , A 2 x k > b 2 A_1x^k = b_1,A_2x^k >b_2 A1xk=b1,A2xk>b2 ,求 ∇ f ( x k ) ∇f(x^k) ∇f(xk)。
-
求解线性规划问题：
( P S ) min ∇ f ( x k ) T d s.t. A 1 d ≥ 0 E d = 0 − 1 ≤ d j ≤ 1 , j = 1 , . . . , n \begin{aligned} (PS) ~ ~ ~ \min &~ ~ ~ ∇f(x^k)^T d\\\text{s.t.} &~ ~ ~ A_1d≥0\\ &~ ~ ~ Ed =0\\ &~ ~ ~-1 \leq d_j \leq 1,j=1,...,n\end{aligned} (PS) mins.t. ∇f(xk)Td A1d≥0 Ed=0 −1≤dj≤1,j=1,...,n
得最优解 d k d^k dk -
若 ∣ ∇ f ( x k ) T d k ∣ < ε |\nabla f(x_{k})^{T}d^{k}| < \varepsilon ∣∇f(xk)Tdk∣<ε，则输出 x k x_{k} xk ，停止迭代；否则，计算 b ^ = b 2 − A 2 x k , d ^ = A 2 d k \hat{b} =b_2-A_2x^{k} ,~~ \hat{d}= A_2 d^k b^=b2−A2xk, d^=A2dk 。
-
精确线搜索：
$$
\begin{aligned} (P\alpha_{max}) ~ ~ ~ \min &~ ~ ~ f(x^{k}+\alpha d^k)\\text{s.t.} &~ ~ ~0\leq \alpha \leq \alpha_{max} \end{aligned}
$$
得步长 α k \alpha _k αk. -
令 x k + 1 = x k + α k d k x^{k+1}=x^{k}+\alpha_kd^k xk+1=xk+αkdk , k = k + 1 ~~~k=k+1 k=k+1 ，转2。
例
用Zoutendijk可行方向法解下列优化问题
取初始可行点 x 1 = ( 0 , 0 ) T x^1 =(0,0)^T x1=(0,0)T.
【解】将原问题化为
s.t.
−
2
x
1
+
x
2
≥
−
1
−
x
1
−
x
2
≥
−
2
x
1
≥
0
x
2
≥
0
\begin{aligned} \text{s.t.} ~ ~ ~ -2x_1+x_2 &\geq -1 \\ ~ ~ ~ -x_1-x_2 &\geq -2 \\ ~ ~ ~ x_1 &\geq 0 \\ ~ ~ ~ x_2 &\geq 0 \\ \end{aligned}
s.t. −2x1+x2 −x1−x2 x1 x2≥−1≥−2≥0≥0
第一次迭代:
$$
∇f(x)=\begin{pmatrix}2x_1-2
\ 2x_2-4
\end{pmatrix},
A=\begin{bmatrix}
-2 & 1\
-1 & -1\
1 & 0\
0 & 1
\end{bmatrix},b=\begin{bmatrix}
-1\
-2\
0\
0
\end{bmatrix}
KaTeX parse error: Can't use function '$' in math mode at position 3: 在$̲x^1 =(0,0)^T$处寻…
A_1^1=\begin{bmatrix}
1 & 0\
0 & 1\end{bmatrix},
b_1^1=\begin{bmatrix}
0\0 \end{bmatrix}
A_2^1=\begin{bmatrix}
-2 & 1\
-1 & -1\\end{bmatrix},
b_2^1=\begin{bmatrix}
-1\
-2\\end{bmatrix}
$$
$$
∇f(x^1)=\begin{pmatrix}-2
\ -4
\end{pmatrix}
$$
(1)求解线性规划问题：
min
−
2
d
1
−
4
d
2
s.t.
d
1
≥
0
d
2
≥
0
−
1
≤
d
1
≤
1
−
1
≤
d
2
≤
1
\begin{aligned} ~ ~ ~ \min &~ ~ ~ -2 d_1 -4d_2\\\text{s.t.} &~ ~ ~ d_1≥0\\ &~ ~ ~ d_2≥0\\ &~ ~ ~-1 \leq d_1 \leq 1\\ &~ ~ ~-1 \leq d_2 \leq 1 \end{aligned}
mins.t. −2d1−4d2 d1≥0 d2≥0 −1≤d1≤1 −1≤d2≤1
由图解法求得最优解 d 1 = ( 1 , 1 ) T d^1 = (1,1)^T d1=(1,1)T
(2)精确线搜索：
计算 b ^ = b 2 − A 2 x 1 = [ − 1 − 2 ] − [ − 2 1 − 1 − 1 ] [ 0 0 ] = [ − 1 − 2 ] , d ^ = A 2 d 1 = [ − 2 1 − 1 − 1 ] [ 1 1 ] = [ − 1 − 2 ] \hat{b} =b_2-A_2x^{1} = \begin{bmatrix} -1\\ -2\\\end{bmatrix}- \begin{bmatrix} -2 & 1\\ -1 & -1\\\end{bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix} =\begin{bmatrix} -1\\-2 \end{bmatrix} ,~~ \hat{d}= A_2 d^1=\begin{bmatrix} -2 & 1\\ -1 & -1\\\end{bmatrix}\begin{bmatrix} 1\\1 \end{bmatrix} =\begin{bmatrix} -1\\-2 \end{bmatrix} b^=b2−A2x1=[−1−2]−[−2−11−1][00]=[−1−2], d^=A2d1=[−2−11−1][11]=[−1−2]
由于
d
^
≱
0
\hat{d}\ngeqslant0
d^0，计算
α
m
a
x
=
m
i
n
{
−
1
−
1
,
−
2
−
2
}
=
1
\alpha_{max} = min\left\{ \frac{{-1}}{{-1}},\frac{{-2}}{{-2}}\right\} =1
αmax=min{−1−1,−2−2}=1
而
x
1
+
α
d
1
=
(
0
0
)
+
α
(
1
1
)
=
(
α
α
)
x^{1}+\alpha d^1=\begin{pmatrix}0 \\ 0 \end{pmatrix} +\alpha \begin{pmatrix}1 \\ 1 \end{pmatrix} =\begin{pmatrix}\alpha \\\alpha \end{pmatrix}
x1+αd1=(00)+α(11)=(αα)
$$
\begin{aligned} (P\alpha_{max}) ~ ~ ~ \min &~ ~ ~ f(x^{1}+\alpha d1)=2\alpha2 -6\alpha+6\\text{s.t.} &~ ~ ~
0\leq \alpha \leq 1 \end{aligned}
$$
令$f(x^{1}+\alpha d^1)’=0, 0\leq \alpha \leq 1 $解得
α
1
=
1
\alpha_1=1
α1=1.
令$x{2}=x{1}+\alpha_1d^1=\begin{pmatrix}1
\ 1 \end{pmatrix} $
第二次迭代:
在
x
2
=
(
1
,
1
)
T
x^2 =(1,1)^T
x2=(1,1)T处寻找满足分解
A
A
A的子矩阵：
A
1
2
=
[
−
2
1
−
1
−
1
]
,
b
1
2
=
[
−
1
−
2
]
A
2
2
=
[
1
0
0
1
]
,
b
2
2
=
[
0
0
]
A_1^2=\begin{bmatrix} -2 & 1\\ -1 & -1\\\end{bmatrix}, b_1^2=\begin{bmatrix} -1\\ -2\\\end{bmatrix} A_2^2=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix}, b_2^2=\begin{bmatrix} 0\\0 \end{bmatrix}
A12=[−2−11−1],b12=[−1−2]A22=[1001],b22=[00]
$$
∇f(x^2)=\begin{pmatrix}0
\ -2
\end{pmatrix}
$$
(1)求解线性规划问题：
min
−
2
d
2
s.t.
−
2
d
1
+
d
2
≥
0
−
d
1
−
d
2
≥
0
−
1
≤
d
1
≤
1
−
1
≤
d
2
≤
1
\begin{aligned} ~ ~ ~ \min &~ ~ ~ -2d_2\\\text{s.t.} &~ ~ ~ -2d_1+d_2≥0\\ &~ ~ ~ -d_1-d_2≥0\\ &~ ~ ~-1 \leq d_1 \leq 1\\ &~ ~ ~-1 \leq d_2 \leq 1 \end{aligned}
mins.t. −2d2 −2d1+d2≥0 −d1−d2≥0 −1≤d1≤1 −1≤d2≤1
由图解法求得最优解 d 2 = ( − 1 , 1 ) T d^2 = (-1,1)^T d2=(−1,1)T
(2)精确线搜索：
计算
b
^
=
b
2
−
A
2
x
2
=
[
0
0
]
−
[
1
0
0
1
]
[
1
1
]
=
[
−
1
−
1
]
,
d
^
=
A
2
d
2
=
[
1
0
0
1
]
[
−
1
1
]
=
[
−
1
1
]
\hat{b} =b_2-A_2x^{2} = \begin{bmatrix} 0\\ 0\\\end{bmatrix}- \begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix}\begin{bmatrix} 1\\1 \end{bmatrix} =\begin{bmatrix} -1\\-1 \end{bmatrix} ,~~ \hat{d}= A_2 d^2=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix}\begin{bmatrix} -1\\1 \end{bmatrix} =\begin{bmatrix} -1\\1 \end{bmatrix}
b^=b2−A2x2=[00]−[1001][11]=[−1−1], d^=A2d2=[1001][−11]=[−11]
由于
d
^
≱
0
\hat{d}\ngeqslant0
d^0，计算
α
m
a
x
=
m
i
n
{
−
1
−
1
}
=
1
\alpha_{max} = min\left\{ \frac{{-1}}{{-1}}\right\} =1
αmax=min{−1−1}=1
而
x
2
+
α
d
2
=
(
1
1
)
+
α
(
−
1
1
)
=
(
1
−
α
1
+
α
)
x^{2}+\alpha d^2=\begin{pmatrix}1 \\ 1 \end{pmatrix} +\alpha \begin{pmatrix}-1 \\ 1 \end{pmatrix} =\begin{pmatrix}1-\alpha \\1+\alpha \end{pmatrix}
x2+αd2=(11)+α(−11)=(1−α1+α)
$$
\begin{aligned} (P\alpha_{max}) ~ ~ ~ \min &~ ~ ~ f(x^{1}+\alpha d1)=2\alpha2 -2\alpha+2\\text{s.t.} &~ ~ ~
0\leq \alpha \leq 1 \end{aligned}
$$
令$f(x^{1}+\alpha d^1)’=0, 0\leq \alpha \leq 1 $解得
α
2
=
1
2
\alpha_2=\frac{1}{2}
α2=21.
令$x{3}=x{2}+\alpha_2d^2=\begin{pmatrix}\frac{1}{2}
\ \frac{3}{2} \end{pmatrix} $
第三次迭代:
在$x^3
处
寻
找
满
足
分
解
处寻找满足分解
处寻找满足分解A$的子矩阵：
$$
A_1^3=\begin{bmatrix}
-1 & -1\\end{bmatrix},
b_1^3=\begin{bmatrix}
-2\\end{bmatrix}
A_2^3=\begin{bmatrix}-2 & 1\
1 & 0\
0 & 1\end{bmatrix},
b_2^3=\begin{bmatrix} -1\
0\0 \end{bmatrix}
$$
$$
∇f(x^3)=\begin{pmatrix}-1
\ -1
\end{pmatrix}
$$
(1)求解线性规划问题：
min
−
d
1
−
d
2
s.t.
−
d
1
−
d
2
≥
0
−
1
≤
d
1
≤
1
−
1
≤
d
2
≤
1
\begin{aligned} ~ ~ ~ \min &~ ~ ~ -d_1-d_2\\\text{s.t.} &~ ~ ~ -d_1-d_2≥0\\ &~ ~ ~-1 \leq d_1 \leq 1\\ &~ ~ ~-1 \leq d_2 \leq 1 \end{aligned}
mins.t. −d1−d2 −d1−d2≥0 −1≤d1≤1 −1≤d2≤1
由图解法求得最优解
d
3
=
(
0
,
0
)
T
d^3 = (0,0)^T
d3=(0,0)T
此时 ∇ f ( x ) T d = 0 ∇f(x)^T d = 0 ∇f(x)Td=0.所以由 定 理 2 \large\color{magenta}{\boxed{\color{brown}{定理2} }} 定理2知$x^3 是 原 问 题 的 K K T 点 . 又 因 为 原 问 题 是 凸 规 划 , 所 以 是原问题的KKT点.又因为原问题是凸规划,所以 是原问题的KKT点.又因为原问题是凸规划,所以x^3 是 原 问 题 的 最 优 解 。 最 优 值 为 是原问题的最优解。最优值为 是原问题的最优解。最优值为f(x^3) = \frac{3}{2}$.
3 非线性约束情形
考虑不等式约束问题
(
P
)
min
f
(
x
)
s.t.
g
i
(
x
)
≥
0
,
i
=
1
,
…
,
m
x
∈
R
n
(8)
\begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\\text{s.t.} &~ ~ ~ g_i(x) \geq 0, i = 1,~ \ldots, m\\ &~ ~ ~x ∈ R^n \end{aligned}\tag 8
(P) mins.t. f(x) gi(x)≥0,i=1, …,m x∈Rn(8)
(1)利用起作用约束构造可行下降方向
定
理
\large\color{magenta}{\boxed{\color{brown}{定理} }}
定理设
x
x
x是问题(8)的可行解,点
x
x
x处起作用约束的指标集记作
I
(
x
)
=
{
i
∣
g
i
(
x
)
=
0
,
i
=
1
,
…
,
m
}
I(x )=\{ i| g_i(x)= 0, i = 1,~ \ldots, m\}
I(x)={i∣gi(x)=0,i=1, …,m}
设目标函数和
g
i
(
x
)
(
i
∈
I
)
g_{i}(x)(i \in I)
gi(x)(i∈I) 在
x
x
x 点可 微，
g
i
(
x
)
(
i
∉
I
)
g_{i}(x)(i \notin I)
gi(x)(i∈/I) 在
x
x
x 点连续,点
x
x
x处的可行下降方向
d
d
d满足:
{
∇
f
(
x
)
T
d
<
0
∇
g
i
(
x
)
T
d
>
0
,
i
∈
I
(
x
)
(9)
\left\{\begin{matrix} &~∇f(x)^T d < 0 \\ &~∇g_i(x)^T d > 0,i \in I(x) \end{matrix}\right.\tag9
{ ∇f(x)Td<0 ∇gi(x)Td>0,i∈I(x)(9)
问题(8)化简为线性规划问题：
min
z
s.t.
∇
f
(
x
)
T
d
−
z
≤
0
∇
g
i
(
x
)
T
d
+
z
≥
0
,
i
∈
I
(
x
)
−
1
≤
d
j
≤
1
,
j
=
1
,
.
.
.
,
n
(10)
\begin{aligned} \min &~ ~ ~ z\\\text{s.t.} &~ ~ ~ ∇f(x)^T d -z \leq 0 \\ &~ ~ ~ ∇g_i(x)^T d +z\geq 0 ,i \in I(x)\\ &~ ~ ~-1 \leq d_j \leq 1,j=1,...,n \end{aligned}\tag {10}
mins.t. z ∇f(x)Td−z≤0 ∇gi(x)Td+z≥0,i∈I(x) −1≤dj≤1,j=1,...,n(10)
定
理
3
\large\color{magenta}{\boxed{\color{brown}{定理3} }}
定理3设问题(10)的最优解为
(
z
ˉ
,
d
ˉ
)
(\bar{z}, \bar{d})
(zˉ,dˉ)有下述两种情况:
- (1)若 z ˉ < 0 \bar{z}<0 zˉ<0,则 d ˉ \bar{d} dˉ为 x x x处的可行下降方向;
- (2)若 z ˉ = 0 \bar{z}=0 zˉ=0,则 x x x是Fritz John 点.
(2)确定一维搜索步长
为保证后继迭代点的可行性,考虑求解
$$
\begin{aligned} \min &~ ~ ~ f(x_{k}+\alpha d_k)\\text{s.t.} &~ ~ ~
0\leq \alpha \leq \alpha_{max} \end{aligned}\tag {11}
$$
其中KaTeX parse error: \tag works only in display equations
算法步骤
-
选定初始容许点$ x_{0} ； 允 许 误 差 ；允许误差 ；允许误差 \varepsilon$ ,置 k = 0 k=0 k=0 。
-
确定起作用约束.确定点$ x_{k} $处起作用约束的指标集
I ( x k ) = { i ∣ g i ( x k ) = 0 , i = 1 , … , m } I(x_{k} )=\{ i| g_i(x_{k})= 0, i = 1,~ \ldots, m\} I(xk)={i∣gi(xk)=0,i=1, …,m}
-
求解线性规划问题：
min z s.t. ∇ f ( x k ) T d − z ≤ 0 ∇ g i ( x k ) T d + z ≥ 0 , i ∈ I ( x k ) − 1 ≤ d j ≤ 1 , j = 1 , . . . , n \begin{aligned} \min &~ ~ ~ z\\\text{s.t.} &~ ~ ~ ∇f(x_{k})^T d -z \leq 0 \\ &~ ~ ~ ∇g_i(x_{k})^T d +z\geq 0 ,i \in I(x_{k})\\ &~ ~ ~-1 \leq d_j \leq 1,j=1,...,n \end{aligned} mins.t. z ∇f(xk)Td−z≤0 ∇gi(xk)Td+z≥0,i∈I(xk) −1≤dj≤1,j=1,...,n
得最优解 ( z k , d k ) (z_k,d_k) (zk,dk) -
若 $ |z_k| < \varepsilon $，则输出 x k x_{k} xk ，停止迭代；否则，得到可行下降方向 d k d_k dk，进行5
-
精确线搜索：
$$
\begin{aligned} \min &~ ~ ~ f(x_{k}+\alpha d_k)\\text{s.t.} &~ ~ ~0\leq \alpha \leq \alpha_{max} \end{aligned}
$$
得步长 α k \alpha _k αk. -
令$x_{k+1}=x_{k}+\alpha_kd_k $ , k = k + 1 ~~~k=k+1 k=k+1 ，转2。
Zoutendijk可行方向法特点
特点:1）可行方向法是用梯度去求解约束优化设计问题的一种有代表性的直接搜索方法。
2）收敛速度快，效果较好，但程序比较复杂。使用条件:适用于大中型约束优化设计问题的求解。
缺点:
由于Zoutendijk可行方向法是基于无约束优化中的最速下降法,所以此算法具有最速下降法的一些缺点。以非典型的缺点就是“锯齿现象”，从而，当迭代逼近非有效约束边界时可能会发生一些突然的变化，使得收敛速度很慢，甚至不收敛于K-T点.
Zoutendijk法的改进问题的提出
对于线性和非线性不等式约束问题,前面我们仅使用起作用约束来确定搜索方向．当某迭代点在一个约束的边界上时，如果可行方向取得不恰当，那么沿该方向可能因接近另一个约束边界而只能作一个微小的移动，否则,就会使迭代点跑出边界．为防止这一现象发生,设想在约束条件的边界上设立一道“安全带”，迭代点进入“安全带”时，只允许它往可行域内部移动,而不许向边界靠近.为此引入起作用约束的概念,即在构造可行方向时，既把通过当前迭代点的约束边界看作起作用约束，也把充分接近当前这代点的边界约束考虑在内.
4 Zoutendijk法的改进
(1) ε \varepsilon ε起作用约束可行方向法
定 义 \large\color{magenta}{\boxed{\color{brown}{定义} }} 定义对于给定的 ε k > 0 \varepsilon_k >0 εk>0,称 I ε k ( x k ) = { i ∣ 0 ≤ g i ( x k ) ≤ ε k , i = 1 , … , m } I_{\varepsilon_k}(x_{k} )=\{ i| 0 \leq g_i(x_{k})\leq \varepsilon_k, i = 1,~ \ldots, m\} Iεk(xk)={i∣0≤gi(xk)≤εk,i=1, …,m}为点$ x_{k} 处 的 处的 处的\varepsilon_k 起作用$约束的指标集
算 法 步 骤 \large\color{#70f3ff}{\boxed{\color{brown}{算法步骤} }} 算法步骤
-
选定初始容许点$ x_{0} ； 允 许 误 差 ；允许误差 ；允许误差 \varepsilon$ ,置 k = 0 k=0 k=0 。
-
确定起作用约束.确定点$ x_{k} 处 起 作 用 约 束 的 指 标 集 处起作用约束的指标集 处起作用约束的指标集I_{\varepsilon_k}(x_{k} )={ i| 0 \leq g_i(x_{k})\leq \varepsilon_k, i = 1,~ \ldots, m}$
-
求解线性规划问题：
min z s.t. ∇ f ( x k ) T d − z ≤ 0 ∇ g i ( x k ) T d + z ≥ 0 , i ∈ I ( x k ) − 1 ≤ d j ≤ 1 , j = 1 , . . . , n \begin{aligned} \min &~ ~ ~ z\\\text{s.t.} &~ ~ ~ ∇f(x_{k})^T d -z \leq 0 \\ &~ ~ ~ ∇g_i(x_{k})^T d +z\geq 0 ,i \in I(x_{k})\\ &~ ~ ~-1 \leq d_j \leq 1,j=1,...,n \end{aligned} mins.t. z ∇f(xk)Td−z≤0 ∇gi(xk)Td+z≥0,i∈I(xk) −1≤dj≤1,j=1,...,n
得最优解 ( z k , d k ) (z_k,d_k) (zk,dk) -
若 $ |z_k| < \varepsilon $，则输出 x k x_{k} xk ，停止迭代；否则，得到可行下降方向 d k d_k dk，进行5
-
精确线搜索：
$$
\begin{aligned} \min &~ ~ ~ f(x_{k}+\alpha d_k)\\text{s.t.} &~ ~ ~0\leq \alpha \leq \alpha_{max} \end{aligned}
$$
得步长 α k \alpha _k αk. -
令$x_{k+1}=x_{k}+\alpha_kd_k $ , k = k + 1 ~~~k=k+1 k=k+1 ，转2。
Frank-Wolfe 方法
给定线性规划问题
min
f
(
x
)
s.t.
{
A
x
=
b
x
≥
0
\min f(x)\\ \text {s.t.}\left\{\begin{array}{c} A x=b \\ x \geq 0 \end{array}\right.
minf(x)s.t.{Ax=bx≥0
其中
A
A
A 是
m
×
n
m \times n
m×n 矩阵，秩为
m
,
b
m, b
m,b 是
m
m
m 维列向量,
f
(
x
)
f(x)
f(x) 是可微函数,
x
∈
R
n
⋅
x \in R^{n} \cdot
x∈Rn⋅ 令
D
=
{
x
∣
A
x
=
b
,
x
≥
0
}
,
D=\{x \mid A x=b, x \geq 0\},
D={x∣Ax=b,x≥0}, 称
D
D
D 为可行域。
算法思想:在每次迭代中, 将目标函数
f
(
x
)
f(x)
f(x) 线性化，通过 求解线性规划方法求得可行下降方向, 并沿该方向在可行 域内进行一维搜索。
设已知可行点
x
k
,
x^{k},
xk, 则有
f
(
x
)
≈
f
(
x
k
)
+
∇
f
(
x
k
)
T
(
x
−
x
k
)
=
∇
f
(
x
k
)
T
x
+
[
f
(
x
k
)
−
∇
f
(
x
k
)
T
x
k
]
f(x) \approx f\left(x^{k}\right)+\nabla f\left(x^{k}\right)^{T}\left(x-x^{k}\right)\\ =\nabla f\left(x^{k}\right)^{T} x+\left[f\left(x^{k}\right)-\nabla f\left(x^{k}\right)^{T} x^{k}\right]
f(x)≈f(xk)+∇f(xk)T(x−xk)=∇f(xk)Tx+[f(xk)−∇f(xk)Txk]
求解线性规划
min
∇
f
(
x
k
)
T
x
s.t.
x
∈
D
\begin{array}{ll} \min & \nabla f\left(x^{k}\right)^{T} x \\ \text {s.t.} & x \in D \end{array}
mins.t.∇f(xk)Txx∈D
定
理
\large\color{magenta}{\boxed{\color{brown}{定理} }}
定理设
f
(
x
)
f(x)
f(x) 可微,
x
k
∈
D
,
x^{k} \in D,
xk∈D, 如果
y
k
y^{k}
yk 是上述线性规划的最优解, 则有
(1) 当
∇
f
(
x
k
)
T
(
y
k
−
x
k
)
=
0
时
,
则
x
k
\nabla f\left(x^{k}\right)^{T}\left(y^{k}-x^{k}\right)=0 时, 则 x^{k}
∇f(xk)T(yk−xk)=0时,则xk 是
K
−
T
K-T
K−T 点;
(2) 当
∇
f
(
x
k
)
T
(
y
k
−
x
k
)
≠
0
\nabla f\left(x^{k}\right)^{T}\left(y^{k}-x^{k}\right) \neq 0
∇f(xk)T(yk−xk)=0 时,则向量
d
k
=
y
k
−
x
k
d^{k}=y^{k}-x^{k}
dk=yk−xk 是
f
(
x
)
f(x)
f(x) 在点
x
k
x^{k}
xk 处关于
D
D
D 的可行下降方向。
当
∇
f
(
x
k
)
T
(
y
k
−
x
k
)
≠
0
\nabla f\left(x^{k}\right)^{T}\left(y^{k}-x^{k}\right) \neq 0
∇f(xk)T(yk−xk)=0 时,求解下列一维搜索问题
min
f
(
x
k
+
λ
(
y
k
−
x
k
)
)
s.t.
0
≤
λ
≤
1
\begin{array}{ll} \min & f\left(x^{k}+\lambda\left(y^{k}-x^{k}\right)\right) \\ \text { s.t. } & 0 \leq \lambda \leq 1 \end{array}
min s.t. f(xk+λ(yk−xk))0≤λ≤1
设极小点为
λ
k
,
\lambda_{k},
λk, 则可取
x
k
+
1
=
x
k
+
λ
k
(
y
k
−
x
k
)
.
x^{k+1}=x^{k}+\lambda_{k}\left(y^{k}-x^{k}\right) .
xk+1=xk+λk(yk−xk). 因为D为凸集, 则
x
k
+
1
∈
D
.
x^{k+1} \in D .
xk+1∈D.
再对点
x
k
+
1
x^{k+1}
xk+1 重复上述过程。
参考资料
http://www.doc88.com/p-9428289778928.html
http://www.doc88.com/p-6189636904074.html
https://wenku.baidu.com/view/a9074e61524de518974b7d65.html?fr=search-1-wk_sea_es-income3
https://wenku.baidu.com/view/d1a4495484254b35effd342a.html?fr=search-1-wk_sea_es-income1