04-典型的凸优化问题

1 凸优化问题

凸优化问题

标准形式的凸优化问题

\begin{array}{ll}
\min _{x \in D} & f(x) \\
\text { s.t. } & g_i(x) \leq 0, \quad i=1, \ldots, m \\
& A x=b
\end{array}

• 目标函数f、不等式约束条件g_i都是凸函数，必须是Ax=b
• 定义域D=\text{dom }f\cap (\cap_{i=1}^m\text{dom }g_i)通常省略
• 可行域为X=D\cap\{x\mid g_i(x)\leq 0,i=1,2,\cdots,m,Ax=b\}

注意定义域和可行域的区别。可行域是定义域交上约束条件的集合。

若X_{\text{opt}}为下面凸优化问题的解集，即

\begin{align}
X_{\text{opt}}=\operatorname*{argmin}_x\quad &f(x)\\
\text{s.t.}\quad &g_i(x)\leq 0,\quad i=1,...,m\\
&Ax=b
\end{align}

• 其中X_{\text{opt}}是凸集.

• 若f是严格凸函数，则凸优化问题的解唯一，即X_\text{opt}只有一个元素

------------------------------------------

------------------------------------------

局部和全局最优

凸优化问题的任意局部最优解都是全局最优解

证明采用反证法证明矛盾

可微凸优化问题的最优性条件

x是凸优化问题\min_{x\in X} f(x)的最优解当且仅当x可行且满足：

\nabla f(x)^\top(y-x)\geq 0,\quad \forall y\in X.

我的理解：在这个可行域内任何一个方向都和正梯度方向呈锐角或直角（大于等于0），也就是无法再下降

几何解释：与-\nabla f(x)（负梯度）呈锐角的方向都是下降方向。任取y\in X，-\nabla f(x)与y-x呈钝角，即内积 \langle y-x,-\nabla f(x)\rangle \leq 0.提出一个负号即是上式。若存在y\in X使得-\nabla f(x)与y-x呈锐角，那说明还能够继续下降，在可行域X还能找到比x更优的解。

如果\nabla f(x)非零，它定义了可行域X在x处的支撑超平面，即再也无法下降。

具体含义

无约束优化：x是最优解当且仅当

x\in \text{dom }f,\quad \nabla f(x)=0

等式约束优化问题：

\min_x \quad f(x) \quad \text{ s.t.}  \quad Ax=b

x是最优解当且仅当存在v使得

x\in \text{dom } f,\ Ax=b,\ \nabla f(x)+A^\top v=0

注意这里的A

A=\begin{pmatrix}
a_1^\top  \\
a_2^\top  \\
\vdots \\
a_n^\top 
\end{pmatrix},A^\top=(a_1,a_2,\cdots,a_n)\\
\nabla f(x)=A^Tv=\sum_{i=1}^n a_i\cdot v_i

非负约束优化问题：

\min_x \quad f(x) \quad \text{s.t.}  \quad x\geq 0

x是最优解当且仅当

x\in \text{dom }f,\quad x\geq 0,\quad 
\begin{cases}
\nabla f(x)_i\geq 0 &x_i=0\\
\nabla f(x)_i=0&x_i>0
\end{cases}