凸最佳化 - 規劃問題

---

---

有四種類型的凸規劃問題：

步驟1 − $min \:f\left ( x \right )$, 其中 $x \in S$ 且 S 是 $\mathbb{R}^n$ 中的非空凸集，$f\left ( x \right )$ 是凸函式。

步驟2 − $min \: f\left ( x \right ), x \in \mathbb{R}^n$ 受以下約束：

$g_i\left ( x \right ) \geq 0, 1 \leq m_1$ 且 $g_i\left ( x \right )$ 是凸函式。

$g_i\left ( x \right ) \leq 0,m_1+1 \leq m_2$ 且 $g_i\left ( x \right )$ 是凹函式。

$g_i\left ( x \right ) = 0, m_2+1 \leq m$ 且 $g_i\left ( x \right )$ 是線性函式。

其中 $f\left ( x \right )$ 是凸函式。

步驟3 − $max \:f\left ( x \right )$ 其中 $x \in S$ 且 S 是 $\mathbb{R}^n$ 中的非空凸集，$f\left ( x \right )$ 是凹函式。

步驟4 − $min \:f\left ( x \right )$, 其中 $x \in \mathbb{R}^n$ 受以下約束：

$g_i\left ( x \right ) \geq 0, 1 \leq m_1$ 且 $g_i\left ( x \right )$ 是凸函式。

$g_i\left ( x \right ) \leq 0, m_1+1 \leq m_2$ 且 $g_i\left ( x \right )$ 是凹函式。

$g_i\left ( x \right ) = 0,m_2+1 \leq m$ 且 $g_i\left ( x \right )$ 是線性函式。

其中 $f\left ( x \right )$ 是凹函式。

可行方向錐

設 S 是 $\mathbb{R}^n$ 中的非空集，且 $\hat{x} \in \:Closure\left ( S \right )$，則 S 在 $\hat{x}$ 處的可行方向錐，記為 D，定義為 $D=\left \{ d:d\neq 0,\hat{x}+\lambda d \in S, \lambda \in \left ( 0, \delta \right ), \delta > 0 \right \}$

每個非零向量 $d \in D$ 稱為可行方向。

對於給定函式 $f:\mathbb{R}^n \Rightarrow \mathbb{R}$，在 $\hat{x}$ 處的改進方向錐記為 F，且由下式給出：

$$F=\left \{ d:f\left ( \hat{x}+\lambda d \right )\leq f\left ( \hat{x} \right ),\forall \lambda \in \left ( 0,\delta \right ), \delta >0 \right \}$$

每個方向 $d \in F$ 稱為 f 在 $\hat{x}$ 處的改進方向或下降方向

定理

必要條件

考慮問題 $min f\left ( x \right )$ 使得 $x \in S$，其中 S 是 $\mathbb{R}^n$ 中的非空集。假設 f 在點 $\hat{x} \in S$ 處可微。如果 $\hat{x}$ 是區域性最優解，則 $F_0 \cap D= \phi$，其中 $F_0=\left \{ d:\bigtriangledown f\left ( \hat{x} \right )^T d < 0 \right \}$ 且 D 是可行方向錐。

充分條件

如果 $F_0 \cap D= \phi$，f 是在 $\hat{x}$ 處的偽凸函式，並且存在 $\hat{x}$ 的鄰域 $N_\varepsilon \left ( \hat{x} \right ), \varepsilon > 0$，使得對於任何 $x \in S \cap N_\varepsilon \left ( \hat{x} \right )$，$d=x-\hat{x}\in D$，則 $\hat{x}$ 是區域性最優解。

證明

必要條件

設 $F_0 \cap D\neq \phi$，即存在 $d \in F_0 \cap D$ 使得 $d \in F_0$ 且 $d\in D$

由於 $d \in D$，因此存在 $\delta_1 >0$ 使得 $\hat{x}+\lambda d \in S, \lambda \in \left ( 0,\delta_1 \right ).$

由於 $d \in F_0$，因此 $\bigtriangledown f \left ( \hat{x}\right )^T d <0$

因此，存在 $\delta_2>0$ 使得 $f\left ( \hat{x}+\lambda d\right )< f\left ( \hat{x}\right ),\forall \lambda \in f \left ( 0,\delta_2 \right )$

設 $\delta=min \left \{\delta_1,\delta_2 \right \}$

則 $\hat{x}+\lambda d \in S, f\left (\hat{x}+\lambda d \right ) < f\left ( \hat{x} \right ),\forall \lambda \in f \left ( 0,\delta \right )$

但 $\hat{x}$ 是區域性最優解。

因此，這是一個矛盾。

因此 $F_0\cap D=\phi$

充分條件

設 $F_0 \cap D\neq \phi$ 且 f 是偽凸函式。

設存在 $\hat{x}$ 的鄰域 $N_{\varepsilon}\left ( \hat{x} \right )$ 使得 $d=x-\hat{x}, \forall x \in S \cap N_\varepsilon\left ( \hat{x} \right )$

設 $\hat{x}$ 不是區域性最優解。

因此，存在 $\bar{x} \in S \cap N_\varepsilon \left ( \hat{x} \right )$ 使得 $f \left ( \bar{x} \right )< f \left ( \hat{x} \right )$

