凸优化 - 凸规划问题
凸规划问题有四种类型 −
步骤 1 − $min \:f\left ( x ight )$，其中 $x \in S$ 且 S 是 $\mathbb{R}^n$ 中的非空凸集，$f\left ( x ight )$ 是凸函数。
步骤 2 − $min \: f\left ( x ight ), x \in \mathbb{R}^n$ 服从
$g_i\left ( x ight ) \geq 0, 1 \leq m_1$ 且 $g_i\left ( x ight )$ 为凸函数。
$g_i\left ( x ight ) \leq 0,m_1+1 \leq m_2$ 且 $g_i\left ( x ight )$ 为凹函数。
$g_i\left ( x ight ) = 0, m_2+1 \leq m$ 且 $g_i\left ( x ight )$ 为线性函数。
其中 $f\left ( x ight )$ 为凸函数。
步骤3 − $max \:f\left ( x ight )$ 其中 $x \in S$ 且 S 是 $\mathbb{R}^n$ 中的非空凸集，而 $f\left ( x ight )$ 是凹函数。
步骤 4 − $min \:f\left ( x ight )$，其中 $x \in \mathbb{R}^n$ 服从
$g_i\left ( x ight ) \geq 0, 1 \leq m_1$ 且 $g_i\left ( x ight )$ 为凸函数。
$g_i\left ( x ight ) \leq 0, m_1+1 \leq m_2$ 且 $g_i\left ( x ight )$ 为凹函数。
$g_i\left ( x ight ) = 0,m_2+1 \leq m$ 且 $g_i\left ( x ight )$ 为线性函数。
其中 $f\left ( x ight )$ 为凹函数。
可行锥方向
设 S 为 $\mathbb{R}^n$ 中的非空集，且 $\hat{x} \in \:Closure\left ( S ight )$，则 S 在 $\hat{x}$ 处的可行方向锥用 D 表示，定义为 $D=\left \{ d:d eq 0,\hat{x}+\lambda d \in S, \lambda \in \left ( 0, \delta ight ), \delta > 0 ight \}$
每个非零向量 $d \in D$ 称为可行方向。
对于给定函数 $f:\mathbb{R}^n \Rightarrow \mathbb{R}$，在 $\hat{x}$ 处的改进方向锥用 F 表示，并给出
$$F=\left \{ d:f\left ( \hat{x}+\lambda d ight )\leq f\left ( \hat{x} ight ),\forall \lambda \in \left ( 0,\delta ight ), \delta >0 ight \}$$
每个方向 $d \in F$ 称为 f 在 $\hat{x}$ 处的改善方向或下降方向
定理
必要条件
考虑问题 $min f\left ( x ight )$，使得 $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} ight )^T d < 0 ight \}$ 且 D 是可行方向锥。
充分条件
如果 $F_0 \cap D= \phi$ f 在 $\hat{x}$ 处为伪凸函数，且存在 $\hat{x},N_\varepsilon \left ( \hat{x} ight ), \varepsilon > 0$ 的邻域，使得对于任意 $x \in S \cap N_\varepsilon \left ( \hat{x} ight )$，$d=x-\hat{x}\in D$，则 $\hat{x}$ 为局部最优解解。
证明
必要条件
设 $F_0 \cap D eq \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 ight )。$
由于 $d \in F_0$，因此 $\bigtriangledown f \left ( \hat{x} ight )^T d <0$
因此，存在 $\delta_2>0$ 使得 $f\left ( \hat{x}+\lambda d ight )< f\left ( \hat{x} ight ),\forall \lambda \in f \left ( 0,\delta_2 ight )$
设 $\delta=min \left \{\delta_1,\delta_2 ight \}$
则 $\hat{x}+\lambda d \in S, f\left (\hat{x}+\lambda d ight ) < f\left ( \hat{x} ight ),\forall \lambda \in f \left ( 0,\delta ight )$
但$\hat{x}$是局部最优解。
因此是矛盾的。
因此$F_0\cap D=\phi$
充分条件
设$F_0 \cap D eq \phi$，设f为伪凸函数。
设存在$\hat{x}, N_{\varepsilon}\left ( \hat{x} ight )$的邻域，使得$d=x-\hat{x}, \forall x \in S \cap N_\varepsilon\left ( \hat{x} ight )$
设$\hat{x}$不是局部最优解。
因此存在$\bar{x} \in S \cap N_\varepsilon \left ( \hat{x} ight )$ 使得 $f \left ( \bar{x} ight )< f \left ( \hat{x} ight )$
根据对 $S \cap N_\varepsilon \left ( \hat{x} ight ) 的假设，d=\left ( \bar{x}-\hat{x} ight )\in D$
根据 f 的伪凸性，
$$f\left ( \hat{x} ight )>f\left ( \bar{x} ight )\Rightarrow \bigtriangledown f\left ( \hat{x} ight )^T\left ( \bar{x}-\hat{x} ight )<0$$
$\Rightarrow \bigtriangledown f\left ( \hat{x} ight) ^T d <0$
$\Rightarrow d \in F_0$
因此 $F_0\cap D eq \phi$
这是一个矛盾。
因此，$\hat{x}$ 是局部最优解。
考虑以下问题：$min \:f\left ( x ight )$ 其中 $x \in X$ 使得 $g_x\left ( x ight ) \leq 0, i=1,2,...,m$
$f:X ightarrow \mathbb{R},g_i:X ightarrow \mathbb{R}^n$ 并且 X 是$\mathbb{R}^n$
设 $S=\left \{x:g_i\left ( x ight )\leq 0,\forall i ight \}$
设 $\hat{x} \in X$，则 $M=\left \{1,2,...,m ight \}$
设 $I=\left \{i:g_i\left ( \hat{x} ight )=0, i \in M ight \}$，其中 I 称为 $\hat{x}$ 处所有有效约束的索引集
设 $J=\left \{i:g_i\left ( \hat{x} ight )<0,i \in M ight \}$，其中 J 称为 $\hat{x}$ 处所有有效约束的索引集。
设$F_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown f\left ( \hat{x} ight )^T d <0 ight \}$
设 $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gI\left ( \hat{x} ight )^T d <0 ight \}$
或 $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gi\left ( \hat{x} ight )^T d <0 ,\forall i \in I ight \}$
引理
若 $S=\left \{ x \in X:g_i\left ( x ight ) \leq 0, \forall i \in I ight \}$且 X 是 $\mathbb{R}^n$ 中的非空开集。令 $\hat{x}\in S$ 和 $g_i$ 在 $\hat{x}, i \in I$ 处不同，令 $g_i$ 其中 $i \in J$ 在 $\hat{x}$ 处连续，则 $G_0 \subseteq D$。
证明
令 $d \in G_0$
由于 $\hat{x} \in X$ 且 X 为开集，因此存在 $\delta_1 >0$ 使得对于 $\lambda \in \left ( 0, \delta_1 ight )$，$\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 ight )<0, \lambda \in \left ( 0, \delta_2 ight )$
由于 $d \in G_0$，因此，$\bigtriangledown g_i\left ( \hat{x} ight )^T d <0, \forall i \in I$，因此存在 $\delta_3 >0, g_i\left ( \hat{x}+\lambda d ight )< g_i\left ( \hat{x} ight )=0$，对于 $\lambda \in \left ( 0, \delta_3 ight ) i \in J$
设 $\delta=min\left \{ \delta_1, \delta_2, \delta_3 ight \}$
因此，$\hat{x}+\lambda d \in X, g_i\left ( \hat{x}+\lambda d ight )< 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 ight ) 处的伪凸函数，i \in I$ 是 $\hat{x} 某个 $\varepsilon$ - 邻域上的严格伪凸函数，则 \hat{x}$ 是局部最优解。
备注
设 $\hat{x}$ 为可行点，使得 $\bigtriangledown f\left(\hat{x} ight)=0$，则 $F_0 = \phi$。因此，$F_0 \cap G_0= \phi$ 但 $\hat{x}$ 不是最优解
但如果 $\bigtriangledown g\left(\hat{x} ight)=0$，则 $G_0=\phi$，因此 $F_0 \cap G_0= \phi$
考虑问题：最小 $f\left(x ight)$ 使得 $g\left(x ight)=0$。
由于 $g\left(x ight)=0$，因此 $g_1\left(x ight)=g\left(x ight)<0$ 且 $g_2\left(x ight)=-g\left(x ight) \leq 0$。
设 $\hat{x} \in S$，则$g_1\left(\hat{x} ight)=0$ 且 $g_2\left(\hat{x} ight)=0$。
但 $\bigtriangledown g_1\left(\hat{x} ight)= - \bigtriangledown g_2\left(\hat{x} ight)$
因此，$G_0= \phi$ 且 $F_0 \cap G_0= \phi$。
