1、最优化模型及其分类

   最优化的数学模型一般表示为

其中及都是定义在上的实值连续函数，且至少有一个是非线性的。如果，则问题被称为无约束优化问题。如果是正整数，则问题被称为约束优化问题。其中，称为目标函数，称为约束函数。如果都是线性函数，则问题就是线性规划。如果和存在一个非线性函数，则问题就是非线性规划。特别地，若为二次函数，为线性函数，则问题是二次规划问题。
  

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

  无约束优化问题，即

  求解无约束优化问题 (1) 的算法有线搜索算法和信赖域法等
(1)、线搜索
  线搜索的基本迭代格式为

其中是搜索方向，是搜索步长为线搜索确定。线搜索分为精确线搜索和非精确线搜索

i、精确线搜索

   精确线搜索的代价较高，实际计算中很难实现和锯齿现象。所以在实际中我们会常常选择非精确线搜索，不要求函数沿着方向下降到最小，只需满足一定的下降条件即可。以下列举几种常见的非精确线搜索

ii、Armijo-Goldstein 准则
  这一准则是 Armijo 和 Goldstein 在 20 世纪 60 年代提出的，它要求步长满足下列条件

  其中，(3) 式中的第一个不等式是保证目标函数有足够的下降，第二个不等式则防止过小

iii、Wolfe--Powell 准则
  由于准则有可能把步长的极小值排除在接受区间外，为此 Wolfe 和 Powell 提出了如下准则

  其中，(4) 式中第一个不等式是关于函数信息，第二个不等式是曲率信息。Wolfe-Powell 准则也被称为标准 Wolfe 准则。

iV、强 Wolfe 准则
  (4) 中的不足之处在于，当时也不能得到精确线搜索。为此有

  以上只是几种常见的线搜索，线搜索的种类有很多，以后会详细谈到。要使得上述线搜索中的存在，则应是下降方向，即

  关于的存在性，我们都未给出证明，可以参考一些书籍，或者一些知网上面的文章吧，过程并不复杂。

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

i、最速下降法
  1847 年，法国数学家 Cauchy 在研究函数沿什么方向下降最快的问题，提出了最速下降法。其基本迭代格式

其中 Cauchy 步长由精确线搜索所确定，虽然理论是是函数在下降最快的方向且 Cauchy 步长让函数在搜索方向最小，但这只是反映了函数的局部性质。从整体上看，最速下降法效率却很低，因为相邻的两次搜索方向是正交。当趋于极小值时，锯齿现象会更严重。

ii、牛顿法
  若二阶连续可微，由 Taylor 公式，在处的二阶近似为

假设 Hesse 矩阵是正定的，牛顿法将的极小值作为下一个迭代点。即

当初始点接近极小值点时，牛顿法是二阶收敛的。值得注意的是，当初始点远离极小值点时，牛顿法可能不收敛，为此提出了阻尼牛顿法。

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

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

V、拟牛顿法
   拟牛顿法就是用拟牛顿矩阵近似矩阵，从而避免直接计算，矩阵满足拟牛顿方程

其中，不同的拟牛顿矩阵对应不同的算法，主要有 DFP 算法 和 BFGS 算法。此处省略。

(3)、信赖域法
   根据前面的分析，我们知道线搜索是先确定搜索方向，再由线搜索条件确定步长因子，从而确定位移。但是信赖域法则不然，是在算法中直接求出每次迭代步的位移。
   信赖域法首先给出一个位移长度上界（信赖域半径），以当前点为中心，以此上界为半径确立一个领域。然后通过求这个领域内的二次近似目标函数的最优点来确定候选位移。这个区域内的近似函数往往是可信赖的而称为信赖域。若新的位移能够使目标函数值充分下降，则接受候选位移，并保持或扩大信赖域范围，然后继续新的迭代。若新的位移不能使目标函数值充分下降，这说明二次模型与目标函数的近似程度不够好，因此需要缩小信赖域范围，然后通过新的信赖域内二次模型，求新的候选位移。
其基本数学模型为
   最优化的数学模型一般表示为

其中是信赖域半径，为的近似，我们定义实际下降量（）和实际下降量（）


定义比值为

若趋于1，则二次模型与目标函数在信赖域范围内有很好的近似，则可令，下一次迭代可以适当扩大信赖域半径。否则，我们就需要缩小信赖域半径。