简说最优化基本算法_耀世-耀世娱乐网络科技媒体工作室

Title
简说最优化基本算法

发布时间：2024-06-10 07:23:34 作者：佚名点击量：

最优化算法为大多数机器学习算法所依赖的基础，因此为了深入理解机器学习算法，应首先了解最优化的基本算法。

“最优化要指在一定条件限制下，选取某种研究方案使目标达到最优的一种方法。”

----百度百科

本文主要从以下几个方面介绍最优化算法：

优化基本知识
无约束优化

最速下降法
共轭方向法
牛顿法
拟牛顿法

有约束优化

线性规划及对偶问题
非线性规划

拉格朗日条件
KKT条件
凸优化

凡是提及优化算法，免不了离不开梯度，黑塞矩阵，方向导数这三个基本概念。

函数 $f: R^{n}\\rightarrow R$ ，则

梯度： $\ abla{f}=(\\frac{\\partial{f}}{\\partial{x_1}}, \\frac{\\partial{f}}{\\partial{x_2}}, \\dots, \\frac{\\partial{f}}{\\partial{x_n}})$
黑塞矩阵： $\ extbf{F(x)}=\\left[ \\begin{array}{ccc}\\frac{\\partial^{2}{f}}{\\partial^{2}{x_1}}{(\ extbf{x})}& \\dots &\\frac{\\partial^{2}{f}}{\\partial{x_n}\\partial{x_1}}{(\ extbf{x})}\\\\ \\vdots & & \\vdots\\\\ \\frac{\\partial^{2}{f}}{\\partial{x_n}\\partial{x_1}}{(\ extbf{x})}& \\dots &\\frac{\\partial^{2}{f}}{\\partial^{2}{x_n}}{(\ extbf{x})}\\end{array}\\right]$
函数 $f$ 在 $\ extbf{x}$ 沿方向 $\ extbf{d}$ 的方向导数为 $\\frac{\\partial{f}}{\\partial{\ extbf{d}}}(\ extbf{x})=\\lim_{a \ o 0}{\\frac{f(\ extbf{x}+ a\ extbf{d})}{a}}=\\frac{\\mathrm{d}}{ \\mathrm{d}a}{f(\ extbf{x}+a\ extbf{d})}|_{a=0}=\ abla{f}\\cdot \ extbf{d}$

极小值点 $\ extbf{x}^{*}$ 的一阶必要条件 (前提为函数 $f$ 为一阶可微)：

$\ extbf{x}^{*}$ 为内点或边界点， $\ extbf{d}$ 为 $\ extbf{x}^{*}$ 处的可行方向，则 $\\forall \ extbf{d}, \ extbf{d}^{\\mathrm{T}}\ abla{f}(\ extbf{x}^{*}) \\geq 0$ ；
$\ extbf{x}^{*}$ 为内点，则 $\ abla{f}(\ extbf{x}^{*})=0$ 。

极小值点 $\ extbf{x}^{*}$ 的二阶必要条件 (前提为函数 $f$ 为二阶可微)：

$\ extbf{x}^{*}$ 为内点或边界点， $\ extbf{d}$ 为 $\ extbf{x}^{*}$ 处的可行方向，且 $\ extbf{d}^{\\mathrm{T}}\ abla{f}(\ extbf{x}^{*}) \\geq 0$ ，则 $\ extbf{d}^{\\mathrm{T}}\ extbf{F}(\ extbf{x}^{*})\ extbf{d}\\geq 0$ ；
$\ extbf{x}^{*}$ 为内点， $\ abla{f}(\ extbf{x}^{*})=0$ ，则 $\\forall \ extbf{d}, \ extbf{d}^{\\mathrm{T}}\ extbf{F}(\ extbf{x}^{*})\ extbf{d}\\geq 0$ ,即 $\ extbf{F}(\ extbf{x}^{*})$ 半正定。

极小值点的二阶充分条件 (前提为函数 $f$ 为二阶可微)：

$\ extbf{x}^{*}$ 为内点，若 $\ abla{f}(\ extbf{x}^{*})=0$ 且 $\ extbf{F}(\ extbf{x}^{*}) > 0$ (正定) ，则 $\ extbf{x}^{*}$ 为 $f$ 的严格局部极小点。

最速下降法（只涉及目标函数的一阶导数）

负梯度方向为函数值下降最快的方向。最速下降法为每次迭代沿着负梯度方向，选取合适的步长，使得目标函数值能够得到最大程度的减小。相邻两次迭代方向垂直，即 $\ abla{f}(\ extbf{x}_{k}) \\bot \ abla{f}(\ extbf{x}_{k+1})$

