凸优化 - Fritz-John 条件

必要条件

定理

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

令 $f:X ightarrow \mathbb{R}$ 和 $g_i:X ightarrow \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} ight )+\displaystyle\sum\limits_{i\in I} u_i \bigtriangledown g_i \left ( \hat{x} ight )$=0

其中 $u_0,u_i \geq 0,i \in I$ 且 $\left ( u_0, u_I ight ) eq \left ( 0,0 ight )$

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

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

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

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

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

备注

• $u_i$ 称为拉格朗日乘数。

• $\hat{x}$ 对于给定问题可行，称为原始可行条件。

• 要求 $u_0 \bigtriangledown f\left (\hat{x} ight )+\displaystyle\sum\limits_{i=1}^m u-i \bigtriangledown g_i\left ( x ight )=0$称为对偶可行性条件。

• 条件 $u_ig_i\left ( \hat{x} ight )=0, i=1, 2, ...m$称为互补松弛条件。此条件要求 $u_i=0, i \in J$

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

充分条件

定理

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

示例

• $min \:f\left ( x_1,x_2 ight )=\left ( x_1-3 ight )^2+\left ( x_2-2 ight )^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 ight )$

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

  $g_2\left (x_1,x_2 ight )=x_1+2x_2-4,$

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

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

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

  $g_2\left (x_1,x_2 ight )\leq 0,$

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

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

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

  因此将这些值放入 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 ight )=-x_1$。

  这样 $x_2-\left (1-x_1 ight )^3 \leq 0$，

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

  设 $g_1\left (x_1,x_2 ight )=x_2-\left (1-x_1 ight )^3$，

  $g_2\left (x_1,x_2 ight )=-x_2$

  因此上述约束可以写成−

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

  $g_2\left (x_1,x_2 ight )\leq 0,$

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

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

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

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

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

  因此 Fritz John 条件得到满足。