无约束最优化问题:
约束优化问题:
其中向量 $x=(x_1,...,x_n) $称为优化问题的变量（optimization variables），函数 $f:\quad \textbf{R}^n \rightarrow \textbf{R} $为目标函数（objective function），函数 $f_i,g_j: \quad \textbf{R}^n \rightarrow \textbf{R} $称为约束函数（constraint functions）.
优化问题的形式如下：
其中向量 \(x=(x_1,...,x_n)\) 称为优化问题的变量（optimization variables），函数 $f(x):\quad \textbf{R}^n \rightarrow \textbf{R} $为目标函数（objective function），m个函数 $g_i(x),h_j(x): \quad \textbf{R}^n \rightarrow \textbf{R} $称为约束函数（constraint functions）.
圆心为x，半径为\(\varepsilon\)的球:
考虑以下关于集合F的优化问题
我们有以下局部/全局、非严格极小/极大值的定义
\(\large\color{#70f3ff}{\boxed{\color{brown}{定义1.1} }}\) 对于所有的\(y∈B({x}, \varepsilon)∩F\)，若存在可使其\(F (x)≤F (y)\)，则\(x∈F\)为\((P)\)的局部最小值。
\(\large\color{#70f3ff}{\boxed{\color{brown}{定义1.2} }}\)对于所有\(y∈F\)，如果\(F (x)≤F (y)\)，则\(x∈F\)是\((P)\)的全局最小值。
\(\large\color{#70f3ff}{\boxed{\color{brown}{定义1.3} }}\) 对于所有的\(y∈B({x}, \varepsilon)∩F，y\neq x\)，若存在可使其\(F (x)<F (y)\)，则\(x∈F\)为\((P)\)的严格局部最小值。
\(\large\color{#70f3ff}{\boxed{\color{brown}{定义1.4} }}\)对于所有\(y∈F,y\neq x\)，如果\(F (x)<F (y)\)，则\(x∈F\)是\((P)\)的严格全局最小值。
\(\large\color{#70f3ff}{\boxed{\color{brown}{梯度} }}\)令\(f(x): X→R\)，其中开集\(x?R^n\)。如果存在向量$?f(\bar{x}) \((f(x)的梯度)，那么\)f(x)\(在\)\bar{x}∈X\(时是可微的，使得对于每个\){x}∈X$，
\(\lim_{y\rightarrow 0}α(\bar{x},y)=0\).
f(x)在\(X\)上是可微的，如果\(f(x)\)对所有\(\bar{x}∈X\)都是可微的。
梯度针对多元函数 \(f: \mathbb{R}^n \to \mathbb{R}\) ，是导数的推广， 它的结果是一个向量：
也经常写为算子形式 \(\nabla_{\boldsymbol{}}\) :
梯度的近似：\(f(\vec{x}) \approx f(\vec{x}_0) + \nabla f(\vec{x}_0) \cdot (\vec{x} - \vec{x}_0) \\\),注意梯度是一个数值。
\(\large\color{#70f3ff}{\boxed{\color{brown}{Hessians } }}\)如果存在一个向量$?f(\bar{x}) \(和一个\)n×n\(对称矩阵\)H(\bar{x})$ (\(f(\bar{x})\)的Hessian))，那么函数f(x)在\(\bar{x}∈X\)时是2阶可微，使得对于每个\({x}∈X\)，
如果\(f(x)\)对所有\(\bar{x}∈X\)都是2阶可微的,f(x)在\(X\)上是2阶可微的。
Hessian是二阶偏导数的矩阵,对于\(f: \mathbb{R}^n \to \mathbb{R}\):
一个\(n×n\)对称矩阵\(H({x})\) ,写成：\({\displaystyle \mathbf {H}_{ij}={\frac {\partial ^{2}f}{\partial x_{i}\partial x_{j}}}} \\\).
\(\large\color{#70f3ff}{\boxed{\color{brown}{方向导数 } }}\)函数f(x) 在\(x_0\)处d方向上的方向导数为:
考虑以下优化问题:
\(\large\color{#70f3ff}{\boxed{\color{brown}{定义4.1} }}\)如果\(f(x_0 + λd)< f(x_0)\)对于所有的\(λ>0\)且λ足够小,那么\(d\)方向称为\(f(x)\)在\(x = x_0\)时的下降方向.
局部最优性的一个必要条件:
\(\large\color{#70f3ff}{\boxed{\color{brown}{定理4.1} }}\) 假设f(x)在\(x_0\)处是可微的，如果有一个向量\(d\)使得\(?f(x_0)^T d < 0\)，有\(f(x_0 + λd)< f(x_0)\)对于所有的\(λ>0\)且λ足够小，那么\(d\)方向称为\(f(x)\)在\(x = x_0\)时的下降方向.
\(\large\color{#70f3ff}{\boxed{\color{brown}{定理4.2} }}\) 一阶必要最优性条件
假设f(x)在\(x_0\)处是可微的，如果\(x_0\)是局部最小值，那么\(?f(x_0) = 0\)。
\(\large\color{#70f3ff}{\boxed{\color{brown}{定理4.3} }}\)二阶必要最优性条件
假设f(x)在\(x_0\)处是二阶可微的，如果\(x_0\)是局部最小值，那么\(?f(x_0) = 0\)和\(H(x_0)\)是正半定的。
\(\large\color{#70f3ff}{\boxed{\color{brown}{定理4.3} }}\)二阶充分最优性条件
假设f(x)在\(x_0\)处是二阶可微的,如果\(?f(x_0) = 0\)和\(H(x_0)\)是正定的，那么\(x_0\)是一个(严格的)局部最小值。
凸集：
凸函数：
标准形式的凸优化问题：
其中，
对于凸优化问题，定义域记作 $X = \bigcap_{i=0}^m \mathrm{dom}(f_i) \cap \bigcap_{i=1}^p \mathrm{dom}(g_i) $，最优解记作 \(x^* = \arg\min_{x \in X} f(x)\) ，最优值记作 \(p^* = f(x^*)\) 。
\(\large\color{#70f3ff}{\boxed{\color{brown}{定理5.1} }}\) 凸优化问题中，\(x‘\)是(CP)的局部最小值。那么\(x‘\)是f(x) 的全局最小值。
证明：
凸函数：定义域 \(dom\,f\) 是凸集，对于 \(x,y\in f, \theta\leq 1\) ，
假设$x^* $是凸函数f 的全局最优解；如果 $x^* $是局部最优解，那么必存在 \(\bar x \ne x^*\) 使得 $f(\bar x) \leq f(x^*) $。根据凸函数的定义：
也就是说，位于 $\bar x \(和\) x^* \(之间的线段上的函数值都小于\) f(x^)$ ，这与$x^ $是局部最优解矛盾，因此 \(x^*\)只能是全局最优解。
结论：
\(\large\color{#70f3ff}{\boxed{\color{brown}{定理5.2} }}\) 假设\(X\)是一个非空开凸集，\(f(x): X→R\)是可微的。则\(f(x)\)是凸函数的充分必要条件是\(f(x)\)满足以下梯度不等式:
\(\large\color{#70f3ff}{\boxed{\color{brown}{定理5.3} }}\) 假设\(X\)是一个非空开凸集，\(f(x): X→R\)是二次可微的。\(H(x)\)表示\(f(x)\)的Hessian。那么f(x)是的凸函数充分必要条件是\(H(x)\)对所有\(x∈X\)都是半正定的。
\(\large\color{#70f3ff}{\boxed{\color{brown}{定理5.4} }}\)对于问题(CP)，设\(f(x): X→R\)在\(X\)上是凸可微的，那么\(x^*\in X\)是全局最小的充分必要条件是\(?f(x^*) = 0\)。
https://www.zhihu.com/topic/20312858/hot
MIT凸优化课程
Stephen Boyd的Convex Optimization
《凸优化》，Stephen Boyd等著，王书宁等译
https://www.jianshu.com/p/f00715396c7b
原文：https://www.cnblogs.com/liangjiangjun/p/14022639.html