则最速下降法的迭代公式为：

$\\alpha_{k}=\\mathrm{arg}_{\\alpha_{k}\\geq0}\ ext{ }\\mathrm{min}f(\ extbf{x}_{k}-\\alpha_{k}\ abla{f}(\ extbf{x}_{k}))$
$\ extbf{x}_{k+1}=\ extbf{x}_{k}- \\alpha_{k}\ abla{f}(\ extbf{x}_{k})$

特殊情况：对于目标函数为二次型函数的情况，即 $f(\ extbf{x})=\\frac{1}{2}\ extbf{x}^{T}\ extbf{Q}\ extbf{x}-\ extbf{b}^{T}\ extbf{x}$ ,则 $\\alpha_{k}=\\frac{\ extbf{g}_{k}^{T}\ extbf{g}_{k}}{\ extbf{g}_{k}^{T}\ extbf{Q}\ extbf{g}_{k}}$ ,其中 $\ extbf{g}_{k}=\ extbf{Q}\ extbf{x}_{k}-\ extbf{b}$ ，则迭代公式为 $\ extbf{x}_{k+1}=\ extbf{x}_{k}+ \\frac{\ extbf{g}_{k}^{T}\ extbf{g}_{k}}{\ extbf{g}_{k}^{T}\ extbf{Q}\ extbf{g}_{k}}\ extbf{g}_{k}$ 。

************************************************************************

牛顿法（涉及目标函数的一阶导数以及二阶导数）

当初始点与极小值点足够接近时，牛顿法的效率比最速下降法的要高。

牛顿法的主要思想为：

给定一个迭代点后，构造二次型函数，使得该二次型函数在该迭代点的一次导数和二次导数都与目标函数相同，将此二次型函数看为目标函数的近似函数；
求该二次型函数的极小点，作为下个迭代点。

通过对目标函数在 $\ extbf{x}_{k}$ 处进行泰勒展开得到二次型函数：

$f(\ extbf{x}) \\approx f(\ extbf{x}_{k}) + (\ extbf{x}- \ extbf{x}_{k})^{T}\ extbf{g}_{k}+ (\ extbf{x}- \ extbf{x}_{k})^{T}\ extbf{F}(\ extbf{x}_{k})(\ extbf{x}- \ extbf{x}_{k})$

则此二次型函数的极小值点为其梯度为0，则 $\ extbf{F}(\ extbf{x}_{k})(\ extbf{x}-\ extbf{x}_{k}) - \ extbf{g}_{k}=0$ ，因此牛顿法的迭代公式为 $\ extbf{x}_{k+1}=\ extbf{x}_{k}+ \ extbf{F}(\ extbf{x}_{k})^{-1}\ extbf{g}_{k}$ .

由于 $\ extbf{F}(\ extbf{x}_{k})^{-1}$ 并不容易求，我们用解方程的方式来代替求逆，则牛顿法可以分为以下两步：

求解 $\ extbf{F}(\ extbf{x}_k)\ extbf{d}_{k}=-\ extbf{g}_{k}$ ，得到 $\ extbf{d}_{k}$
下一个迭代点为 $\ extbf{x}_{k+1}=\ extbf{x}_{k}+ \ extbf{d}_{k}$ .

************************************************************************

共轭方向法（共轭梯度法）

共轭方向法，在效率上讲，处于最速下降法与牛顿法之间。

在描述共轭方向法之前，我们先定义共轭方向。给定 $\ extbf{Q}\\in R^{n\ imes n}$ ，对于一组方向 $\ extbf{d}_{0}, \ extbf{d}_{1}, \ extbf{d}_{1},\\dots, \ extbf{d}_{n}$ ，若对于任意 $i \ eq j$ ，都有 $\ extbf{x}_{i}^{T}\ extbf{Q}\ extbf{x}_{j}=0$ ，则我们说其关于 $\ extbf{Q}$ 共轭。

我们基于目标函数是二次型函数，即 $f(\ extbf{x})=\\frac{1}{2}\ extbf{x}^{T}\ extbf{Q}\ extbf{x}-\ extbf{b}^{T}\ extbf{x}$ ，介绍基本共轭方向算法，给定关于 $\ extbf{Q}$ 的共轭方向 $\ extbf{d}_{0}, \ extbf{d}_{1}, \ extbf{d}_{1}, \\dots, \ extbf{d}_{n-1}$ ，以及初始点 $\ extbf{x}_{0}$ ，具体迭代步骤如下：