根據 $S \cap N_\varepsilon \left ( \hat{x} \right )$ 的假設，$d=\left ( \bar{x}-\hat{x} \right )\in D$

根據 f 的偽凸性，

$$f\left ( \hat{x} \right )>f\left ( \bar{x} \right )\Rightarrow \bigtriangledown f\left ( \hat{x} \right )^T\left ( \bar{x}-\hat{x} \right )<0$$

$\Rightarrow \bigtriangledown f\left ( \hat{x} \right) ^T d <0$

$\Rightarrow d \in F_0$

因此 $F_0\cap D \neq \phi$

這是一個矛盾。

因此，$\hat{x}$ 是區域性最優解。

考慮以下問題：$min \:f\left ( x\right )$ 其中 $x \in X$ 使得 $g_x\left ( x\right ) \leq 0, i=1,2,...,m$

$f:X \rightarrow \mathbb{R},g_i:X \rightarrow \mathbb{R}^n$ 且 X 是 $\mathbb{R}^n$ 中的開集

設 $S=\left \{x:g_i\left ( x\right )\leq 0,\forall i \right \}$

設 $\hat{x} \in X$，則 $M=\left \{1,2,...,m \right \}$

設 $I=\left \{i:g_i\left ( \hat{x}\right )=0, i \in M\right \}$，其中 I 稱為 $\hat{x}$ 處所有活動約束的索引集

設 $J=\left \{i:g_i\left ( \hat{x}\right )<0,i \in M\right \}$，其中 J 稱為 $\hat{x}$ 處所有活動約束的索引集。

設 $F_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown f\left ( \hat{x} \right )^T d <0 \right \}$

設 $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gI\left ( \hat{x} \right )^T d <0 \right \}$

或 $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gi\left ( \hat{x} \right )^T d <0 ,\forall i \in I \right \}$

引理

如果 $S=\left \{ x \in X:g_i\left ( x\right ) \leq 0, \forall i \in I\right \}$ 且 X 是 $\mathbb{R}^n$ 中的非空開集。設 $\hat{x}\in S$ 且 $g_i$ 在 $\hat{x}, i \in I$ 處可微，且 $g_i$ 在 $\hat{x}$ 處連續，其中 $i \in J$，則 $G_0 \subseteq D$。

證明

設 $d \in G_0$

由於 $\hat{x} \in X$ 且 X 是開集，因此存在 $\delta_1 >0$ 使得對於 $\lambda \in \left ( 0, \delta_1\right )$，$\hat{x}+\lambda d \in X$

此外，由於 $g_\hat{x}<0$ 且 $g_i$ 在 $\hat{x}, \forall i \in J$ 處連續，因此存在 $\delta_2>0$，$g_i\left ( \hat{x}+\lambda d\right )<0, \lambda \in \left ( 0, \delta_2\right )$

由於 $d \in G_0$，因此，$\bigtriangledown g_i\left ( \hat{x}\right )^T d <0, \forall i \in I$，因此存在 $\delta_3 >0, g_i\left ( \hat{x}+\lambda d\right )< g_i\left ( \hat{x}\right )=0$，對於 $\lambda \in \left ( 0, \delta_3\right ) i \in J$

設 $\delta=min\left \{ \delta_1, \delta_2, \delta_3 \right \}$

因此，$\hat{x}+\lambda d \in X, g_i\left ( \hat{x}+\lambda d\right )< 0, i \in M$

$\Rightarrow \hat{x}+\lambda d \in S$

$\Rightarrow d \in D$

$\Rightarrow G_0 \subseteq D$

證畢。

定理

必要條件

設 f 和 $g_i, i \in I$ 在 $\hat{x} \in S,$ 處可微，且 $g_j$ 在 $\hat{x} \in S$ 處連續。如果 $\hat{x}$ 是 S 的區域性最小值，則 $F_0 \cap G_0=\phi$。

充分條件

如果 $F_0 \cap G_0= \phi$ 且 f 是 $\left (\hat{x}, g_i 9x \right )$ 處的偽凸函式，$i \in I$ 是在 $\hat{x}$ 的某個 $\varepsilon$ - 鄰域上的嚴格偽凸函式，則 $\hat{x}$ 是區域性最優解。

備註

• 設 $\hat{x}$ 是一個可行點，使得 $\bigtriangledown f\left(\hat{x} \right)=0$，則 $F_0 = \phi$。因此，$F_0 \cap G_0= \phi$，但 $\hat{x}$ 不是最優解

• 但如果 $\bigtriangledown g\left(\hat{x} \right)=0$，則 $G_0=\phi$，因此 $F_0 \cap G_0= \phi$

• 考慮問題：min $f\left(x \right)$ 使得 $g\left(x \right)=0$。

  由於 $g\left(x \right)=0$，因此 $g_1\left(x \right)=g\left(x \right)<0$ 且 $g_2\left(x \right)=-g\left(x \right) \leq 0$。

  設 $\hat{x} \in S$，則 $g_1\left(\hat{x} \right)=0$ 且 $g_2\left(\hat{x} \right)=0$。

  但 $\bigtriangledown g_1\left(\hat{x} \right)= - \bigtriangledown g_2\left(\hat{x}\right)$

  因此，$G_0= \phi$ 且 $F_0 \cap G_0= \phi$。