凸优化 - 编程问题
有四种类型的凸规划问题 -
步骤 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 \右 )$ 是凹函数。
步骤 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 在 S$ 中的点 $\hat{x} \处可微。如果 $\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$ 使得 $d=x-\hat{x}\in D$ 对于任何 $x \in S \cap N_\varepsilon \left ( \hat{x} \right )$，则 $\ 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 \左 ( 0,\delta_2 \右 )$
令 $\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 \在 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 \帽 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 ( \帽子{x} \右)$
假设 $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$
$\右箭头 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,...,米$
$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$ 其中 $i \in J$ 在 $\hat{x 处连续}$，然后$G_0 \subseteq D$。
证明
让 $d \in G_0$
由于 $\hat{x} \in X$ 且 X 是开集，因此存在 $\delta_1 >0$ 使得 $\hat{x}+\lambda d \in X$ 对于 $\lambda \in \左 ( 0, \delta_1\right )$
另外，由于 $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$
$\右箭头 d \in D$
$\右箭头 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$ 是某些 $\varepsilon$ 邻域上的严格伪凸函数$\hat{x}的\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$
考虑这个问题：最小$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\左(x\右)\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$。