$\ extbf{g}_{k}=\ extbf{Q}\ extbf{x}_{k}- \ extbf{b}$
$\\alpha_{k}=-\\frac{\ extbf{g}_{k}^{T}\ extbf{d}_{k}}{\ extbf{d}_{k}^{T}\ extbf{Q}\ extbf{d}_{k}}$
$\ extbf{x}_{k+1}=\ extbf{x}_{k}+ \\alpha_{k}\ extbf{d}_{k}$

但是提前给出一组共轭方向并不容易，在这种情况下，共轭梯度法（对于二次型目标函数）被提出，其不需要提前给定共轭方向。共轭梯度法的步骤如下：

给定初始值 $\ extbf{x}_{0}$
计算 $\ extbf{g}_{0}=\ abla{f}(\ extbf{x}_{0})$ ，若 $\ extbf{g}_{0}=0$ ，则停止迭代；否则， $\ extbf{d}_{0}=- \ extbf{g}_{0}$ .
计算步长 $\\alpha_{k}=-\\frac{\ extbf{g}_{k}^{T}\ extbf{d}_{k}}{\ extbf{d}_{k}^{T}\ extbf{Q}\ extbf{d}_{k}}$
计算 $\ extbf{x}_{k+1}=\ extbf{x}_{k}+ \\alpha_{k}\ extbf{d}_{k}$
计算 $\ extbf{g}_{k+1}=\ abla{f}(\ extbf{x}_{k+1})$ 。若 $\ extbf{g}_{k+1}=0$ ，则停止迭代。
计算 $\\beta_{k}=\\frac{\ extbf{g}_{k+1}^{T}\ extbf{Q}\ extbf{d}_{k}}{\ extbf{d}_{k}^{T}\ extbf{Q}\ extbf{d}_{k}}$
计算 $\ extbf{d}_{k+1}=-\ extbf{g}_{k}+ \\beta_{k}\ extbf{d}_{k}$
令 $k=k+1$ ,回到第三步。

************************************************************************

拟牛顿法

拟牛顿法的思路为：

为牛顿法增添步长
为 $\ extbf{F}(\ extbf{x}_{k})^{-1}$ 寻找近似矩阵

因此拟牛顿法的的迭代公式为：

$\ extbf{d}_{k}=-\ extbf{H}_{k}\ extbf{g}_{k}$ ( $\ extbf{H}_{k}$ 为对称矩阵)
$\\alpha_{k}=\\mathrm{arg}_{\\alpha \\geq 0}\\mathrm{min}f({\ extbf{x}_{k}+ \\alpha\ extbf{d}_k})$
$\ extbf{x}_{k+1}=\ extbf{x}_{k}+ \\alpha_{k}\ extbf{d}_{k}$

线性规划以及对偶问题

线性规划的标准形式为：

minimize $\ extbf{c}^{T}\ extbf{x}$

subject to $\ extbf{A}\ extbf{x}=\ extbf{b}$ ; $\ extbf{x}\\geq 0$

其中 $\ extbf{c}\\in R^{n}, \ extbf{A}\\in R^{m \ imes n}, rank(\ extbf{A})=m,\ extbf{b}\\in R^{m}, m < n, \ extbf{b}\\geq \ extbf{0}$

对于方程 $\ extbf{A}\ extbf{x}=\ extbf{b}$ ,选择矩阵前 $\ extbf{A}$ 的前m列为基，经过简单行变换矩阵 $\ extbf{B}\\in R^{m \ imes m}$ 可以使得 $\ extbf{A}$ 前m列变为单位矩阵，即 $\ extbf{B}\ extbf{A}=[\ extbf{I}_{m}, \ extbf{Y}_{m, n-m}]$ , $\ extbf{B}\ extbf{b}=\ extbf{y}_{0}$ 增广矩阵标准型： $[\ extbf{I}_{m}, \ extbf{Y}_{m,n-m}, \ extbf{y}_{0}]=\\left[ \\begin{array}{cccccccc}1 & 0 & \\cdots & 0 & y_{1,m+1}& \\cdots & y_{1,n}& y_{1,0}\\\\ 0 & 1 & \\cdots &0 & y_{2, m+1}& \\cdots & y_{2,n}& y_{2, 0}\\\\ \\vdots & \\vdots & \\ddots & \\vdots & \\vdots & & \\vdots & \\vdots \\\\ 0 & 0 & \\cdots & 1 & y_{m, m+1}& \\cdots & y_{m, n}& y_{m,0}\\end{array}\\right]$

