凸优化 - 规划问题

上一页
下一页

有四种类型的凸规划问题：

步骤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$。

打印页面
上一页
下一页
广告