第5章 无约束优化及非线性优化

无约束非线性优化算法此类算法提供公式 2 的精确解。

但是，它们要耗费与 H 的几个分解成比例的时间。

因此，对于大型问题，需要一种不同方法。

文献（[42] 和 [50]）中提出了几种基于公式 2 的逼近和启发式方法建议。

Optimization Toolbox 求解器采用的逼近方法是将信赖域子问题限制在二维子空间 S 内（[39] 和[42]）。

一旦计算出子空间 S，即使需要完整的特征值/特征向量信息，求解公式 2 的工作量也不大（因为在子空间中，问题只是二维的）。

现在的主要工作已转移到子空间的确定上。

二维子空间 S 是借助下述预条件共轭梯度法确定的。

求解器将 S 定义为由 s1和 s2确定的线性空间，其中 s1是梯度 g 的方向，s2是近似牛顿方向，即下式的解或是负曲率的方向，以此种方式选择 S 背后的理念是强制全局收敛（通过最陡下降方向或负曲率方向）并实现快速局部收敛（通过牛顿步，如果它存在）。

现在，我们可以很容易地给出基于信赖域的无约束最小化的大致框架：1.构造二维信赖域子问题。

2.求解公式 2 以确定试探步 s。

3.如果 f(x + s) < f(x)，则 x = x + s。

4.调整Δ。

重复这四个步骤，直到收敛。

信赖域维度Δ 根据标准规则进行调整。

具体来说，它会在试探步不被接受（即f(x + s) ≥ f(x)）时减小。

有关这方面的讨论，请参阅[46] 和 [49]。

Optimization Toolbox 求解器用专用函数处理 f 的一些重要特例：非线性最小二乘、二次函数和线性最小二乘。

然而，其底层算法思路与一般情况相同。

这些特例将在后面的章节中讨论。

非线性优化与约束优化问题的求解方法非线性优化问题是在目标函数和约束条件中包含非线性项的优化问题。

约束优化问题是在目标函数中加入了一些约束条件的优化问题。

解决这些问题在实际应用中具有重要意义，因此研究非线性优化和约束优化问题的求解方法具有重要的理论和实际意义。

一、非线性优化问题的求解方法非线性优化问题的求解方法有很多，下面介绍几种常见的方法：1. 黄金分割法：黄金分割法是一种简单但有效的搜索方法，它通过不断缩小搜索范围来逼近最优解。

该方法适用于目标函数单峰且连续的情况。

2. 牛顿法：牛顿法利用目标函数的一阶和二阶导数信息来逼近最优解。

该方法收敛速度较快，但在计算高阶导数或者初始点选取不当时可能产生不稳定的结果。

3. 拟牛顿法：拟牛顿法是对牛顿法的改进，它通过逼近目标函数的Hessian矩阵来加快收敛速度。

拟牛顿法可以通过不同的更新策略来选择Broyden-Fletcher-Goldfarb-Shanno（BFGS）方法或者DFP方法。

4. 全局优化方法：全局优化方法适用于非凸优化问题，它通过遍历搜索空间来寻找全局最优解。

全局优化方法包括遗传算法、粒子群优化等。

二、约束优化问题的求解方法约束优化问题的求解方法也有很多，下面介绍几种常见的方法：1. 等式约束问题的拉格朗日乘子法：等式约束问题可以通过引入拉格朗日乘子来转化为无约束优化问题。

通过求解无约束优化问题的驻点，求得原始约束优化问题的解。

2. 不等式约束问题的罚函数法：不等式约束问题可以通过引入罚函数来转化为无约束优化问题。

罚函数法通过将违反约束条件的点处添加罚项，将约束优化问题转化为无约束问题。

3. 逐次二次规划法：逐次二次规划法是一种常用的求解约束优化问题的方法。

该方法通过依次处理逐个约束来逼近最优解，每次处理都会得到一个更小的问题，直至满足所有约束条件。