检验数为 $r_{i}=c_{i}- z_{i}=c_{i}- (c_{1}y_{1,i}+ \\cdots + c_{m}y_{m,i})$

利用单纯性法来求解线性规划，其步骤为：

根据初始基本可行解构造增广矩阵规范型
计算非基变量的检验数
若所有的非基检验数都为非负，则停止运算，当前基本可行解为最优解，否则进入下一步。
从负检验数中选择一个检验数 $r_{q}$ ，其对应的非基变量为进阶变量。
若不存在 $y_{i,q}> 0$ ，则停止运算，则问题无解。否则，计算 $p=\\mathrm{arg}\ extbf{ }\\mathrm{min}_{i}\\{{\\frac{y_{i,0}}{y_{i,q}}: y_{i,q}>0}\\}$ , p对应的基变量为出阶变量。若求解得多个下标满足条件，则 $p$ 为最小的下标值
以元素 (p,q) 为枢纽元素作为枢纽元素作枢纽变换，更新增广矩阵规范型
转到步骤2.

可以利用单纯形表来解决线性规划问题，举个，如下：

线性规划问题为：

maximize $7x_{1}+ 6x_{2}$

s.t. $2x_{1}+ x_{2}\\leq 3 ; x_{1}+ 4x_{2}\\leq 4; x_{1}, x_{2}\\geq 0$

首先把该规划问题转化为标准形式，目标函数乘以-1，为约束1和约束2加入松弛变量，得到的单纯形表如下：

$\\begin{array}{cccc}& x_{1}& x_{2}& x_{3}& x_{4}& b\\\\ & 2 & 1 & 1 & 0 & 3\\\\ & 1 & 4 & 0 & 1 & 4 \\\\ \ extbf{c}^{T}\ extbf{x}& -7 & -6 & 0 & 0 & 0 \\end{array}$

最后一行包含了检验数，-7最小，则第一列为进阶向量，利用 b 列除以 $x_{1}$ 列，得到 $\\frac{3}{2}< \\frac{4}{1}$ ，则基变量中的第一个为出阶变量，则以第一行第一列为出的元素为枢纽元素得到第二个单纯形表 $\\begin{array}{cccc}& x_{1}& x_{2}& x_{3}& x_{4}& b\\\\ & 1 & \\frac{1}{2}& \\frac{1}{2}& 0 & \\frac{3}{2}\\\\ & 0 & \\frac{7}{2}& -\\frac{1}{2}& 1 & \\frac{5}{2}\\\\ \ extbf{c}^{T}\ extbf{x}& 0 & -\\frac{5}{2}&\\frac{7}{2}& 0 & \\frac{21}{2}\\end{array}$ , 利用b列除以 $x_{2}$ 列，得到 $3 > \\frac{5}{7}$ ，则第二行第二列的元素为枢纽元素，得到的单纯形表为 $\\begin{array}{cccc}& x_{1}& x_{2}& x_{3}& x_{4}& b\\\\ & 1 & 0 & \\frac{4}{7}& -\\frac{1}{7}& \\frac{8}{7}\\\\ & 0 & 1 & -\\frac{1}{7}& \\frac{2}{7}& \\frac{5}{7}\\\\ \ extbf{c}^{T}\ extbf{x}& 0 & 0 &\\frac{22}{7}& \\frac{5}{7}& \\frac{86}{7}\\end{array}$ ，则 $x_{1}=\\frac{8}{7}, x_{2}=\\frac{5}{7}, x_{3}=0, x_{4}=0$ 为线性规划的最优解，相应的目标函数的值为 $-\\frac{87}{7}$ 。则原问题的最优解为 $x_{1}=\\frac{8}{7}, x_{2}=\\frac{5}{7}$ ,相应的目标函数值为 $\\frac{87}{7}$ .

************************************************************************

对偶问题：

把形如：

minimize $\ extbf{c}^{T}\ extbf{x}$

subject to $\ extbf{A}\ extbf{x}\\geq \ extbf{b}$ ; $\ extbf{x}\\geq 0$

转化为：

maximize $\\mathbf{\\lambda}^{T}\\mathbf{b}$

subject to $\\mathbf{\\lambda}\ extbf{A}\\leq \ extbf{c}^{T}$ ; $\\mathbf{\\lambda}\\geq 0$

目标值相同

************************************************************************

非线性规划

拉格朗日条件

拉格朗日条件是为了解决等式约束优化。

问题描述：

minimize $f(\ extbf{x})$

