凸优化 - Fritz-John 条件

必要条件

定理

考虑问题 - $min f\left ( x \right )$ 使得 $x \in X$ ，其中 X 是 $\mathbb{R}^n$ 中的开集，并令 $g_i \left ( x \right ) \leq 0, \forall i =1,2,....m$。

设 $f:X \rightarrow \mathbb{R}$ 和 $g_i:X \rightarrow \mathbb{R}$

设 $\hat{x}$ 为可行解，并设 f 和 $g_i, i \in I$ 在 $\hat{x}$ 处可微，且 $g_i, i \in J$ 在 $\hat{ 处连续x}$。

如果 $\hat{x}$ 局部解决了上述问题，则存在 $u_0, u_i \in \mathbb{R}, i \in I$ 使得 $u_0 \bigtriangledown f\left ( \hat{x} \右 )+\displaystyle\sum\limits_{i\in I} u_i \bigtriangledown g_i \left ( \hat{x} \right )$=0

其中 $u_0,u_i \geq 0,i \in I$ 和 $\left ( u_0, u_I \right ) \neq \left ( 0,0 \right )$

此外，如果 $g_i,i \in J$ 在 $\hat{x}$ 处也可微，则上述条件可以写为 -

$u_0 \bigtriangledown f\left ( \hat{x}\right )+\displaystyle\sum\limits_{i=1}^m u_i \bigtriangledown g_i\left ( \hat{x} \right )=0$

$u_ig_i\left (\hat{x} \right )$=0

$u_0,u_i \geq 0, \forall i=1,2,....,m$

$\left (u_0,u \right ) \neq \left ( 0,0 \right ), u=\left ( u_1,u_2,s,u_m \right ) \in \mathbb{R}^m$

$u_i$ 称为拉格朗日乘数。
$\hat{x}$ 对给定问题可行的条件称为原始可行条件。
要求 $u_0 \bigtriangledown f\left (\hat{x} \right )+\displaystyle\sum\limits_{i=1}^m ui \bigtriangledown g_i\left ( x \right )=0$ 称为对偶可行性健康）状况。
条件 $u_ig_i\left ( \hat{x} \right )=0, i=1, 2, ...m$ 称为互补松弛条件。这个条件需要$u_i=0, i \in J$
原始可行条件、对偶可行性条件和互补松弛性一起称为弗里茨-约翰条件。

充分条件

定理

如果存在 $\hat{x}N_\varepsilon \left 的 $\varepsilon$ 邻域 ( \hat{x} \right ),\varepsilon >0$ 使得 f 在 $N_\varepsilon \left 上是伪凸 ( \hat{x} \right )\cap S$ 和 $g_i,i \in I$ 在 $N_\varepsilon \left ( \hat{x}\right )\cap S$ 上严格伪凸，则 $\hat{ x}$ 是上述问题的局部最优解。如果 f 在 $\hat{x}$ 处是伪凸函数，并且如果 $g_i, i \in I$ 都是在 $\hat{x}$ 处的严格伪凸函数和拟凸函数，\hat{x}$ 是该问题的全局最优解如上所述。

例子

$min \:f\left ( x_1,x_2 \right )=\left ( x_1-3 \right )^2+\left ( x_2-2 \right )^2$

使得 $x_{1}^{2}+x_{2}^{2} \leq 5, x_1+2x_2 \leq 4, x_1,x_2 \geq 0$ 并且 $\hat{x}=\left ( 2 ,1 \右)$

设 $g_1\left (x_1,x_2 \right )=x_{1}^{2}+x_{2}^{2} -5,$

$g_2\左(x_1,x_2\右)=x_1+2x_2-4,$

$g_3\left (x_1,x_2 \right )=-x_1$ 和 $g_4\left ( x_1, x_2 \right )= -x_2$。

因此上述约束可以写为 -

$g_1\左 (x_1,x_2 \右)\leq 0,$

$g_2\左 (x_1,x_2 \右)\leq 0,$

$g_3\left (x_1,x_2 \right )\leq 0$ 和

$g_4\left (x_1,x_2 \right )\leq 0$ 因此，$I = \left \{1,2 \right \}$ 因此，$u_3=0,u_4=0$

$\bigtriangledown f \left (\hat{x} \right )=\left (2,-2 \right ),\bigtriangledown g_1\left (\hat{x} \right )=\left (4,2 \right )$ 和 $\bigtriangledown g_2\left (\hat{x} \right )=\left (1,2 \right )$

因此，将这些值放入 Fritz-John 条件的第一个条件中，我们得到 -

$u_0=\frac{3}{2} u_2, \:\:u_1= \frac{1}{2}u_2,$ 并让 $u_2=1$，因此 $u_0= \frac{3}{2} ,\:\:u_1= \frac{1}{2}$

这样弗里茨·约翰的条件就满足了。
$min f\left (x_1,x_2\right )=-x_1$。

这样 $x_2-\left (1-x_1\right )^3 \leq 0$,

$-x_2 \leq 0$ 和 $\hat{x}=\left (1,0\right )$

令 $g_1\left (x_1,x_2 \right )=x_2-\left (1-x_1\right )^3$,

$g_2\左 (x_1,x_2 \右)=-x_2$

因此上述约束可以写为 -

$g_1\左 (x_1,x_2 \右)\leq 0,$

$g_2\左 (x_1,x_2 \右)\leq 0,$

因此，$I=\left \{1,2 \right \}$

$\bigtriangledown f\left (\hat{x} \right )=\left (-1,0\right )$

$\bigtriangledown g_1 \left (\hat{x} \right )=\left (0,1\right )$ 和 $g_2 \left (\hat{x} \right )=\left (0, -1 \right )$

因此，将这些值放入 Fritz-John 条件的第一个条件中，我们得到 -

$u_0=0,\:\: u_1=u_2=a>0$

这样弗里茨·约翰的条件就满足了。

凸优化 - Fritz-John 条件

必要条件

定理

评论

充分条件

定理

例子