4. 内点法：内点法是一种有效的求解约束优化问题的方法。

该方法通过向可行域内部逼近，在整个迭代过程中都保持在可行域内部，从而避免了外点法需要不断向可行域逼近的过程。

垫墼兰￡望叁兰堑圭兰垒篁塞１第一章预备知识§１．１共轭梯度方法§１．１．１引言共轭梯度法足最优化中最常用的方法之一。

它具有算法简便，存储需求小等优点，十分适合于大规模优化问题．在石油勘探，大气模拟，航天航空等领域出现的特大规模的优化问题是常常利用共轭梯度法求解。

在所有需要计算导数的优化方法中，最速下降是最简单的，但它速度太慢。

拟牛顿方法收敛速度很快，被广泛认为是非线性规划的最有效的方法。

但拟牛顿法需要存储矩阵以及通过求解线性方程组来计算搜索方向，这对于求解诸如上述问题等一些大规模问题几乎是不太可能办到的，共轭梯度法在算法的简便性，所需存储量等方面均与最速下降法差别不大，而收敛速度比最速下降法要快。

非线性共轭梯度法的收敛性分析的早期工作主要由Ｆｌｅｔｃｈｅｒ，Ｐｏｗｅｌｌ，Ｂｅａｌｅ等学者给出的，近年来，Ｎｏｃｅｄａｌ，Ｇｉｌｂｅｒｔ，Ｎａｚａｒｅｔｈ等学者在收敛性方面得到了不少的结果，使得共轭梯度法的研究由又热了起来．我国的学者也在共轭梯度法的理论研究中也取得了一定的成绩。

例如中科院应用数学所的韩继业，戴口等．§１．１．２共轭方向法共轭梯度法最本质的是共轭性质，共轭性是正交的一种推广。

定义１．１．２．１：设Ｗ∈咿×ｎ对称正定，ｄｌ，ｄ２，…，ｄ。

是咿中的一组非零向量，如果盯Ａｄｊ＝０，（ｉ≠Ｊ）．（１．１）则称ｄ１，ｄ２，…，ｄ。

是相互Ａ一共轭。

显然可见，如果ｄｌ，ｄ２，…，ｄ。

相互Ａ一共轭，则它们是线性无关的。

设Ｊ是单位阵则知，一共轭就是正交。

一般共轭方向法步骤如下：算法１．１．２．１：（一般共轭方向法）给出∞＋的初始点Ｘｌ，步ｌ：计算ｇｌ＝ｇ（Ｘ１）．步２：计算ｄｌ，使（ｆ｛’９ｌ＜０．步３：令女＝１．步４：计算口ｋ和Ｘｋ＋１，使得ｆ（ｘｋ－Ｆ‘１ｋｄｋ）。

Ｉ。

ｊ１１，‰十“呶），Ｘｋ＋１＝Ｘｋ＋ｖ。

ｋｄｋ．步５：计算以＋ｌ使得ｄ矗１Ｇｄｊ＝０，Ｊ＝１，２，…ｋ．步６：令ｋ：＝ｋ＋１，转步４．共轭方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性，这就足下面的共轭方向法基本定理。

05-⽆约束优化算法05-⽆约束优化算法⽬录⼀、⽆约束最⼩化问题[⽆约束最⼩化问题] 使 f(x) 最⼩化， f:R n→R 是凸的，且⼆次可微（意味着 domf 是开集)。

假设这个问题是可解的，也就是存在最优点 x∗ ，最优值 inf x f(x)=f(x∗) ，记为 p∗ .[最优充要条件] 因为 f 是可微且凸的，点 x∗ 是最优点的充要条件是∇f(x∗)=0 .注：其实可以从⼆维的图像去理解因此解决⽆约束最⼩化问题等同于寻找上式的解，是含有n个未知数的n个⽅程的集⽅程组。

有时我们是⽤递归算法来解决这个问题，也就是依次计算x(0),x(1),...∈domf , 有f(x(k))→p∗,k→∞ 。

