无约束最优化与非线性方程的数值方法-介绍(原版译文方便论文写作)

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

2、理假设下建立的数学等价，但我们不打算用相同的算法来处理，而打算展示当前最佳的算法是如何找出每个问题的结构。联立非线性方程问题（现在简称“非线性方程”）是三大非线性方程问题中最基础的，并且计算中可利用的结构最少。公式如下：已知在公式中 表示n维欧氏空间。当然，(1.1.1)只是表示含未知数“n”的n非线性方程的标准公式，方程式的右边通常是零。例如：如果已知且(1.1.1) 公式中计算出来的必然会是的最小值。表示F的第i个组成函数。这是无约束极小化问题的特殊例子。 （1.1.2）是我们要考虑的第二个问题。通常（1.1.2）是的缩写。例如： 可以得出在一些应用中，有人对解决（1.1.3）受限版本有兴

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

4、但是由于它的重要性以及它特殊的结构，其本身就构成一个研究领域。这就是非线性最小二乘问题： 表示的第i个组成函数。（1.1.5）在曲线拟合中是最常见的，除此之外当线性系统的线性需求比自由度多时它也会出现。当非线性函数、至少有一个、两个或者分别有两个连续不同数时，我们只考虑最常见的例子。要是函数是充分平滑的，我们不一定要用假设，导数就可通过分析得出。对于今天正在解决的非线性问题的典型规模以及其它特点的进一步阐释，可看1.2节。在非线性问题的数值解的典型的场景中，计算者须提供评估函数的一个子程序，并且起始点是的大概近似值。如果可行，计算者还需提供第一个导数，或许还有第二个导数。我们这本书的重点是解决

5、在这个框架中遇到的最常见的一些困难：（1）如果起始点和最终的答案（全局方法）不是近似值该如何解决以及如何用区域变量来有效的联合（局部方法）这个问题；（2）以及如果没得出解析导数应该如何处理；（3）如果问题函数的求值用精确的算法将会是高效的（算法往往不精确）。我们研究的基本方法以及提供的基本算法思路是当前解决这些问题的最好方法。我们也给出了自认为是理解这些方法和，扩展或改进这些问题的相关分析。尤其是，我们试图辨别并强调这些在这个领域已经演变为中心的理念和方法。我们认为这个领域已经到达了一个可识别技术的点,这个点很可能还可改进,但不大可能如量子跳跃般超越目前最好的算法。解决非线性方程和无约束最小化

6、的问题的方法很相似。这本书大部分是关于这两个问题的。非线性最小二乘问题只是无约束极小化的一个特例,但可以利用非线性最小二乘问题的特殊结构调整无约束极小化技术获取更好的算法。因此第十章用一个广泛可行的例子说明了如何应用和扩展前部分的内容。在这本书中,我们没有解决的问题是找出一个非线性函数的极小点，这个变量是在出现许多个不同的局部极小值的情况下的绝对最低点。（1.1.2）的解答是，是开放区域的连接。这是一个非常难的问题,并无广泛的研究也不像我们已解决的问题那样容易。涉及此问题的两个论文集分别是(1975,1978).通观全书我们会使用到“全局 ”、“全局法” 或者“全局收敛法”这些词语来表示一种算

7、法，这种算法是专门设计用来汇集非线性函数的全局极小点、或者是任何一个非线性方程组的起始点的一些解法。把这些算法叫做“局部”或者“局部收敛”是比较合适的，但在另一个算法上这些说明已经被传统保留了，对于一般算法来说确保从每个起始点收敛的方法或许是低效的（选自Allgower and Georg (1980)）。1.2 “真实世界”问题的特征在这节中我们提供一些关于实践中遇到的非线性问题。首先我们列举了三个真正的非线性问题的例子和一些参与设置数值问题的思考。然后我们对大小、费用和其他非线性问题中遇到的一般特征作出了评价。讨论样品问题的困难之一是在这一领域的背景和代数描述的问题很少是简单的。虽然这使得