subject to $\ extbf{h}(\ extbf{x})=\ extbf{0}$

正则点：对于满足约束 $h_{1}(\\mathbf{x}^{*})=0, \\cdots, h_{m}(\\mathbf{x^{*}})$ 的点 $x^{*}$ ，如果梯度向量 $\ abla{h}_{1}(\\mathbf{x}^{*}), \\cdots, \ abla{h}_{m}(\\mathbf{x}^{*})$ 线性无关，则称点 $x^{*}$ 为该约束的一个正则点。

已知

$\\mathrm{D}\\mathbf{h}(\\mathbf{x})=\\left[ \\begin{array}{c}\\mathrm{D}h_{1}(\\mathbf{x})\\\\ \\vdots\\\\ \\mathrm{D}h_{m}(\\mathbf{x}) \\end{array}\\right]=\\left[ \\begin{array}{c}\ abla{h}_{1}(\\mathbf{x})^{T}\\\\ \\vdots\\\\ \ abla{h}_{m}(\\mathbf{x})^{T}\\end{array}\\right]$

拉格朗日定理：

$\\mathbf{x}^{*}$ 为 $f$ 的极值点，且为正则点，则存在 $\\mathbf{\\lambda ^{*}}\\in R^{m}$ ,使得 $\\mathrm{D}{f}(\\mathbf{x}^{*}) + \\mathbf{\\lambda}^{T}\\mathrm{D}{\\mathbf{h}}(\\mathbf{x}^{*})=\\mathbf{0}^{T}$

极小值点存在二阶必要条件和充分条件。

************************************************************************

KKT条件

KKT条件为了解决不等式优化问题。

问题描述如下：

minimize $f(\ extbf{x})$

subject to $\ extbf{h}(\ extbf{x})=\ extbf{0}； \ extbf{g}(\ extbf{x}) \\leq \ extbf{0}$

对于不等式优化问题，其约束的正则点 $\\mathbf{x}^{*}$ 为令等式以及在 $\\mathbf{x}^{*}$ 处起作用的不等式的梯度线性无关的点。在 $\\mathbf{x}^{*}$ 处起作用的不等式 $g$ 满足 $g(\\mathbf{x^{*}})=0$ , 在 $\\mathbf{x}^{*}$ 处不起作用的不等式 $g$ 满足 $g(\\mathbf{x^{*}}) < 0$ 。

KKT条件：设 $\\mathbf{x}^{*}$ 为正则点以及局部极小点，则存在 $\\mathbf{\\lambda}^{*}$ 和 $\\mathbf{\\mu}^{*}$ 使得

$\\mathbf{\\mu}^{*}\\geq \\mathbf{0}$
$\\mathrm{D}{f}(\\mathbf{x}^{*}) +{\\mathbf{\\lambda}^{*}}^{T}\\mathrm{D}{\\mathbf{h}}(\\mathbf{x}^{*}) +{\\mathbf{\\mu}^{*}}^{T}\\mathrm{D}\\mathbf{g}(\\mathbf{x}^{*})=\\mathbf{0}^{T}$
${\\mathbf{\\mu}^{*}}^{T}\\mathbf{g}(\\mathbf{x}^{*})=0$

************************************************************************

凸优化

若在介绍KKT条件中描述的问题的目标函数 $f$ 为凸函数，且约束条件构成的可行域 $\\Omega$ 为凸集。若存在存在 $\\mathbf{x}^{*}$ , $\\mathbf{\\lambda}^{*}$ 和 $\\mathbf{\\mu}^{*}$ 使得：

$\\mathbf{\\mu}^{*}\\geq \\mathbf{0}$
$\\mathrm{D}{f}(\\mathbf{x}^{*}) +{\\mathbf{\\lambda}^{*}}^{T}\\mathrm{D}{\\mathbf{h}}(\\mathbf{x}^{*}) +{\\mathbf{\\mu}^{*}}^{T}\\mathrm{D}\\mathbf{g}(\\mathbf{x}^{*})=\\mathbf{0}^{T}$
${\\mathbf{\\mu}^{*}}^{T}\\mathbf{g}(\\mathbf{x}^{*})=0$

则 $\\mathbf{x}^{*}$ 是 $f$ 在 $\\Omega$ 上的全局极小点。

以上即为最优化的基础算法，敬请批评指正。

返回列表

联系我们

地址：广东省广州市天河区88号
电话：400-123-4567
点击图标在线留言，我们会及时回复

Title 简说最优化基本算法

Title
简说最优化基本算法