这样的序列叫做问题的最⼩化序列 (minimizing sequence)。

算法的停⽌条件：f(x(k))−p∗≤ϵ，ϵ≥0 是可容许的误差值。

[初始点，下⽔平集] 初始点 x(0) 必须在 domf 中，并且下⽔平集S={x∈domf|f(x)≤f(x(0))} 必须是闭的。

注：下⽔平集是闭的，其实就是对函数做了⽔平切割，然后⽔平切割下的图像是封闭的如果函数 f 是闭的（也就是它的所有下⽔平集都是闭的）那么以上条件都能满⾜。

定义在domf=R n上的连续函数是闭的，所以如果domf=R n，那么初始下⽔平集条件对于任何x(0)都满⾜。

另⼀种闭函数：定义域是开集，当x趋近于bd domf时，f(x) 趋近于⽆限。

[强凸] ⼀个函数在 S 上是强凸的，如果存在 m>0 ，使得对于所有的 x∈S ，有∇2f(x)⪰mI.注：强凸的性质，其实就是保证函数的 ∇2f(x)>0 ，也就是确保只有⼀个最优解，⽽弱凸是最优解有多个，如下图所⽰。

对于x,y∈S我们有f(y)=f(x)+∇f(x)T(y−x)+12(y−x)T∇2f(z)(y−x) , for some z∈[x,y] 。

根据强凸的假设，最后⼀项⼤于等于 (m/2)‖y−x‖22,∀x,y∈S ，也就是：f(y)≥f(x)+∇f(x)T(y−x)+(m/2)‖y−x‖22 .当m=0 时，我们得到了描述凸性的基本不等式。

求解无约束优化问题及非线性方程组的共轭梯度法求解无约束优化问题及非线性方程组的共轭梯度法一、引言无约束优化问题和非线性方程组是数学和工程领域中常见的问题。

它们的解决对于优化模型的求解以及工程实际问题的解决具有重要意义。

本文将介绍一种常用的求解无约束优化问题和非线性方程组的方法——共轭梯度法，包括算法原理、步骤和性能分析等。

二、共轭梯度法的算法原理共轭梯度法是一种迭代法，它通过计算一系列共轭方向，逐步接近于最优解。

具体而言，共轭梯度法的算法原理如下：（1）初始化。

选择一个起始值x0，设置迭代精度ε，取初始共轭方向d0=g0=-∇f(x0)，其中g0为梯度的初始值。

（2）迭代过程。

从k=1开始，根据共轭方向的性质，可以得到更新公式xk=xk-1+αkdk，其中αk为步长，dk为共轭方向。

通过下面的迭代公式可以计算共轭方向dk：di=(-gi)+βidi-1βi=(gi，gi)/(gi-1，gi-1)其中gi为第i次迭代的梯度。

（3）收敛判断。

如果满足||gk||<ε，则停止迭代计算，得到近似解。

否则，继续迭代。

三、共轭梯度法的步骤根据共轭梯度法的算法原理，可以得到具体的步骤如下：（1）初始化。

选择起始点x0，设置迭代精度ε，取初始共轭方向d0=g0=-∇f(x0)，其中g0为梯度的初始值。

（2）循环迭代。

从k=1开始，计算步长αk，更新公式xk=xk-1+αkdk，计算新的梯度gk，计算共轭方向dk。

（3）收敛判断。

如果满足||gk||<ε，则停止迭代。

（4）输出结果。

输出近似解xk。

四、共轭梯度法的性能分析共轭梯度法在求解无约束优化问题和非线性方程组时具有一些优良的性能特点：（1）收敛性。

共轭梯度法在理想情况下可以在n步内达到最优解，其中n为问题的维度。

（2）存储要求小。

共轭梯度法只需要存储上一次迭代的结果，存储量较小。

（3）不需要二阶导数信息。

与牛顿法等方法相比，共轭梯度法不需要二阶导数信息，计算速度更快。