8、咨询工作很有趣,但对于介绍性数值分析的书是没有什么帮助的。因此,我们尽可能简化我们的示例。最简单的非线性问题只包含一个变量。例如,科学家可能希望确定分子构型化合物。研究者得出一个公式f(x)，把可能配置的势能看作函数的切线x与两个组件之间的角度。然后,因为自然会导致分子承担最小势能的配置,所以需要找到f(x)的最小值x。这是一个单变量x的最小化问题。它可能是高度非线性的, 由于x可以取任何值，所以物理函数真的是无约束。如果问题中只有一个变量，那么就可以用第二章的方法轻易解决。然而我们已经得知相关的问题是一个介于20到100个变量的函数。虽然它们一个个不难解决，但每个F的值在5美元到100美元之

9、间，因此它们合在一起是难以解决的。第二类常见的非线性问题是曲线族中一些最符合实验数据或人口统计数据的曲线选择的种类。举出1.2.1的例题：20个太阳光谱曲线数据通过卫星提供了波长ti，基本理论暗示任一数据m如(ri, yi), ., (tm, ym)都符合钟形的曲线。然而如数据显示,在实践中这点有实验上的错误。为了从数据中得出结论，我们想要无限接近钟形曲线的m点。因此大致钟形的等式为 这意味着所选的x1, x2, x3, x4要将数据点与曲线之间的误差最小化，因此用以下公式最常用的方法是求r的平方和，得出钟形曲线的解决方案是用非线性最小二乘法：这里是注解。第一点，1.2.1的问题是一个非线性最

10、小二乘法问题，余下的函数r，x是非线性函数的变量x1, x2, x3, x4。实际上ri在X1和X2是线性的，我们可以用前面提到的方法利用这一优势（详见第10章）。 第二点，有一些函数以外的平方和可以用来测量钟形函数数据点间的距离。图1.2.1符合钟形函数的数据点有两个明显的公式： 通常选择f (x)而不是f1 (x) 或f0(x)，有时候是因为统计的问题，有时候是因为简化的结果很难处理。因为最小二乘法函数是不断可微分的，但是其它两个却不是。在练习中大多数数据拟合问题都是用最小二乘法解决的。通常是通过余数进一位，但这对我们的讨论不重要。最后一个例子，我们在研究核聚变反应堆的过程中遇到了一个问题

11、。核聚变反应堆可以在内部加入高温等离子体塑造成圆环状。（详见图1.2.2）问题可以简化成：我们要找到内圆半径r、圆环的宽w和等离子体的温度t就可以得出每单元能源的最低成本。科学家得出以下公式计算每单元能源的最低成本：cl、c2, 、c3、c4是常数。因此非线性问题可以简化为一个r、w、t的函数。然而关于这个问题还有其它重要的方面。第一，不像之前例子最后的那个变量，r、w和t不能随便赋值。比如说r和w不能是负数。图1.2.2 核聚变反应堆因此这是一个不能轻视的问题。这三个变量总共有5个将影响到解决方案的限制。当约束影响到解决方案时，问题就不能同样当成函数解决。在核反应堆问题上这些限制很重要。因此

12、要用技术强制解决。然而很多简单的约束问题，如对变量的界限都可以无约束地解决。因为限制满足不受限制的最低要求。注意，我们在核反应堆中提到的限制通常会起很大作用。这是因为实际上由于cl、c2, 、c3和c4的常数值不同，我们要解决625个问题。这些常数的值取决于因素，如电力成本。这将是恒定的反应器的运行，但不知到何时。它运行的问题得视不同的情况而定。但是当核反应堆在运行时，电力成本也在不断变化。因此有必要不断改变条件以寻找反应堆最佳的特征。通常在实践中，需要解决在不同情况下的特定问题，这使算法的效率更为重要。这也使我们用不同的算法去评估这些因素特定的级别。最后，这条等式（1.2.2）只是简单粗略地

