凸最佳化 - 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 條件。