1、 本科毕业论文 （ 20 届） 无约束优化的改进变尺度算法 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 II 摘要 最优化计算是实际应用中的一个十分活跃的数学方法 . 随着计算机的普及 , 已广泛 应用于化工 , 机械 , 建筑等许多工程技术部门 . 而 且在解决生产组织 , 资源分配等管理科学问题时 , 最优化计算也是一种重要方法 . 无约束优化在实际最优化问题中占有很大的比例 , 而 变尺度算法正是解决无约束优化问题最有效的算法之一 . 在本文中 , 我们研究了 变尺度算法的原理和计算步骤 , 通过对比计算证明了算法的优越性 , 其收敛速度快且计算
2、较为简洁 . 并基于 Wei zengxin提出的改进 BFGS公式研究了一类改进的变尺度算法并通过数值实验证明其收敛性 . 关键词： 无约束优化 ; 变尺度 ; DPF; BFGS III IV Abstract Optimization is a very active mathematical method in the practical application. As the computers being more and more popularity, Optimization has been widely used in many engineering departmen
3、t such as chemical industry, machinery and architecture. Even in solving some management science problems like production organization and resource resources, optimization is also an important method. Unconstrained optimization holds a large proportion in practical optimization problems. And Variabl
4、e-dimension is one of the most effective algorithms in solving unconstrained optimization problems. In this dissertation, we studied the principle and the calculation steps of variable-dimension algorithm. We proved the superiority of variable-dimension algorithm through comparing the calculation, w
5、e see its convergence rate is fast and its calculation is very succinct. At last, we studied a new modified BFGS method based on Wei zengxins new modified BFGS formula and proved that it had convergence properties. Keywords: Unconstrained optimization; variable-dimension; DPF; BFGS V 目录 摘要 .I Abstra
6、ct . IV 1 前言 . 1 2 无约束最优化的求解 . 3 2.1 函数的极值点 . 3 2.2 极值点存在的条件 . 3 2.3 梯度法求解 . 5 2.4 Newton 法简介 . 6 3 变尺度算法 . 7 3.1 变尺度法的基本思想 . 7 3.2 变尺度法的基本原理 . 7 3.3 DFP 法 . 8 3.4 BFGS 法简介 . 10 3.5 变尺度法的优越性 .11 3.6 变尺度法的 matlab 实现 . 13 4 变尺度法的改进 . 15 4.1 BFGS 法的改进 . 15 4.2 改进算法的推导 . 15 4.3 改进算法的步骤 . 16 4.4 算法的数值对比
7、. 17 小结 . 20 参考文献 . 21 致谢 . 错误 !未定义书签。 1 1 前言 随着生产和经济的高速发展 , 最优化的方法在越来越多的领域得到了应用 , 可谓是数学在实际应用中最为广泛的方法之一 . 在实际中 , 很多问题的目标函数或约束条件中都含有非线性函数 , 这一类问题就是非线性规划问题 . 非线性规划是最优化问题的一个重要分支 . 其数学模型可写成以下形式 min fx , nxR （ 1.1） 即在 n 维空间 nR 的一个子集 中求目标函数 fx的极小值点和极小值 . 最优化计算方法通常可分为两类 , 即无约束优化和约束优化 . 在（ 1.1）中 , 如果 nR , 则
8、问题被称为无约束非线性规划问题 , 即 minfx , nxR （ 1.2）无约束最优化算法的重要性不仅体现在其本身解决无约束优化问题的应用，而且还可以将一些约束问题转化为无约束问题来处理 . 从这个意义上讲 , 无约束优化算法也是处理约束优化问题的基本方法 . 无约束优化的算法有许多种 , 早在 1847年 , Cauchy就提出了最速下降法 1 , 也称梯度法 . 这就是最早的求解无约束最优化问题的方法 . 对于变量不多的某些问题 , 此方法是可行的 , 但是对于变量较多的一类问题 , 就常常不适用了 . 其原因是除某些特殊情形外 , 计算产生的方程组是非线性的 , 对它的求解十分困难 ;
9、 而最速下降法的收敛速度往往又很慢 . 之后出现并发展了收敛性能较好的牛顿法 2 , 需要计算目标函数的二阶导数 , 故而计算量较大 . 而变尺度法 3 则是既 保持了牛顿法收敛速度快的特点 , 是超线性收敛的 , 又克服了牛顿法计算量大的缺点 . 变尺度算法最早由 Davidon在 1959年提出 , 是无约束最优化计算方法中最为杰出的 , 最富有创造性的工作 . 之后经由 Fletcher 和 Powell 的改进简化 , 于 1963 年形成了Davidon-Fletcher-Powell 法 , 简称 DFP 法 . 1970 年 , Huang 对变尺度算法作了处理，得出了包含 3
10、个自由参数的 Huang 族变尺度法 . 在这之前的 1967 年 , Broyden 也曾提出只包含 1 个自由参数的 Broyden 族变尺度 法 , 现视作 Huang 族变尺度法的一个子族 . 另一著名的变尺度算法 BFGS 法是 Broyden, Fletcher, Goldfarb 和 Shanno 共同研究的结果 , 于 1979 年出世 . 无约束最优化方法已具有较完善的方法 , 但是仍有许多工作可以做 . 在当代的变尺度研2 究中 , Liao aiping 4 在 Byrd 和 Nocedal提供的工具框架下 , 对 BFGS 法作了改进 , 于 1997 年提出了一种双参
11、数修正的拟牛顿法 , 具有更好的适应性 . Xiao yunhai和 Wei zengxin等人也分别对 BFGS 公式做了改进 . 本文 的 第二章 主要介绍了无约束优化求解的条件及基础方法 . 第三章详细介绍了变尺度算法的原理及计算步骤 , 并通过计算显示其优越性 . 第四章 基于 BFGS 法的各类改进公式研究了一类改进的变尺度算法并利用数值实验证明其优越性 . 3 2 无约束最优化的求解 2.1 函数的极值点 求解最优化问题 , 关键就是求出极小点 . 函数的极小点有两种 : 局部极小点和全局极小点 . 在文献 5中做出如下定义 : 定义 2.1 对于 nxR , nxR , 若存在
12、0 , 使得当 xx时 , 总满足 f x f x （ 2.1） 则称 x 是 fx的局 部极小点 . 若当 xx 时 , 式（ 2.3）不等号恒成立 , 则称 x 是 fx的严格局部极小点 . 定义 2.2 对于任意 nxR , 若存在 nxR , 使得式（ 2.1）恒成立 , 则称 x 是 fx的全局极小点 . 若当 xx 时 , 式（ 2.1）不等号恒成立 , 则称 x 是 fx的严格全局极小点 . 尽管在解决现实问题的计算中 , 我们要寻找的往往是全局极小点 , 但现有的理论和算法大多只能近似求出局部极小点 . 所以一般地说 , 求解无约束最优化问题的算法都是通过多次迭代 , 设法寻找
13、多个局部极小点，然后将其中取值最小的那个极小点近似的作为全局极小点 . 2.2 极值点存在的条件 首先根据文献 6介绍梯度和海塞矩阵的定义 . 定义 2.3 设 R 是 nR 上的开集 , xR , 若 fx 对 1, Tnx x x 各分量的一阶偏导数都存在 , 即函数 fx在点 x 处一阶可导 , 则称向量 12,Tnf x f x f xfxx x x （ 2.2） 为函数 fx在点 x 处的梯度 . 定义 2.4 设 R 是 nR 上的开集 , xR , 若 fx 对 1, Tnx x x 各分量的二阶偏导数都存在 , 即函数 fx在点 x 处二阶可导 , 则称向量 4 2 2 221
14、 1 2 12 2 22 22 1 2 22 2 2212Tnnn n nf x f x f xx x x x xf x f x f xfx x x x x xf x f x f xx x x x x （ 2.3） 为函数 fx在点 x 处的 Hesse 矩阵 Hx . 下面说明极值点存在的必要条件和充分条件 . 定理 2.1（必要条件） 设 R 是 nE 上某一开集 , fx在 R 上有一阶连续偏导数 , 且在点x R 取得局部极值 , 则必有 120nf x f x f xx x x 即 0fx. 证明 : 可反证 , 假设 0fx, 取 p f x , 则有 2 0TTf x p f x
15、 f x f x , 那么 p 就是 f 在点 x 处的下降方向 , 即存在 0 , 使得 f x tp f x , 0,t . 取 p , 由 t 得 tp p, 故存在点 x x tp, 使 f x f x , 这与 x 是局部极点相矛盾 . 定理 2.2（ 充分条件） 设 R 是 nE 上某一开集 , fx在 R 上有二阶连续偏导数 , xR , 5 若 0fx, 且 2fx 正定 , 则 x 为 fx的严格局部极小点 . 证明 : 对任意 0t 和 0p , 由 0fX, 有二阶 Taylor 展式 22212 Tf x t p f x t p f x p o t p , 2fx 正定
16、 , 那么 2 0Tp f x p, 故存在 0 , 使 2221 0 , 0 ,2 Tf x t p f x t p f x p o t p t , 即 存在任意点 x x tp, 使 f x f x , 故 x 为 fx的严格局部极小点 . 2.3 梯度法求解 在求解无约束极值问题的方法中 , 梯度法是最古老和最基础的方法 . 下面通过例题简单介绍梯度法的求解步骤 . 例 1 用梯度法求 221211f X x x 的极小点 , 终止误差 0.1 解 取初始点 0 0,0 TX 此时分别计算得 122 1 , 2 1 Tf X x x 0 2, 2 TfX 22 220 2 2 8fX 20fX 则继续进行迭代 . 2002HX
