无约束最优化与非线性方程的数值方法

1、Numerical Methodsfor UnconstrainedOptimization andNonlinear Equations无约束最优化与非线性方程的数值方法J.E. De nnis, Jr. & Robert B. Sch nabel介绍这本书讨论了三大非线性问题计算的方法、运算法则和思路分析：非线性方程组的解法、非线性函数的无约束极小化方法和非线性最小二乘参数选择。1.1节介绍了这些问题和我们对此提出的假设。1.2节列举了一些非线性难题并且论述了在实际运算中遇到的这类问题的典型特征；对这类问题很熟悉的读者可能会想跳过这个章节。1.3节总结了计算机有限精度算术的特点。为了理解文

2、本中以计算机为依托 的算法，这些特点是读者必须要了解的。1.1考虑的问题这本书讨论了实践中经常遇到的三大非线性问题的实际变量。 这些是 合理假设下建立的数学等价，但我们不打算用相同的算法来处理， 而 打算展示当前最佳的算法是如何找出每个问题的结构。联立非线性方程问题（现在简称“非线性方程”）是三大非线性方程问题中最基础的，并且计算中可利用的结构最少。公式如下：已知Given F:才* find x. g R* for which F（x.） = 0 w FT*（LL1）在公式中表示n维欧氏空间。当然，（1.1.1）只是表示含未知数“n”的n非线性方程的标准公式，方程式的右边通常是零。例如：如果

3、已知门耳）7且S i山xia（x）2（1.1.1）公式中计算出来的J必然会是厂的最小值。门表示F的第i个组成函数。这是无约束极小化问题的特殊例子。Given f: R *find jc. e R for which /（xj for every x g R （l丄2）（1.1.2）是我们要考虑的第二个问题。通常（1.1.2）是min f: Rn * 喘.的缩写。例如：min /（xn x3） = （x - 3）2 + x2 + 5）4 + （x3 - 8）2,X X可以得出丄* _ X *在一些应用中，有人对解决（1.1.3 ）受限版本有兴趣，其中Q 是一个封闭连通域。如果（1.1.4 ）的解

4、法来自Q的内部，那么（1.1.4）min f: Rn R,x w Qc R仍可以看作是一个无约束极小化问题。 然而，如果.是。的边界点， 丿的极小化超过 成为一个约束极小化问题。我们不考虑约束问 题，因为目前已知的该如何去解决这个问题的知识还较少，而且其间有很多无约束问题需要我们考虑。 此外，解决无约束问题的技巧是解 决约束算法的基础。事实上，许多解决约束问题的尝试不是发现相关*X的无约束最小化问题的答案 很接近约束问题的答案 “，就是发现非线性方程组的联立解都等于 J。最终，我们在实践中遇到的绝大 多数的问题不是无约束问题就是最简单的约束问题一一例如每个入都必须非负数。我们考虑的第三个问题也

5、是无约束极小化的一个特殊例子， 但是 由于它的重要性以及它特殊的结构， 其本身就构成一个研究领域。这 就是非线性最小二乘问题：Given R : R励王略IHfinde R* for which 力（几（*护 is minimized* （LL5）21川刘表示丘的第i个组成函数。（1.1.5 ）在曲线拟合中是最常见 的，除此之外当线性系统的线性需求比自由度多时它也会出现。当非线性函数卜、；、X至少有一个、两个或者分别有两个连续 不同数时，我们只考虑最常见的例子。要是函数是充分平滑的，我们 不一定要用假设，导数就可通过分析得出。对于今天正在解决的非线 性问题的典型规模以及其它特点的进一步阐释，可

6、看1.2节。在非线性问题的数值解的典型的场景中，计算者须提供评估函数 的一个子程序，并且起始点5是的大概近似值。如果可行，计算 者还需提供第一个导数，或许还有第二个导数。我们这本书的重点是 解决在这个框架中遇到的最常见的一些困难：（1）如果起始点5和最终的答案U （全局方法）不是近似值该如何解决以及如何用区域 变量来有效的联合（局部方法）这个问题；（2）以及如果没得出解 析导数应该如何处理；（3）如果问题函数的求值用精确的算法将会 是高效的（算法往往不精确）。我们研究的基本方法以及提供的基本算法思路是当前解决这些问题的最好方法。 我们也给出了自认为是理解这些方法和，扩展或改进这些问题的相关分析

