凸优化 - 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} \right )+\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 u_i \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$

• 原始可行性条件、对偶可行性条件和互补松弛条件一起称为 Fritz-John 条件。

充分条件

定理

如果存在 $\hat{x}$ 的 $\varepsilon$-邻域 $N_\varepsilon \left ( \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 \right )$

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

  $g_2\left (x_1,x_2 \right )=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\left (x_1,x_2 \right )\leq 0,$

  $g_2\left (x_1,x_2 \right )\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}$

  因此，满足 Fritz-John 条件。

• $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\left (x_1,x_2 \right )=-x_2$

  因此，上述约束可以写成：

  $g_1\left (x_1,x_2 \right )\leq 0,$

  $g_2\left (x_1,x_2 \right )\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 条件。