优化03优化导论和无约束问题的最优条件

2024-03-01 13:48:10

优化导论和无约束问题的最优条件

优化导论和无约束问题的最优条件

1 优化问题的类型

无约束最优化问题:

\[\begin{align*} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~ ~ ~x ∈ X ⊆ R^n \end{align*} \]

约束优化问题:

\[\begin{align*} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~~ ~ f_i(x) \leq 0,~ i = 1, \ldots, m\\ &~ ~ ~ g_j(x) = 0, j = 1,~ \ldots, p\\ &~ ~ ~ x ∈ X ⊆ R^n \end{align*} \]

其中向量 $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）.

优化问题的形式如下：

\[\begin{align*}（P）~ ~ ~\min &~ ~ ~ f(x)\\ \text{s.t.} &~~ ~ g_i(x) \leq 0,~ i = 1, \ldots, m\\ &~ ~ ~ h_j(x) = 0, j = 1,~ \ldots, p\\ &~ ~ ~ x \in R^n \end{align*} \]

其中向量 $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）.

2局部、全局和严格优化

圆心为x，半径为$\varepsilon$的球:

\[B(\bar{x}, \varepsilon) := \{x| ~ ~ || x-\bar{x} ||≤ \varepsilon\}. \]

考虑以下关于集合F的优化问题

\[\begin{align*}（P）~ ~ ~min~ ~ or ~ ~max &~ ~ ~ f(x)\\ \text{s.t.} &~~ ~ x \in F ⊆ R^n\\ \end{align*} \]

我们有以下局部/全局、非严格极小/极大值的定义

