Zoutendijk可行方向法
目录1 基本问题
Zoutendijk可行性方法属于约束优化问题可行方向法中的一种。与之前无约束优化问题中的最速下降法、牛顿法相像。可行方向法:从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点，直到满足终止条件，得到最优解\(x^*\).
\(\large\color{#70f3ff}{\boxed{\color{brown}{基本思想：} }}\)
在给定一个可行点\(x^k\)之后，用某种方法确定一个改进的可行方向\(d^k\),然后沿方向\(d^k\)，求解一个有约束的线搜索问题,得极小点\(x^{k+1}\)，令
\[x^{k+1}=x^{k}+\alpha_k d^k \tag{*} \]如果仍不是最优解,则重复上述步骤.
不同的可行方向法的主要区别在于，选择可行方向的策略不同,大体上可以分为三类:
- 用求解一个 \(\bbox[cyan,2pt]{线性规划}\) 问题来确定,如Zoutendjk方法,Frank-Wolfe方法和Topkis-Veinott方法等;
- 利用\(\bbox[cyan,2pt]{投影矩阵}\)来直接构造一个改进的可行方向,如Rosen的梯度投影法和Rosen-Polak方法等;
- 利用\(\bbox[cyan,2pt]{既约梯度}\),直接构造一个改进的可行方向,如Wolfe的既约梯度法及其各种改进,凸单纯形法.
可行方向法是通过直接处理约束问题，得到一个下降可行方向，从而产生一个收敛于线性约束优化问题的K-T点。一般地，求解约束优化问题要比求解无约束优化问题复杂、困难，因为在求解过程中，不仅要使目标函数值单调下降，而且还要保证迭代点满足约束条件。因此，在求解过程中，要求产生的迭代点的搜索方向为下降可行方向。由于这时的约束为线性函数，因而可通过利用线性代数的知识和无约束优化方法来设计一些有效算法。
2 线性约束情形
考虑线性约束问题
\[\begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\\text{s.t.} &~ ~ ~ Ax \geq b\\ &~ ~ ~ Ex = e\\ &~ ~ ~x ∈ R^n \end{aligned}\tag{1} \](1)利用起作用约束构造可行下降方向
\(\large\color{magenta}{\boxed{\color{brown}{定理1} }}\)设\(x\)是问题\((P)\)的可行解,在点\(x\)处有\(A_1x = b_1,A_2x >b_2\),其中
\[A=\begin{bmatrix} A_1\\ A_2 \end{bmatrix}, b=\begin{bmatrix} b_1\\ b_2 \end{bmatrix} \]则非零向量\(d\)为\(x\)处的可行方向的充要条件是
\[A_1d≥0~~,~~ Ed =0\tag2 \]【证明】必要性 设非零向量 \(d\) 是 \(\bar{x}\) 处的可行方向, 则存在 \(\delta>\mathbf{0},\) 使得对任意
的 \(\alpha \in(\mathbf{0}, \delta), \bar{x}+\alpha d\) 仍是可行解。即 \(A(\bar{x}+\alpha d) \geq b, E(\bar{x}+\alpha d)=e\)
充分性同理可证
因为 \(\alpha >0,\) 所以 \(A_{1} d \geq 0 .\) 而 \(E(\bar{x}+\alpha d)=e+\alpha E d=e,\) 故 \(E d=0 .\)\(\bbox[cyan,2pt]{~~}\)
(1)根据无约束问题的KKT条件
\[\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} \]可得
\[\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 \]\(\large\color{#70f3ff}{\boxed{\color{brown}{定理4.1} }}\)和定理1,如果非零向量d同时满足
\[∇f(x)^T d < 0,A_1d≥0~~,~~ Ed =0\tag3 \]则d是x处的可行下降方向.
由（2）可以将求解（P）转化为求解线性规划问题：
\[\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} \]其中为了能获得有限最优解,限制了方向\(d\)的长度,即增加规范约束条件\(-1 \leq d_j \leq 1,j=1,...,n\)
因\(d=0\)是问题(PS)的可行解,故目标函数的最优值必定小于或等于0.
\(\large\color{magenta}{\boxed{\color{brown}{定理2} }}\)设x是(P)的一个可行解，则\(x\)是(P)的KKT点当且仅当(PS)目标函数的最优值为零,
- 若\(∇f(x)^T d < 0\),则\(d\)是问题(P)在x处的可行下降方向;
- 若\(∇f(x)^T d = 0\),则\(x\)是KKT点.
(2)确定一维搜索步长
在\(\tag{*}\)式的迭代中，为保证后继迭代点的可行性,考虑求解
\[\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 \](4)中\(E(x^{k}+\alpha d^k) =e\) 可去除，因为 \(d^{k}\) 是可行下降方向，故 \(E d^{k}=0,\) 即约束条件
\[E\left(x^{k}+\alpha d^{k}\right)=E x^{k}+\alpha E d^{k}=E x^{k}=e \]总是成立。
设在点 \(x^{k}\) 处有 \(A_{1} x^{k}=b_{1}, A_{2} x^{k}>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\left(x^{k}+\alpha d^{k}\right) \geq b\) 可改写为 \(\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)\),
\(d\) 是可行方向 \(\Leftrightarrow A_{1} d \geq 0, E d=0\)
因为 \(d^{k}\) 是可行下降方向,所以 \(A_{1} d^{k} \geq 0,\) 又 \(A_{1} x^{k}=b_{1}, \alpha \geq 0\),
故不等式约束 \(A_{1}\left(x^{k}+\alpha d^{k}\right) \geq b_{1}\) 自然成立。
利用可行方向条件与起作用约束简化\((P\alpha)\),即\((P\alpha)\)满足
\[Ex^k= e , Ed^k= 0, A_1x^k = b_1, A_1d^k≥0,~A_2x^k >b_2 \]化简为
\[\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_2x >b_2\)则 \(\hat{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)在\(\hat{d}≥0\),这时对于\(\alpha \geq 0\),\(\alpha \hat{d} ≥\hat{b}\)式总成立;
(2)\(\hat{d}\ngeqslant0\),这时\(\hat{d}\)至少有一个分量\(\hat{d_i}<0\)对于\(\alpha \geq 0\),使\(\alpha \hat{d} ≥\hat{b}\)式成立的\(\alpha\)的上限为\(min\left\{ \frac{\hat{b_i}}{\hat{d_i}}, \hat{d_i}<0\right\}\)
记
\[\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}\)；允许误差\(\varepsilon\) ,置 \(k=0\) 。
-
把 \(A\) 分解为 \(A_1,A_2\)，相应地把 \(b\)分解为 \(b_1,b_2\) ，使得 \(A_1x^k = b_1,A_2x^k >b_2\) ,求\(∇f(x^k)\)。
-
求解线性规划问题：
\[\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} \]得最优解\(d^k\)
-
若 \(|\nabla f(x_{k})^{T}d^{k}| < \varepsilon\)，则输出 \(x_{k}\) ，停止迭代；否则，计算\(\hat{b} =b_2-A_2x^{k} ,~~ \hat{d}= A_2 d^k\) 。
-
精确线搜索：
\[\begin{aligned} (P\alpha_{max}) ~ ~ ~ \min &~ ~ ~ f(x^{k}+\alpha d^k)\\\text{s.t.} &~ ~ ~ 0\leq \alpha \leq \alpha_{max} \end{aligned} \]得步长\(\alpha _k\).
-
令\(x^{k+1}=x^{k}+\alpha_kd^k\) ,\(~~~k=k+1\) ，转2。
例
用Zoutendijk可行方向法解下列优化问题
取初始可行点\(x^1 =(0,0)^T\).
【解】将原问题化为
\[\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} \]第一次迭代:
\[∇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} \]在\(x^1 =(0,0)^T\)处寻找满足分解\(A\)的子矩阵：
\[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)求解线性规划问题：
\[\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} \]由图解法求得最优解 \(d^1 = (1,1)^T\)
(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}\)
由于\(\hat{d}\ngeqslant0\)，计算
\[\alpha_{max} = min\left\{ \frac{{-1}}{{-1}},\frac{{-2}}{{-2}}\right\} =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}\)
\[\begin{aligned} (P\alpha_{max}) ~ ~ ~ \min &~ ~ ~ f(x^{1}+\alpha d^1)=2\alpha^2 -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 $解得 \(\alpha_1=1\).
令$x{2}=x{1}+\alpha_1d^1=\begin{pmatrix}1
\ 1 \end{pmatrix} $
第二次迭代:
在\(x^2 =(1,1)^T\)处寻找满足分解\(A\)的子矩阵：
\[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} \] \[∇f(x^2)=\begin{pmatrix}0 \\ -2 \end{pmatrix} \](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} \]由图解法求得最优解 \(d^2 = (-1,1)^T\)
(2)精确线搜索：
计算
\[\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} \]由于\(\hat{d}\ngeqslant0\)，计算
\[\alpha_{max} = min\left\{ \frac{{-1}}{{-1}}\right\} =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}\)
\[\begin{aligned} (P\alpha_{max}) ~ ~ ~ \min &~ ~ ~ f(x^{1}+\alpha d^1)=2\alpha^2 -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 $解得 \(\alpha_2=\frac{1}{2}\).
令$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)求解线性规划问题：
\[\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} \]由图解法求得最优解 \(d^3 = (0,0)^T\)
此时\(∇f(x)^T d = 0\).所以由\(\large\color{magenta}{\boxed{\color{brown}{定理2} }}\)知$x^3 \(是原问题的KKT点.又因为原问题是凸规划,所以\)x^3 \(是原问题的最优解。最优值为\)f(x^3) = \frac{3}{2}$.
3 非线性约束情形
考虑不等式约束问题
\[\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 \](1)利用起作用约束构造可行下降方向
\(\large\color{magenta}{\boxed{\color{brown}{定理} }}\)设\(x\)是问题(8)的可行解,点\(x\)处起作用约束的指标集记作\(I(x )=\{ i| g_i(x)= 0, i = 1,~ \ldots, m\}\)
设目标函数和 \(g_{i}(x)(i \in I)\) 在 \(x\) 点可 微， \(g_{i}(x)(i \notin I)\) 在 \(x\) 点连续,点\(x\)处的可行下降方向\(d\)满足:
问题(8)化简为线性规划问题：
\[\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} \]\(\large\color{magenta}{\boxed{\color{brown}{定理3} }}\)设问题(10)的最优解为\((\bar{z}, \bar{d})\)有下述两种情况:
- (1)若\(\bar{z}<0\),则\(\bar{d}\)为\(x\)处的可行下降方向;
- (2)若\(\bar{z}=0\),则\(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} \]其中\(\alpha_{max}=sup ~\{\alpha | g_i(x_{k}+\alpha d_k)\geq 0 ,i = 1,~ \ldots, m \} \tag{12}\)
算法步骤
-
选定初始容许点$ x_{0} \(；允许误差\) \varepsilon$ ,置 \(k=0\) 。
-
确定起作用约束.确定点$ x_{k} $处起作用约束的指标集
\(I(x_{k} )=\{ i| g_i(x_{k})= 0, i = 1,~ \ldots, m\}\)
-
求解线性规划问题：
\[\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} \]得最优解\((z_k,d_k)\)
-
若 $ |z_k| < \varepsilon $，则输出 \(x_{k}\) ，停止迭代；否则，得到可行下降方向\(d_k\)，进行5
-
精确线搜索：
\[\begin{aligned} \min &~ ~ ~ f(x_{k}+\alpha d_k)\\\text{s.t.} &~ ~ ~ 0\leq \alpha \leq \alpha_{max} \end{aligned} \]得步长\(\alpha _k\).
-
令$x_{k+1}=x_{k}+\alpha_kd_k $ ,\(~~~k=k+1\) ，转2。
Zoutendijk可行方向法特点
特点:1）可行方向法是用梯度去求解约束优化设计问题的一种有代表性的直接搜索方法。
2）收敛速度快，效果较好，但程序比较复杂。使用条件:适用于大中型约束优化设计问题的求解。
缺点:
由于Zoutendijk可行方向法是基于无约束优化中的最速下降法,所以此算法具有最速下降法的一些缺点。以非典型的缺点就是“锯齿现象”，从而，当迭代逼近非有效约束边界时可能会发生一些突然的变化，使得收敛速度很慢，甚至不收敛于K-T点.
Zoutendijk法的改进问题的提出
对于线性和非线性不等式约束问题,前面我们仅使用起作用约束来确定搜索方向．当某迭代点在一个约束的边界上时，如果可行方向取得不恰当，那么沿该方向可能因接近另一个约束边界而只能作一个微小的移动，否则,就会使迭代点跑出边界．为防止这一现象发生,设想在约束条件的边界上设立一道“安全带”，迭代点进入“安全带”时，只允许它往可行域内部移动,而不许向边界靠近.为此引入起作用约束的概念,即在构造可行方向时，既把通过当前迭代点的约束边界看作起作用约束，也把充分接近当前这代点的边界约束考虑在内.
4 Zoutendijk法的改进
(1)\(\varepsilon\)起作用约束可行方向法
\(\large\color{magenta}{\boxed{\color{brown}{定义} }}\)对于给定的\(\varepsilon_k >0\),称\(I_{\varepsilon_k}(x_{k} )=\{ i| 0 \leq g_i(x_{k})\leq \varepsilon_k, i = 1,~ \ldots, m\}\)为点$ x_{k} \(处的\)\varepsilon_k 起作用$约束的指标集
\(\large\color{#70f3ff}{\boxed{\color{brown}{算法步骤} }}\)
-
选定初始容许点$ x_{0} \(；允许误差\) \varepsilon$ ,置 \(k=0\) 。
-
确定起作用约束.确定点$ x_{k} \(处起作用约束的指标集\)I_{\varepsilon_k}(x_{k} )={ i| 0 \leq g_i(x_{k})\leq \varepsilon_k, i = 1,~ \ldots, m}$
-
求解线性规划问题：
\[\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} \]得最优解\((z_k,d_k)\)
-
若 $ |z_k| < \varepsilon $，则输出 \(x_{k}\) ，停止迭代；否则，得到可行下降方向\(d_k\)，进行5
-
精确线搜索：
\[\begin{aligned} \min &~ ~ ~ f(x_{k}+\alpha d_k)\\\text{s.t.} &~ ~ ~ 0\leq \alpha \leq \alpha_{max} \end{aligned} \]得步长\(\alpha _k\).
-
令$x_{k+1}=x_{k}+\alpha_kd_k $ ,\(~~~k=k+1\) ，转2。
Frank-Wolfe 方法
给定线性规划问题
\[\min f(x)\\ \text {s.t.}\left\{\begin{array}{c} A x=b \\ x \geq 0 \end{array}\right. \]其中 \(A\) 是 \(m \times n\) 矩阵，秩为 \(m, b\) 是 \(m\) 维列向量, \(f(x)\) 是可微函数,\(x \in R^{n} \cdot\) 令 \(D=\{x \mid A x=b, x \geq 0\},\) 称 \(D\) 为可行域。
算法思想:在每次迭代中, 将目标函数 \(f(x)\) 线性化，通过 求解线性规划方法求得可行下降方向, 并沿该方向在可行 域内进行一维搜索。
设已知可行点 \(x^{k},\) 则有
求解线性规划
\[\begin{array}{ll} \min & \nabla f\left(x^{k}\right)^{T} x \\ \text {s.t.} & x \in D \end{array} \]\(\large\color{magenta}{\boxed{\color{brown}{定理} }}\)设 \(f(x)\) 可微, \(x^{k} \in D,\) 如果 \(y^{k}\) 是上述线性规划的最优解, 则有
(1) 当 \(\nabla f\left(x^{k}\right)^{T}\left(y^{k}-x^{k}\right)=0 时, 则 x^{k}\) 是 \(K-T\) 点;
(2) 当 \(\nabla f\left(x^{k}\right)^{T}\left(y^{k}-x^{k}\right) \neq 0\) 时,则向量 \(d^{k}=y^{k}-x^{k}\) 是 \(f(x)\) 在点 \(x^{k}\) 处关于 \(D\) 的可行下降方向。
当 \(\nabla f\left(x^{k}\right)^{T}\left(y^{k}-x^{k}\right) \neq 0\) 时,求解下列一维搜索问题
\[\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} \]设极小点为 \(\lambda_{k},\) 则可取 \(x^{k+1}=x^{k}+\lambda_{k}\left(y^{k}-x^{k}\right) .\) 因为D为凸集, 则 \(x^{k+1} \in D .\)
再对点 \(x^{k+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