Tabler 阿狗工具

  1. 在线工具
  2. 好文
  3. 2、最优化理论的简介
2、最优化理论的简介
2024-04-09 21:10:37  阅读数 1792

1、最优化模型及其分类

   最优化的数学模型一般表示为
\begin{cases} \underset{x\in\mathbb{R}^n}\min&{f(x)},\\ \rm{s.t} ~~~~ &c_i(x)=0,~~i=1,2,\dots,m_e,\\ &c_i(x)\ge 0,~~i=m_e+1,\dots,m, \end{cases}
其中~f(x)~及~c_i(x)~(i=1,2,\dots,m)都是定义在~\mathbb{R}^n~上的实值连续函数，且至少有一个是非线性的。如果~m=0~，则问题被称为无约束优化问题。如果~m~是正整数，则问题被称为约束优化问题。其中，~f(x)~称为目标函数，~c_i(x)~称为约束函数。如果~f(x),c_i(x)~都是线性函数，则问题就是线性规划。如果~f(x)~和~c_i(x)~存在一个非线性函数，则问题就是非线性规划。特别地，若~f(x)~为二次函数，~c_i(x)~为线性函数，则问题是二次规划问题。
  \color{red}{不过我们主要研究的是无约束非线性规划问题}

2、求解无约束优化问题的方法

  无约束优化问题，即
\min_{x\in\mathbb{R}^n}~f(x)\tag{1}
  求解无约束优化问题 (1) 的算法有线搜索算法和信赖域法等
(1)、线搜索
  线搜索的基本迭代格式为
x_{k+1}=x_k+\alpha_k d_k\tag{2}
其中~d_k~是搜索方向，~\alpha_k>0~是搜索步长为线搜索确定。线搜索分为精确线搜索和非精确线搜索

i、精确线搜索
\alpha_k=\arg\underset{\alpha>0}\min~f(x_k+\alpha d_k)
   精确线搜索的代价较高，实际计算中很难实现和锯齿现象。所以在实际中我们会常常选择非精确线搜索，不要求函数~f(x)~沿着方向~d_k~下降到最小，只需满足一定的下降条件即可。以下列举几种常见的非精确线搜索

ii、Armijo-Goldstein 准则
  这一准则是 Armijo 和 Goldstein 在 20 世纪 60 年代提出的，它要求步长~\alpha_k~满足下列条件
\begin{cases} f(x_k+\alpha_k d_k)\le f(x_k)+\alpha_k\rho g_k^Td_k\\ f(x_k+\alpha_k d_k)\ge f(x_k)+\alpha_k(1-\rho) g_k^T d_k\tag{3} \end{cases}
  其中~0<\rho<\sigma<1~，(3) 式中的第一个不等式是保证目标函数有足够的下降，第二个不等式则防止~\alpha_k~过小

iii、Wolfe--Powell 准则
  由于~\rm{Armijo-Goldstein}~准则有可能把步长的极小值排除在接受区间外，为此 Wolfe 和 Powell 提出了如下准则
\begin{cases} f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k\\ g(x_k+\alpha_k)^T d_k\ge\sigma g_k^Td_k\tag{4} \end{cases}
  其中~0<\rho<\sigma<1~，(4) 式中第一个不等式是关于函数信息，第二个不等式是曲率信息。Wolfe-Powell 准则也被称为标准 Wolfe 准则。

iV、强 Wolfe 准则
  (4) 中的不足之处在于，当~\sigma\rightarrow 0~时也不能得到精确线搜索。为此有
\begin{cases} f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k\\ \vert g(x_k+\alpha_k)^T d_k\vert\le-\sigma g_k^Td_k\tag{5} \end{cases}

  以上只是几种常见的线搜索，线搜索的种类有很多，以后会详细谈到。要使得上述线搜索中的~\alpha_k~存在，则~d_k~应是下降方向，即
g_k^T d_k< 0,~~~\forall~~k\ge 1\tag{6}
  关于~\alpha_k~的存在性，我们都未给出证明，可以参考一些书籍，或者一些知网上面的文章吧，过程并不复杂。

(2)、线搜索算法
   下面介绍几种常见的线搜索算法：最速下降法，牛顿法，阻尼牛顿法、共轭梯度法和拟牛顿法。

i、最速下降法
  1847 年，法国数学家 Cauchy 在研究函数沿什么方向下降最快的问题，提出了最速下降法。其基本迭代格式