7、。尤其是，我们试图 辨别并强调这些在这个领域已经演变为中心的理念和方法。我们认为这个领域已经到达了一个可识别技术的点，这个点很可能还可改进， 但不大可能如量子跳跃般超越目前最好的算法。解决非线性方程和无约束最小化的问题的方法很相似。这本书大部分是关于这两个问题的。非线性最小二乘问题只是无约束极小化的 一个特例,但可以利用非线性最小二乘问题的特殊结构调整无约束极 小化技术获取更好的算法。因此第十章用一个广泛可行的例子说明了 如何应用和扩展前部分的内容。在这本书中，我们没有解决的问题是找出一个非线性函数的极小点，这个变量是在出现许多个不同的局部极小值的情况下的绝 对最低点。(1.1.2 )的解答是

8、，上 是开放区域的连接。这是一个 非常难的问题，并无广泛的研究也不像我们已解决的问题那样容易。 涉及此问题的两个论文集分别是DlXCn an1 “心门(1975,1978). 通观全书我们会使用到“全局 ”、“全局法”或者“全局收敛法”这些词语来表示一种算法，这种算法是专门设计用来汇集非线性函数 的全局极小点、或者是任何一个非线性方程组的起始点的一些解法。 把这些算法叫做“局部”或者“局部收敛”是比较合适的，但在另一 个算法上这些说明已经被传统保留了，对于一般算法来说确保从每个 起始点收敛的方法或许是低效的(选自Allgower and Georg (1980)。 1.2 “真实世界”问题的特

9、征在这节中我们提供一些关于实践中遇到的非线性问题。首先我们列举了三个真正的非线性问题的例子和一些参与设置数值问题的 思考。然后我们对大小、费用和其他非线性问题中遇到的一般特征作 出了评价。讨论样品问题的困难之一是在这一领域的背景和代数描述的问 题很少是简单的。虽然这使得咨询工作很有趣，但对于介绍性数值分 析的书是没有什么帮助的。因此，我们尽可能简化我们的示例。最简单的非线性问题只包含一个变量。例如，科学家可能希望确 定分子构型化合物。研究者得出一个公式 f(x)，把可能配置的势能 看作函数的切线x与两个组件之间的角度。然后，因为自然会导致分 子承担最小势能的配置，所以需要找到f(x)的最小值X

10、。这是一个单 变量X的最小化问题。它可能是高度非线性的，由于X可以取任何值， 所以物理函数真的是无约束。如果问题中只有一个变量，那么就可以用第二章的方法轻易解 决。然而我们已经得知相关的问题是一个介于 20到100个变量的函数。 虽然它们一个个不难解决，但每个F的值在5美元到100美元之间，因 此它们合在一起是难以解决的。第二类常见的非线性问题是曲线族中一些最符合实验数据或人口统计数据的曲线选择的种类。举出1.2.1的例题：20个太阳光谱曲 线数据通过卫星提供了波长ti，基本理论暗示任一数据m如(ri, y)，(t 丐y m)都符合钟形的曲线。然而如数据显示，在实践中这点有实验上的错误。为了从

11、数据中得出结论，我们想要无限接近钟形曲线的m点。因此大致钟形的等式为v（xu x2, x3, x4? 0 =+ x2etX32/x这意味着所选的x1, x2, x3, x4 要将数据点与曲线之间的误差最小化，因此用以下公式Mx）全只小，衍，乂3，X4 Mi）-儿最常用的方法是求r的平方和，得出钟形曲线的解决方案是用非线性最小二乘法：min/U) = yfj(x)2 = yUi + 盘厂依切 一 力J心f=li=l这里是注解。第一点，1.2.1的问题是一个非线性最小二乘法问题，余下的函数r，x是非线性函数的变量xi, X2, x 3, x 4。实际上ri在X和X2是线性 的，我们可以用前面提到的

12、方法利用这一优势（详见第10章）。第二点，有一些函数以外的平方和可以用来测量钟形函数数据点 间的距离。图121符合钟形函数的数据点有两个明显的公式:办(x)= f 皿)1! 因为后者计算靠x和y的关系,但前者不是(见练习6)。在量度误差 和算法讨论时需规定相同符号。a i，B i , i=1,2,3，写作a i=0(Bi)。如果存在一常数c,例如所有的正整数i,除了一些有限的 子集a i 1(见 练习7)。例如，在CDC上，当我们讨论计算机数字，数量和 macheps 是非常有用的。例如,我们可以很容易地表明，相对误差在计算机表示 任何非零实数x的fl(x)小于macheps相反，任何计算机表示实数x将 在如下范围内(x(l - macheps)x(l + macheps) 。同理，以下例子非比匚 1 IX)的整数幕，这样你的算法可以像卜保持计算,使你知道程序最后的运行答案。输出这个值和十进制值。(注意:macheps的价值将取决于2个不同的因素舍入或删除