13、反映核聚变反应堆。在下一小节的学习中，函数给出的每单元能源消耗并不十分准确，就像（1.2.2）。因为它是一个用偏微分方程算出的结果。这里有5个参量（见图1.2.3）。这类函数的精确度在非线性问题中很有限，并且它对运算法则的改进有很大作用。第一，这类函数只是在某些很小的区域内较为准确，因此解决问题时过多要求准确性是没有意义的。第二，这类函数可能在大多时候是不断地可以被微分的，通常无法得到它的导数。这就是为什么导数的近似值变得如此重要了。最后求值可能就会很困难，需要进一步估算。以上问题给出了一些典型的非线性问题典型的特征的指示。首先是它们的规模。虽然实际变量比讨论的变量多，但大多数我们看到的变量相

14、对较少，有2到30个。图1.23以核聚变反应堆的函数估算我们希望能解决大部分的小问题。比如215个的变量。但是其实2个变量就已经很复杂了。现在的运算法则已经可以解决有1550个变量的中等难度的问题了。但是多余50个变量的问题确实是难题，除非它们只是简单的非线性问题或者有人猜想我们不可能将它们简便地解决。这些大小的估计是非常不稳定的，它们较少依赖于算法、更多依赖于快速存储的实用性和计算环境的其他方面。第二个问题是，导函数的可用性。我们经常处理的非线性函数本身是计算机模拟的结果，或是由一个冗长又繁琐的代数公式得来的。因此通常情况下导函数是不可求的，尽管函数是可以不断被微分的。因此在缺乏可分析的导函

15、数的情况下有一个有效率的运算法则是很重要的。事实上如果计算机子程序库包括导函数，用户也几乎不会分析它。谁能怪它们呢？ 第三，如上所述，许多非线性问题是很难解决，要么是因为非线性函数反复进行，要么是要解决的任务牵扯到太多问题了。我们都听说过一个有50个变量的石油工程，其一个功能的每次评估就要花费IBM3033,100小时。算法运行时间和函数和导函数的估算效率是发展非线性算法的一个重要问题。第四，在很多应用中，用户希望答案中只有少数精确的数字。这首先是由于其它问题的近似性质：函数，其它模型参数，数据。另一方面用户通常要求更精确。尽管希望更精确是合乎情理的，但是也要合理地接受会有集合的存在，因为提供

16、的精确度很少能接近电脑的精确度。第五，没有考虑到缩放比例。这意味着变量的大小不同，结果也会有很大不同。比如说一个一个变量可能总是在106107之间，而另一个变量在110之间。 在我们的经验中，这种情况经常发生。然而这一领域的大多数工作一直没有注意到缩放比例的问题。在这本书中我们尝试指出忽略缩放比例会降低非线性算法的性能。我们试图纠正算法中的不足。最后，在这本书中我们只讨论这些非线性问题。其中的未知数是可以有真正的值的，相反那些变量必须是整数。一般说来，这是一个现实的限制。答案是非线性问题中肯定有些变量必须是整数,因为他们代表等人、卡车或大型工具。然而,这种限制使得问题更加难以解决由于连续性缺失

17、我们通常通过将离散变量取整来解决这些问题。这一理论并不能保证这种方法能够解决整数问题,但实际上它通常能在特殊情况下得出合理的答案。一些离散变量约束只能是数值0、1或2。在这种情况下,必须使用离散方法（例如Beale(1977), Garfinkel和Nemhauser(1972)。)1.3有限精度算法和测量误差计算机程序法有一些特点,收敛性的判断取决于精确实数在电脑上的表示。有时,算术编码也受对计算机运算理解的影响。因此,我们需要简述有限精度算法,这是真正的电脑版本算术（更多信息请参考Wilkinson(1963)）。在科学记数法中，数字51.75被写作+ 0.5175 *10+2写的。电脑用