x_{k+1}=x_k-\alpha_k^c g_k\tag{7}
其中 Cauchy 步长~\alpha_k^c~由精确线搜索所确定，虽然理论是~-g_k~是函数~f(x)~在~x_k~下降最快的方向且 Cauchy 步长让函数在搜索方向最小，但这只是反映了函数的局部性质。从整体上看，最速下降法效率却很低，因为相邻的两次搜索方向是正交。当趋于极小值时，锯齿现象会更严重。

ii、牛顿法
  若~f(x)~二阶连续可微，由 Taylor 公式，~f(x)~在~x_k~处的二阶近似为
f(x)\approx f(x_k)+g_k(x-x_k)+\frac{1}{2}(x-x_k)^TG_k(x-x_k)=m_k(x)
假设 Hesse 矩阵~G_k~是正定的，牛顿法将~m_k(x)~的极小值作为下一个迭代点。即
x_{k+1}=x_k-G_k^{-1}g_k
当初始点接近极小值点时，牛顿法是二阶收敛的。值得注意的是，当初始点远离极小值点时，牛顿法可能不收敛，为此提出了阻尼牛顿法。

iii、阻尼牛顿法
  牛顿法面临的主要困难是~G_k~不正定，在这种情况下，下降方向很难获得，为此有阻尼牛顿法。阻尼牛顿法的种类有很多，主要介绍两种，分别是 Goldstein--Price 修正和 Goldfeld 修正。他们思想都很简单，Goldstein--Price 修正就是如果~G_k~不正定，我们选择负梯度方向作为搜索方向。Goldfeld 修正就是若~G_k~不正定，令~d_k=-B_k^{-1}g_k~，其中~B_k=G_k+ E_k~，其中~E_k~是修正矩阵。

iv、共轭梯度法
  \color{red}{共轭梯度法是我目前研究的方向，此处只是简单提一下，后面会有更加详细的介绍。}
   1952 年，Hestense 和 Stiefel 在求解线性方程组 AX=b 时提出了共轭梯度法，我们称为线性共轭梯度法。1964 年，Fletcher 和 Reeves 将共轭梯度法应用到求解二次函数的局部极小点问题中，这通常被认为是求解无约束优化问题的非线性共轭梯度法的开端。共轭梯度法由于只是需要一阶导数信息，所以具有存贮量小的特点，适合求解大型无约束无约束优化问题。共轭梯度法有很多细分方向，比如混合共轭梯度法，三项共轭梯度法，修正共轭梯度法，三项共轭梯度法等。

V、拟牛顿法
   拟牛顿法就是用拟牛顿矩阵~B_k~近似~\rm{Hesse}~矩阵~G_k~，从而避免直接计算~G_k~，矩阵~B_k~满足拟牛顿方程
B_ks_k=y_k
其中~s_k=x_{k+1}-x_k,y_k=g_{k+1}-g_k~，不同的拟牛顿矩阵对应不同的算法，主要有 DFP 算法 和 BFGS 算法。此处省略。

(3)、信赖域法
   根据前面的分析，我们知道线搜索是先确定搜索方向，再由线搜索条件确定步长因子，从而确定位移。但是信赖域法则不然，是在算法中直接求出每次迭代步的位移。
   信赖域法首先给出一个位移长度上界（信赖域半径），以当前点为中心，以此上界为半径确立一个领域。然后通过求这个领域内的二次近似目标函数的最优点来确定候选位移。这个区域内的近似函数往往是可信赖的而称为信赖域。若新的位移能够使目标函数值充分下降，则接受候选位移，并保持或扩大信赖域范围，然后继续新的迭代。若新的位移不能使目标函数值充分下降，这说明二次模型与目标函数的近似程度不够好，因此需要缩小信赖域范围，然后通过新的信赖域内二次模型，求新的候选位移。
其基本数学模型为
   最优化的数学模型一般表示为
\begin{cases} &\min~~~~&m_k(s)=f_k+g_k^Ts+\frac{1}{2}s^T B_ks\\ &\rm{s.t}&\Vert s\Vert\le\triangle_k\tag{8} \end{cases}
其中~\triangle_k~是信赖域半径，~B_k~为~G_k~的近似，我们定义实际下降量（Ared_k）和实际下降量（Pred_k）
Ared_k=f_k-f(x_k+s_k)
Pred_k=m_k(0)-m_k(s_k)
定义比值为
\rho_k=\frac{Ared_k}{Pred_k}
若~\rho_k~趋于1，则二次模型与目标函数在信赖域范围内有很好的近似，则可令~x_{k+1}=x_k+s_k~，下一次迭代可以适当扩大信赖域半径。否则，我们就需要缩小信赖域半径。

  \color{red}{以上内容也只是根据我个人所理解书写出来，可能有不当之处。我目前主要研究的是共轭梯度法，所以后面会详细介绍共轭梯度法。}