Zoutendijk可行方向法

1 基本问题

Zoutendijk可行性方法属于约束优化问题可行方向法中的一种。与之前无约束优化问题中的最速下降法、牛顿法相像。可行方向法的策略是：从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点.

\(\large\color{#70f3ff}{\boxed{\color{brown}{基本思想：} }}\)

在给定一个可行点\(x_k\)之后，用某种方法确定一个改进的可行方向\(d_k\),然后沿方向\(d_k\)，求解一个有约束的线搜索问题,得极小点\(x_{k+1}\)，令

\[x_{k+1}=x_{k}+\alpha_kd_k\tag1 \]

如果仍不是最优解,则重复上述步骤.

不同的可行方向法的主要区别在于，选择可行方向的策略不同,大体上可以分为三类:

• 用求解一个\(\bbox[cyan,2pt]{线性规划}\)问题来确定,如Zoutendjk方法,Frank-Wolfe方法和Topkis-Veinott方法等;
• 利用\(\bbox[cyan,2pt]{投影矩阵}\)来直接构造一个改进的可行方向,如Rosen的梯度投影法和Rosen-Polak方法等;
• 利用\(\bbox[cyan,2pt]{既约梯度}\),直接构造一个改进的可行方向,如Wolfe的既约梯度法及其各种改进,凸单纯形法.

2 线性约束情形

考虑线性约束问题

\[\begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\\text{s.t.} &~ ~ ~ Ax \geq b\\ &~ ~ ~ Ex = e\\ &~ ~ ~x ∈ R^n \end{aligned} \]

(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 \]

---

根据无约束问题的最优条件\(\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} }}\)

• 若\(∇f(x)^T d < 0\),则\(d\)为可行下降方向;
• 若\(∇f(x)^T d = 0\),则\(x\)是KKT点.

(2)确定一维搜索步长

在（1）式的迭代中，为保证后继迭代点的可行性,考虑求解

\[\begin{aligned} (PC) ~ ~ ~ \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 \]

利用可行方向条件与起作用约束简化(PC),即(PC)满足

\[Ex_k= e , Ed_k= 0, A_1x_k = b_1, A_1d_k≥0 \]

化简为

\[\begin{aligned} (PC) ~ ~ ~ \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} (PC) ~ ~ ~ \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} (PC) ~ ~ ~ \min &~ ~ ~ f(x_{k}+\alpha d_k)\\\text{s.t.} &~ ~ ~ 0\leq \alpha \leq \alpha_{max} \end{aligned}\tag 7 \]

\(\large\color{#70f3ff}{\boxed{\color{brown}{算法步骤} }}\)

1. 选定初始容许点$ x_{0} \(；允许误差\) \varepsilon$ ,置 \(k=0\) 。

2. 把 \(A\) 分解为 $A_1,A_2 $，相应地把 $b $分解为 \(b_1,b_2\) ，使得 \(A_1x = b_1,A_2x >b_2\) ,求\(∇f(x_k)\)。

3. 求解线性规划问题：

   \[\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\)

4. 若 $ |\nabla f(x_{k})^{T}p_{k}| < \varepsilon $，则输出 \(x_{k}\) ，停止迭代；否则，计算\(\hat{b} =b_2-A_2x_{k} ,~~ \hat{d}= A_2 d_k\) 。

5. 精确线搜索：

   \[\begin{aligned} (PC) ~ ~ ~ \min &~ ~ ~ f(x_{k}+\alpha d_k)\\\text{s.t.} &~ ~ ~ 0\leq \alpha \leq \alpha_{max} \end{aligned} \]

   得步长\(\alpha _k\).

6. 令$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} (PC) ~ ~ ~ \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} (PC) ~ ~ ~ \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)利用起作用约束构造可行下降方向

设\(x\)是问题(8)的可行解,点\(x\)处起作用约束的指标集记作\(I(x )=\{ i| g_i(x)= 0, i = 1,~ \ldots, m\}\)
点\(x\)处的可行下降方向\(d\)满足:

\[\left\{\begin{matrix} &~∇f(x)^T d < 0 \\ &~∇g_i(x)^T d > 0,i \in I(x) \end{matrix}\right.\tag9 \]

问题(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}\)

\(\large\color{#70f3ff}{\boxed{\color{brown}{算法步骤} }}\)

1. 选定初始容许点$ x_{0} \(；允许误差\) \varepsilon$ ,置 \(k=0\) 。

2. 确定起作用约束.确定点$ x_{k} $处起作用约束的指标集

   \(I(x_{k} )=\{ i| g_i(x_{k})= 0, i = 1,~ \ldots, m\}\)

3. 求解线性规划问题：

   \[\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)\)

4. 若 $ |z_k| < \varepsilon $，则输出 \(x_{k}\) ，停止迭代；否则，得到可行下降方向\(d_k\)，进行5

5. 精确线搜索：

   \[\begin{aligned} \min &~ ~ ~ f(x_{k}+\alpha d_k)\\\text{s.t.} &~ ~ ~ 0\leq \alpha \leq \alpha_{max} \end{aligned} \]

   得步长\(\alpha _k\).

6. 令$x_{k+1}=x_{k}+\alpha_kd_k $ ,\(~~~k=k+1\) ，转2。

非线性约束情形算法特点

计算实践和理论分析表明,该算法可能失效或出现锯齿现象使算法收敛很慢甚至不收敛到最优点或KKT点.

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}{算法步骤} }}\)

1. 选定初始容许点$ x_{0} \(；允许误差\) \varepsilon$ ,置 \(k=0\) 。

2. 确定起作用约束.确定点$ x_{k} \(处起作用约束的指标集\)I_{\varepsilon_k}(x_{k} )={ i| 0 \leq g_i(x_{k})\leq \varepsilon_k, i = 1,~ \ldots, m}$

3. 求解线性规划问题：

   \[\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)\)

4. 若 $ |z_k| < \varepsilon $，则输出 \(x_{k}\) ，停止迭代；否则，得到可行下降方向\(d_k\)，进行5

5. 精确线搜索：

   \[\begin{aligned} \min &~ ~ ~ f(x_{k}+\alpha d_k)\\\text{s.t.} &~ ~ ~ 0\leq \alpha \leq \alpha_{max} \end{aligned} \]

   得步长\(\alpha _k\).

6. 令$x_{k+1}=x_{k}+\alpha_kd_k $ ,\(~~~k=k+1\) ，转2。

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