18、同样的方式代表实数,在我们的例子中使用一个标志(+),一个基数(10),一个指数(+ 2),和一个尾数(0.5175)，使之具有惟一的代表。通过指定/基地<尾数<1,第一个数字的右边“十进制”点是零。尾数的长度,称为表示的精度,这对数值计算是特别重要的。实数的表示在电脑上被称为浮点表示,fl(x)是x的浮点表示。在CDC机器上基数是2,尾数有48位。因为2481014.4这意味着我们可以准确储存14个小数位数。指数的范围可以从-976到+ 1070,这样最小和最大数字是大约10-294和10322。在IBM机器基数是16,尾数单精度6位双精度14位,分别对应于约7和16个小数位数。

19、指数的范围可以从-64到+ 63,这样的最小和最大数字是大约10-77和1076。只有一个有限的精度对存储实数非常重要,但他们能被简单地概括出来。第一,因为并不是每个实数可以在电脑上准确显示,最好可以得到符合计算机精度的准确答案。其次,根据计算机和编译器,每个由机器计算的中间算术运算的结果是被删减或四舍五入的数据。因此,由于有限精度的不准确，可能积累并进一步降低结果的准确性。这些错误被称为舍入错误。虽然舍入的影响可能相当微妙,只是仍然存在三个基本的情况，可以过度影响计算精度。首先是添加一个数字序列,特别是在数字绝对值减少；由于中间结果的表示是有限的，右边的部分较小的数据容易丢失 (例如，练习4

20、）。第二个是采用两个几乎相同的不同数字；因为左边主要数字差异为零而精度丢失 (例如,练习5) 。第三是近奇异系统的线性方程组的解,这个在第三章讨论。这种情况实际上是前两个的结果,但它是如此基本和重要,我们更愿意把它看作第三个基本问题。如果一个人在书面作业或者电脑程序上意识到这三种情况,可以理解和避免许多与有限精度算法有关的问题。由于有限精度算法的使用,甚至是算法的迭代性,我们不能得到大多数非线性问题的准确答案。因此我们经常得求出x和y的关系。我们通常采用的解题思路是取相对误差在一个非零的x、y作为近似数, 这是可取的,除非x = 0时,使用绝对误差, 因为后者计算靠x和y的关系,但前者不是(见

21、练习6)。在量度误差和算法讨论时需规定相同符号。i，i，i=1,2,3，写作i=0（i）。如果存在一常数c，例如所有的正整数i,除了一些有限的子集ic*i。这个不等式表明每个i小于或等于它所对应的i。（详见Aho, Hopcroft, and Ullman 1974.）有限精度算法的另一个效应是,某些方面的算法,如停止标准,将取决于机器的精度。因此,为了描述机器精度的方式介绍讨论和计算机程序可以合理地独立于任何特定的机器.常用的概念“machine epsilon”,缩略为macheps；被定义为最小的正数t,由此1 + t > 1(见练习7)。例如，在CDC上，当我们讨论计算机数字，数

22、量和macheps是非常有用的。例如,我们可以很容易地表明,相对误差在计算机表示任何非零实数x的fl(x)小于macheps。相反,任何计算机表示实数x将在如下范围内(x(l - macheps)x(l + macheps)。同理,以下例子非常常见。解决view macheps的关键是根据题意判断x的有限精度。我们习惯于首先将x赋值为0. 在有限精度下，0代表包含0的范围区间(1 macheps)*x,（1 + macheps）*x)。在计算的过程中，有限精度数字(x + y)=(x)。有时,在数值线性代数算法上,将y=0代入计算是有效的。最后,任何计算机用户应该知道,溢出和下溢的发生条件是在机器中计算生成一个非零的数,指数分别大于或小于0。例如,当我们在CDC上的值为10322会出现下溢,在IBM上的值为10-77会上溢。在溢出的情况下,几乎所有的机器将终止运行并显示错误。下溢的情况下,往往是一个编译器选项终止,或者代替零的表达。有时后者的选择是合理的,但也不一定(见练习8)。幸运的是,当一个人使用编写良好的线性代数的例程, 算法中通常不容易溢出或下溢。3.1节中讨论的例子，需要细心计算欧几里得范数的向量, 1.4