$\large\color{#70f3ff}{\boxed{\color{brown}{定义2.1} }}$ 对于所有的$y∈B({x}, \varepsilon)∩F$，若存在可使其$F (x)≤F (y)$，则$x∈F$为$(P)$的局部最小值。

$\large\color{#70f3ff}{\boxed{\color{brown}{定义2.2} }}$对于所有$y∈F$，如果$F (x)≤F (y)$，则$x∈F$是$(P)$的全局最小值。

$\large\color{#70f3ff}{\boxed{\color{brown}{定义2.3} }}$ 对于所有的$y∈B({x}, \varepsilon)∩F，y\neq x$，若存在可使其$F (x)<F (y)$，则$x∈F$为$(P)$的严格局部最小值。

$\large\color{#70f3ff}{\boxed{\color{brown}{定义2.4} }}$对于所有$y∈F,y\neq x$，如果$F (x)<F (y)$，则$x∈F$是$(P)$的严格全局最小值。

$\large\color{#70f3ff}{\boxed{\color{brown}{定义2.5} }}$ 如果有领域$B({x}, \varepsilon)$ ，其中$x$是 $B({x}, \varepsilon)∩F$唯一的局部极小值,则 $x∈F$是孤立局部最小值

所有孤立局部最小值都是严格的。

严格最小值并不总是孤立的。

以函数为例

\[f(x)=\left\{\begin{array}{rll} x^{4} \cos \left(\frac{1}{x}\right)+2 x^{4}, & \text { if } & x \neq 0 \\ 0, & \text { if } & x=0 \end{array}\right. \]

$x=0$ 是一个严格的局部极小值。然而，存在严格的局部极小化在许多邻近的点 $x_{k}=\frac{2}{4 k \pi+3 \pi}$ 上我们可以标记这些点 $x_{k} \rightarrow 0, k \rightarrow \infty$.

最优化的大部分都与最优解的存在性，最优解的表征(特征)，以及计算最优解的算法有关。

Example 1:

\[\begin{array}{ll} \min & \frac{1+x}{2 x} \\ \text { s.t. } & x \geq 1 . \end{array} \]

这里没有最优解，因为可行域是*的。

Example 2 :

\[\begin{array}{ll} \min & \frac{1}{x} \\ \text { s.t. } & 1 \leq x<2 \end{array} \]

这里不存在最优解，因为可行域不是封闭的。

Example 3 :

\[\begin{array}{ll} \min & f(x) \\ \text { s.t. } & 1 \leq x \leq 2 \end{array} \]

这里

\[f(x)=\left\{\begin{array}{ll} \frac{1}{x}, & x<2 \\ 1, & x=2 \end{array}\right. \]

这里没有最优解，因为函数$f(\cdot)$不是足够光滑的(甚至不是连续的)。

$\large\color{magenta}{\boxed{\color{brown}{定理1} }}$ (序列的Weierstrass’ 定理) 令 $\left\{x_{k}\right\}, k \rightarrow \infty$ 是一个无穷序列，其中的点在紧凑（即封闭和有界）的集合$\mathcal{F}$. 然后点$x_{k_{j}}$的若干无限子序列收敛到$\mathcal{F}$中包含的点。

$\large\color{magenta}{\boxed{\color{brown}{定理2} }}$ (函数的Weierstrass’ 定理)设$f(x)$ 在紧凑空集合 $\mathcal{F} \subseteq R^{n}$上的一个连续实值函数，则$\mathcal{F}$包含一个点，使$f(x)$在集合$\mathcal{F}$上最小(最大化)。

3梯度和Hessian 黑塞矩阵和方向导数

$\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$，

\[f(x) = f(\bar{x}) + ∇f(\bar{x})^T (x − \bar{x}) + ||x − \bar{x}||α(\bar{x},x − \bar{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 f = \begin{pmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots \\ \frac{\partial f}{\partial x_n} \end{pmatrix} \\ \]

也经常写为算子形式 $\nabla_{\boldsymbol{}}$ :

\[\nabla_{\boldsymbol{}} \overset{\underset{\mathrm{}}{}}{=} \left[ \frac{\partial }{\partial x_1}, \frac{\partial }{\partial x_2},\cdots,\frac{\partial }{\partial x_n} \right]^T \\ \]

梯度的近似：$f(\vec{x}) \approx f(\vec{x}_0) + \nabla f(\vec{x}_0) \cdot (\vec{x} - \vec{x}_0) \\$,注意梯度是一个数值。

梯度的散度就是 Laplacian；
梯度的 Jacobian 就是 Hessian。

梯度与Hessian等多种关系图

$\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) = f(\bar{x}) + ∇f(\bar{x})^T (x − \bar{x}) + \frac{1}{2}(x − \bar{x})^TH(\bar{x})(x − \bar{x})+ ||x − \bar{x}||^2α(\bar{x},x − \bar{x}), \]

和 $\lim_{y\rightarrow 0}α(\bar{x},y)=0$.

如果$f(x)$对所有$\bar{x}∈X$都是2阶可微的,$f(x)$在$X$上是2阶可微的。

Hessian是二阶偏导数的矩阵,对于$f: \mathbb{R}^n \to \mathbb{R}$:

\[{\displaystyle \mathbf {H} ={\begin{bmatrix}{\frac {\partial ^{2}f}{\partial x_{1}^{2}}}&{\frac {\partial ^{2}f}{\partial x_{1}\,\partial x_{2}}}&\cdots &{\frac {\partial ^{2}f}{\partial x_{1}\,\partial x_{n}}}\\\\{\frac {\partial ^{2}f}{\partial x_{2}\,\partial x_{1}}}&{\frac {\partial ^{2}f}{\partial x_{2}^{2}}}&\cdots &{\frac {\partial ^{2}f}{\partial x_{2}\,\partial x_{n}}}\\\\\vdots &\vdots &\ddots &\vdots \\\\{\frac {\partial ^{2}f}{\partial x_{n}\,\partial x_{1}}}&{\frac {\partial ^{2}f}{\partial x_{n}\,\partial x_{2}}}&\cdots &{\frac {\partial ^{2}f}{\partial x_{n}^{2}}}\end{bmatrix}}\,} \\ \]

一个$n×n$对称矩阵$H({x})$ ,写成：${\displaystyle \mathbf {H}_{ij}={\frac {\partial ^{2}f}{\partial x_{i}\partial x_{j}}}} \\$.

偏导数只能描绘$x，y$方向上函数的变化率，但是在实际的使用过程中，我们想知道函数在各个方向上的变化率，于是就有了方向导数的概念。

$\large\color{#70f3ff}{\boxed{\color{brown}{方向导数 } }}$函数f(x) 在$x_0$处d方向上的方向导数为:

\[f'(x_0; d) = \lim_{λ\rightarrow 0} \frac{f(x_0 + λd) − f(x_0)}{λ} = ∇f(x_0)^T d \]

方向导数是一个标量，方向导数定义了点 $x_0$处沿向量 $λ$ 方向变化时，对应的函数的瞬时变化率。

$\large\color{magenta}{\boxed{\color{brown}{定理3} }}$ (泰勒定理) $f: R^{n} \rightarrow R$ 是连续可微的，和 $d \in R^{n}$. 然后我们有

\[f(x+d)=f(x)+\nabla f(x+t d)^{T} d \]

其中 $t \in(0,1)$. 而且，如果$f$是连续可微的，我们有

\[f(x+d)=f(x)+\nabla f(x)^{T} d+\frac{1}{2} d^{T} \nabla^{2} f(x+t d) d \]

其中 $t \in(0,1)$ 。

链式求导法则：

\[\varphi(t)=f(x+t d)=f\left(x_{i}+t d_{i}, \ldots, x_{n}+t d_{n}\right)=f\left(\varphi_{1}(t), \ldots, \varphi_{n}(t)\right) \]

\[\begin{array}{l} \varphi^{\prime}(t)=\sum_{i=1}^{n} \frac{\partial f(x+t d)}{\partial \varphi_{i}(t)} \frac{d \varphi_{i}(t)}{d t}=\nabla f(x+t d)^{T} d \\ \varphi^{\prime \prime}(t)=\frac{d}{d t}\left(\nabla f(x+t d)^{T} d\right)=d^{T} \nabla^{2} f(x+t d) d \end{array} \]

4无约束问题的最优条件

考虑以下优化问题:

\[\begin{align*} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~ ~ ~x ∈ X ⊆ R^n \end{align*} \]

$\large\color{#70f3ff}{\boxed{\color{brown}{定义4.1} }}$如果$f(x_0 + λd)< f(x_0)$对于所有的$λ>0$且$λ$足够小,那么$d$方向称为$f(x)$在$x = x_0$时的下降方向.

局部最优性的一个必要条件是这样的表述:“如果x是(P)的一个局部最小值，那么x必须满足……”这样的条件帮助我们确定所有的候选局部最优。

局部最优性的一个充分条件是这样的表述:“if x满足…”，则x是(P)的局部最小值”。这样的条件允许我们自动声明x确实是一个局部优化。

$\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$时的下降方向.

【证明】: 我们有

\[f(\bar{x}+\lambda d)=f(\bar{x})+\lambda \nabla f(\bar{x})^{T} d+\lambda\|d\| \alpha(\bar{x}, \lambda d) \]

其中 $\lim _{\lambda \rightarrow 0} \alpha(\bar{x}, \lambda d)=0 .$ 重整理

\[\frac{f(\bar{x}+\lambda d)-f(\bar{x})}{\lambda}=\nabla f(\bar{x})^{T} d+\|d\| \alpha(\bar{x}, \lambda d) \]

因为 $\nabla f(\bar{x})^{T} d<0$ 和 $\lim _{\lambda \rightarrow 0} \alpha(\bar{x}, \lambda d)=0,$ 就有$f(\bar{x}+\lambda d)<f(\bar{x})$ 对于 $\lambda>0$ 和足够小。

$\large\color{#70f3ff}{\boxed{\color{brown}{定理4.2} }}$ 一阶必要最优性条件

假设f(x)在$x_0$处是可微的，如果$x_0$是局部最小值，那么$∇f(x_0) = 0$。
假设f(x)在$x_0$处是可微的，如果$x_0$是局部最小值, $\textbf{d}$ 为 $\textbf{x}_{0}$ 处的可行方向，则 $\forall \textbf{d} , \textbf{d}^{\mathrm{T}}\nabla{f}(\textbf{x}_{0}) \geq 0$

$\large\color{#70f3ff}{\boxed{\color{brown}{定理4.3} }}$二阶必要最优性条件

假设f(x)在$x_0$处是二阶可微的，如果$x_0$是局部最小值，那么$∇f(x_0) = 0$和$H(x_0)$是正半定的。
如果$x^*$是局部最小值,$\textbf{x}^{*}$ 为内点或边界点， $\textbf{d}$ 为 $\textbf{x}^{*}$ 处的可行方向，且 $\textbf{d}^{\mathrm{T}}\nabla{f}(\textbf{x}^{*}) \geq 0$ ，则 $\textbf{d}^{\mathrm{T}}\textbf{F}(\textbf{x}^{*})\textbf{d} \geq 0$ ；

$\large\color{#70f3ff}{\boxed{\color{brown}{定理4.4} }}$二阶充分最优性条件

假设f(x)在$x_0$处是二阶可微的,如果$∇f(x_0) = 0$和$H(x_0)$是正定的，那么$x_0$是一个(严格的)局部最小值。

$\Large\color{violet}{注:}$

上述定理的二阶充分条件保证比前面讨论的必要条件更强;即，该最小值是一个严格的局部最小值。

还要注意，二阶充分条件不是必需的:点$x^∗$可能是一个严格的局部最小值，但是可能不能满足充分条件。

一个简单的例子

\[f(x)=x^{4} \]

其中，$x^{*}=0$是Hessian矩阵消失的严格极小化点(因此不是正定)。

$\large\color{#70f3ff}{\boxed{\color{brown}{定理4.5} }}$假设 $f(\cdot): R^{n} \rightarrow R$ 连续可微在集合 $S=\left\{x \in R^{n} \mid f(x)<f\left(x^{0}\right)\right\}$ 上， $S$ 是一个封闭有界的集合. ，那么每一个点 $\bar{x}$ 是序列$\left\{x^{k}\right\}$ 的聚类点都满足$\nabla f(\bar{x})=0$

【证明】这个证明是自相矛盾的。由Weierstrass’定理, 令 $\bar{x}$ 是序列$\left\{x^{k}\right\}$ 的聚类点。不失一般性，假设$\lim _{k \rightarrow \infty} x^{k}=\bar{x},$ 其中 $\nabla f(\bar{x})=-\bar{d} \neq 0 .$ 然后，有一个值$\bar{\alpha}>0$使得

\[\delta:=f(\bar{x})-f(\bar{x}+\bar{\alpha} \bar{d})>0 \]

这时同样$(\bar{x}+\alpha \bar{d}) \in$ int $S$. 则 $\lim _{k \rightarrow \infty} d^{k}=\bar{d}$. 那么$\lim _{k \rightarrow \infty}\left(x^{k}+\bar{\alpha} d^{k}\right)=(\bar{x}+\bar{\alpha} \bar{d}),$ 对于$k$足够大，和

\[f\left(x^{k}+\bar{\alpha} d^{k}\right) \leq f(\bar{x}+\bar{\alpha} \bar{d})+\frac{\delta}{2}=f(\bar{x})-\delta+\frac{\delta}{2}=f(\bar{x})-\frac{\delta}{2} \]

不管怎样，

\[f(\bar{x})<f\left(x^{k}+\alpha_{k} d^{k}\right) \leq f\left(x^{k}+\bar{\alpha} d^{k}\right) \leq f(\bar{x})-\frac{\delta}{2} \]

这当然是矛盾的。因此$\nabla f(\bar{x})=0$.

Example 1:

令

\[f(x)=\frac{1}{2} x_{1}^{2}+x_{1} x_{2}+2 x_{2}^{2}-4 x_{1}-4 x_{2}-x_{2}^{3} \]

寻找局部极小值可能的候选者。

解决方案:

\[\begin{array}{c} \nabla f(x)=\left(x_{1}+x_{2}-4, x_{1}+4 x_{2}-4-3 x_{2}^{2}\right)^{T} \\ H(x)=\left(\begin{array}{cc} 1 & 1 \\ 1 & 4-6 x_{2} \end{array}\right) \end{array} \]

让 $\nabla f(x)=0,$ 有

\[\bar{x}=(4,0)^{T}, \widetilde{x}=(3,1)^{T}, H(\bar{x})=\left(\begin{array}{cc} 1 & 1 \\ 1 & 4 \end{array}\right) \succeq 0, H(\widetilde{x})=\left(\begin{array}{cc} 1 & 1 \\ 1 & -2 \end{array}\right) \]

所以，可能的候选者 $\bar{x}=(4,0)^{T}$ 。

Example 2:

令

\[f(x)=x_{1}^{4}+x_{2}^{2} \]

求$f(x)$的局部最小值。

解决方案:

\[\nabla f(x)=\left(4 x_{1}^{3}, 2 x_{2}\right)^{T}, H(x)=\left(\begin{array}{cc} 12 x_{1}^{2} & 0 \\ 0 & 2 \end{array}\right) \]

让 $\nabla f(x)=0,$ 有

\[\bar{x}=(0,0)^{T}, H(\bar{x})=\left(\begin{array}{cc} 0 & 0 \\ 0 & 2 \end{array}\right) \succeq 0 \]

而$\bar{x}=(0,0)^{T}$是局部最小值则很容易知道。

Example 3:

令

\[f(x)=x_{1}^{3}+x_{2}^{2} \]

求$f(x)$的局部最小值。

解决方案:

\[\nabla f(x)=\left(3 x_{1}^{2}, 2 x_{2}\right)^{T}, H(x)=\left(\begin{array}{cc} 6 x_{1} & 0 \\ 0 & 2 \end{array}\right) \]

让 $\nabla f(x)=0,$ 有

\[\bar{x}=(0,0)^{T}, H(\bar{x})=\left(\begin{array}{cc} 0 & 0 \\ 0 & 2 \end{array}\right) \succeq 0 \]

而$\bar{x}=(0,0)^{T}$是局部最小值则很容易知道。

Example 4:

令

\[f(x)=\left(x_{1}^{2}-1\right)^{2}+x_{1}^{2}+2 x_{2}^{2}-2 x_{1} \]

求$f(x)$的局部最小值。

解决方案:

\[\nabla f(x)=\left(4\left(x_{1}^{2}-1\right) x_{1}+2 x_{1}-2,4 x_{2}\right)^{T}, H(x)=\left(\begin{array}{cc} 12 x_{1}^{2}-2 & 0 \\ 0 & 4 \end{array}\right) \]

让 $\nabla f(x)=0,$ 有

\[\bar{x}=(1,0)^{T}, H(\bar{x})=\left(\begin{array}{cc} 10 & 0 \\ 0 & 4 \end{array}\right) \succ 0 \]

因此， $\bar{x}=(1,0)^{T}$ 是一个严格的局部最小值。

5 凸性和最小化

凸集：

凸函数：

标准形式的凸优化问题：

\[\begin{align*} (CP) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~~ ~ f_i(x) \leq 0,~ i = 1, \ldots, m\\ &~ ~ ~ g_j(x) = 0, j = 1,~ \ldots, p\\ &~ ~ ~ x ∈ X \end{align*} \]

其中，

目标函数 $f(x) $是凸函数。
不等式约束 $f_i(x)$ 是凸函数。
等式约束 $g_i(x) = a_i^Tx - b_i $是仿射函数。

对于凸优化问题，定义域记作 $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$是凸集，$f (x): X→R$是凸函数，$x'$是(CP)的局部最小值。那么$x'$是$f(x)$ 的全局最小值。

证明：

凸函数：定义域 $dom\,f$ 是凸集，对于 $x,y\in f, \theta\leq 1$ ，

\[f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y) \]

假设$x^* $是凸函数f 的全局最优解；如果 $x^* $是局部最优解，那么必存在 $\bar x \ne x^*$ 使得 $f(\bar x) \leq f(x^*) $。根据凸函数的定义：

\[\begin{split} f(\theta \bar x+ (1- \theta) x^*) &\leq \theta f(\bar x) + (1-\theta) f(x^*) \\ &\leq \theta f(x^*) + (1 - \theta) f(x^*) \\ & \leq f(x^*) \end{split} \]

也就是说，位于 $\bar x $和$ x^* $之间的线段上的函数值都小于$ f(x^)$ ，这与$x^ $是局部最优解矛盾，因此 $x^*$只能是全局最优解。

结论：

如果f(x)是严格凸的，那么局部最小值就是唯一的全局最小值。
如果f(x)是凹的，局部最大值就是全局最大值
如果f(x)是严格凹的，局部最大值是唯一的全局最大值。

$\large\color{#70f3ff}{\boxed{\color{brown}{定理5.2} }}$ 假设$X$是一个非空开凸集，$f(x): X→R$是可微的。则$f(x)$是凸函数的充分必要条件是$f(x)$满足以下梯度不等式:

\[f(y) ≥ f(x) + ∇f(x)^T (y − x), ∀x, y ∈ 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$。

这些结果(包括第一和第二种条件)为无约束优化算法提供了基础:所有算法都以某种方式寻找$∇f(x^*) = 0$的点。

为什么限定凸优化问题

求解一个一般性的最优化问题的全局极小值是非常困难的，至少要面临的问题是：函数可能有多个局部极值点，另外还有鞍点问题。对于第一个问题，我们找到了一个梯度为0的点，它是极值点，但不是全局极值，如果一个问题有多个局部极值，则我们要把所有局部极值找出来，然后比较，得到全局极值，这非常困难，而且计算成本相当高。第二个问题更严重，我们找到了梯度为0的点，但它连局部极值都不是，典型的是 $X^3$ 这个函数，在0点处，它的导数等于0，但这根本不是极值点：

梯度下降法和牛顿法等基于导数作为判据的优化算法，找到的都导数/梯度为0的点，而梯度等于0只是取得极值的必要条件而不是充分条件。如果我们将这个必要条件变成充分条件，即：

问题将会得到简化。如果对问题加以限定，是可以保证上面这个条件成立的。其中的一种限制方案是：对于目标函数，我们限定是凸函数；对于优化变量的可行域（注意，还要包括目标函数定义域的约束），我们限定它是凸集。

同时满足这两个限制条件的最优化问题称为凸优化问题，这类问题有一个非常好性质，那就是局部最优解一定是全局最优解。

6 无约束优化算法思想

形式：

\[\begin{align*} (UP) ~ ~ ~ \min &~ ~ ~ f(x)\\ &~ ~ ~ x ∈ X \end{align*} \]

所有无约束最小化算法都要求用户提供一个起点，我们通常用$x^0$来表示这个起点。

了解应用程序和数据集的用户可以很好地选择$x^0$作为解决方案的合理估计。否则，起始点必须由算法选择，可以用系统方法选择，也可以用任意方法选择。

开始$x^0$，优化算法生成终止的迭代器$\{x^k\}$序列,当没有进一步的进展时，或者当解点似乎已经足够精确地接近时。在决定如何从一个迭代$x^k$到下一个迭代时，算法使用关于函数f在$x^k$处的信息，也可能是来自早期迭代器$x^0, x^1，····，x^{k- 1}$的信息。通常关于$f$的信息并不便宜，所以我们通常更喜欢不会不必要地调用这些信息的算法。

他们使用这个信息来找到一个新的迭代$x^{k+ 1}$，其函数值小于$x^k$;非单调算法并不要求f在每一步减小，但即使是这些算法也要求f在给定的迭代次数m之后减小，即$f (x^k) < f (x^{k-m})$ .

基本方案:

Step $0,($ 起步 $) x^{0} \in R^{n}, \varepsilon>0, k=0$
Step 1,(终止准则) 如果$\left\|g^{k}\right\|<\varepsilon .$ 终止.
Step 2,(方向) 寻找 $d^{k}: \nabla f\left(x^{k}\right)^{T} d^{k}<0$.
Step 3,(步长) 线搜索寻找： $\alpha_{k}$.