信赖域法示例浅析

信赖域法示例浅析

摘要：本文介绍了非单调信赖域算法的基本知识，包括非单调信赖域算法的理论、算法框图及数值运算实例，数值结果表明该算法在求解高维非线性规划问题时比一般算法更有效。

关键词：信赖域法信赖半径Hesse阵Bk

引言

信赖域方法是求解非线性规划问题的常用方法之一，因其具有良好的可靠性和强健的收敛性备受非线性优化领域专家们的关注[1]，信赖域方法与线搜索技术一样，也是优化算法中的一种保证全局收敛的重要技术。它们的功能都是在优化算法中求出每次迭代的位移，从而确定新的迭代点。漂亮的收敛性和有效的计算性确定了信赖域算法是一类重要和实用的方法[2]。因此研究约束优化问题的信赖域算法具有重要的意义。

1、算法的基本理论

与线搜索技术相比不同的是：线搜索技术是先产生位移方向（亦称为搜索方向），然后确定位移的长度（亦称为搜索步长）。而信赖域技术则是直接确定位移，产生新的迭代点。信赖域方法的基本思想是：首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后，通过求解这个区域内的“信赖域子问题”（目标函数的二次近似模型）的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量，则接受该候选位移作为新的位移，并保持或扩大信赖域半径，继续新的迭代。否则，说明二次模型与目标函数的近似度不够理想，需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。

2、信赖域方法解决无约束线性规划的基本算法结构

设■是第■次迭代点，记是Hesse阵■的第■次近似，则第■次迭代步的信赖域子问题具有如下形式：

其中■是信赖域半径，■是任一种向量范数，通常取2-范数或∞-范数。定义■为■在第■步的实际下降量：

定义■对应的预测下降量：

定义他们的比值为：。一般的，我们有■。因此，若■，则■，■不能作为下一个迭代点，需要缩小信赖半径重新求解问题。若■比较接近于1，说明二次模型与目标函数在信赖与范围内有很好的相似，此时■可以作为新的迭代点，同时

最优化方法——信赖域法

信赖域法 董文峰，03，R数学08-1班伊广旭，03，R数学08-1班李超，04，R数学08-1班 一、算法理论

信赖域方法与线搜索技术一样, 也是优化算法中的一种保证全局收敛的重要技术. 它们的功能都是在优化算法中求出每次迭代的位移, 从而确定新的迭代点.所不同的是: 线搜索技术是先产生位移方向(亦称为搜索方向), 然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移, 产生新的迭代点。 信赖域方法的基本思想是:首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭代。否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。 信赖域方法解决无约束线性规划 f(x)R x ∈min 的基本算法结构。设k x 是第k 次迭代点，记)f(x f k k =，)f(x g k k ?=，k B 是Hesse 阵)f(x k 2?的第k 次近似，则第k 次迭代步的信赖域子问题具有如下形式： ,2 1g (d)min T k d B d d q k T k += k d t s ?≤.. 其中k ?是信赖域半径，?是任一种向量范数，通常取2-范数或∞-范数。 定义k f ?为f 在第k 步的实际下降量： ),d f(x f Δf k k k k +=- 定义k q ?对应的预测下降量： ()().-0k k k k d q q q =? 定义他们的比值为： k k k q f r ??= 一般的，我们有0>?k q 。因此，若0

一种新的二次插值模型算法

一种新的二次插值模型算法 周庆华 【期刊名称】《工程数学学报》 【年(卷),期】2006(023)006 【摘要】本文中,通过利用随算法表现出来的问题的局部信息,我们构造了几种新的搜索子空间,然后对二次插值模型在这些子空间中进行求解.目的是利用前面的迭代信息构造问题更有可能下降的方向.实验证明我们的方法对于大多数问题都可以有效的减少函数值的运算次数.%In this paper, several new search directions are constructed by combining the local infor mation progressively obtained during the iteration of the algorithm to form new subspaces, the quadratic model is then solved in the new subspaces. The purpose is to use the information disclosed by previous steps to construct more promising directions. The effectiveness is demonstrated in that the number of function evaluations are reduced significantly for most tested problems. 【总页数】13页(1075-1087) 【关键词】无约束优化;信赖域方法;二次模型;Lagrange函数;直接法 【作者】周庆华 【作者单位】中国科学院数学与系统科学研究院,计算数学科学与工程计算研究院,科学与工程计算国家重点实验室,北京,100080 【正文语种】中文 【中图分类】O24

圆锥摆模型

一、经典例题 1．将一个半径为的内壁光滑的半球形碗固定在水平地面上，若使质量为的小球贴着碗的内壁在水平面内以角速度做匀速圆周运动，如图所示，求圆周平面距碗底的高度。若角速度增大，则高度、回旋半径、向心力如何变化？ 点评：实质是圆锥摆模型：球面的弹力类比于绳的拉力，球面半径类比于绳长 2．一光滑的圆锥体固定在水平桌面上，其轴线沿竖直方向，其顶角为60o，如图所示，一条长为的轻绳，一端固定在锥顶点，另一端拴一质量为的小球，小球以速率绕圆锥的轴线做水平面内的匀速圆周运动，求： （1）当时，绳上的拉力多大？ （2）当时，绳上的拉力多大？ 1

3．圆锥摆模型的特点： 结构特点：一根质量和形变量可以不计的细绳，一端系一个可以视为质点的摆球，使小球在水平面内做匀速圆周运动。 受力特点：只受两个力即竖直向下的重力以及沿摆线方向的拉力。两个力的合力就是摆球做匀速圆周运动的向心力 4．关键求出临界时的速度，判断物体对圆锥体是否有压力。 5．（1）了解圆锥摆及其拓展模型受力特点，合力提供向心力 （2）圆锥摆中弹力与竖直方向成的角可起“桥梁”作用 二、相关练习题 1．如图所示，长为L的细绳一端固定，另一端系一质量为m的小球。给小球一个合适的初速度，小球便可在水平面内做匀速圆周运动，这样就构成了一个圆锥摆，设细绳与竖直方向的夹角为θ。下列说法中正确的是 2

3 A ．小球受重力、细绳的拉力和向心力作用 B ．细绳拉力在水平方向的分力提供了向心力 C ．θ越大，小球运动的周期越大 D ．θ越大，小球运动的线速度越大 2．如图所示，两个质量不同的小球用长度不等的细线拴在同一点并在同一水平面内做匀速圆周运动，则它们的( ) A ．运动周期相同 B ．运动的线速度相同 C ．运动的角速度相同 D ．向心加速度相同 3．如图所示，两段长均为L 的轻质线共同系住一个质量为m 的小球，另一端分别固定在等高的A 、B 两点，A 、B 两点间距也为L .现使小球在竖直平面内做圆周运动，当小球到达最高点的速率为v 时，两段线中张力恰好均为零，若小球到达最高点速率为2v ，则此时每段线中张力为多大？(重力加速度为g )

圆锥摆模型全透视

1 圆锥摆模型全透视 一、圆锥摆模型： 1．结构特点：一根质量和伸长可以不计的线，系一个可以视为质点的摆球，在水平面内作匀速圆周运动。 2．受力特点：只受两个力：竖直向下的重力mg 和沿摆线方向的拉力F 。两个力的合力，就是摆球作圆周运动的向心力F n ，如图示。 二、常规讨论： 1． 向心力和向心加速度： 设摆球的质量为m ，摆线长为l ，与竖直方向的夹角为θ，摆球的线速度为v ，角速度为ω，周期为T ，频率为f 。 n n ma F =， θ πθπ θωθθsin )2(sin )2(sin sin tan 2222l f m l T m l m l v m mg ====， θπθπ θωθθsin )2(sin )2(sin sin tan 2222l f l T l l v g a n ===== 2． 摆线的拉力： 有两种基本思路：当θ 角已知时θ cos /mg F =，当θ角未知时 l f m l T m l m F F n 22 2)2()2( sin /ππωθ==== 3． 周期的计算： 设悬点到圆周运动圆心的距离为h ，根据向心力公式有g h g l T π θπ2cos 2==，由此可知高度相同的圆锥摆，周期相同，与θ,,l m 无关。 4．动态分析：当角速度ω增大时，根据θωθsin tan 2 R m mg =有R g 2 cos ωθ= ，ω增大，θ增大， 向心力增大，回旋半径增大，周期变小。 三、典型实例： 例1：将一个半径为R 的内壁光滑的半球形碗固定在水平地面上，若使质量为m 的小球贴着碗的内壁在水平面内以角速度ω做匀速圆周运动，如图，求圆周平面距碗底的高度。若角速度ω增大，则高度、回旋半径、向心力如何变化？

试验室科研能力及服务项目情况

实验室科研能力及服务项目情况 （1）若干重要问题如大型线性方程组迭代解法、矩阵特征值问题的理论和数值 方法、代数特征值反问题的理论和数值解法、矩阵方程与矩阵逼近等进行了系统的研究，提出了新的概念、理论和方法，取得了一系列高水平且具有特色的研究成果 2．数学规划算法-主要致力于数学规划理论、算法和应用软件的研究及其在工程实际中的应用.近二十多年来，主要研究大规模最优化理论、方法与软件，无约束最优化问题的理论与方法，非光滑最优化理论与方法，组合优化理论与方法等。在当今国内外研究热点—SQP方法、有限存储方法、锥模型算法、非光滑最优 化条件、非线性向量互补问题与变分不等式、最小支撑树和最短网络等方面取得了一系列研究成果。 3．偏微分方程数值解法及其应用.自八十年代初以来，偏微分方程数值解法及其 应用一直是我校计算数学硕士学科点的稳定研究方向。经戴嘉尊教授和年轻数学工作者的不断建设和发展，特别是特聘教授陆云光博士的加盟，该研究方向已形成了一支实力雄厚、年龄结构合理的学术梯队，已成为我国在该领域开展研究工作最活跃的单位之一。 2．服务项目 （1）构造了解一般稠密大规模非线性规划问题的算法, 并建立了相关理论, 开发了有效的软件, 进行了大量数值试验。其主要贡献是成功地把有限储存技术和截断求子问题途经应用于一般大问题。研究成果已经以33页的篇幅发表在国际著名杂志《Optimization Methods and Software》上。 （2）非线性规划理论与算法的研究. 十多年来，我们主要研究大规模与非光滑最优化理论与方法。在国际核心杂志上发表论文50余篇，其中子空间拟牛顿方法发表在《Mathematics of Computation》(1997,vol.66,no.220)杂志上，已被SCI收录论文他引3次，有限储存截断对偶SQP方法的论文以33页的篇幅发

新北师大版六年级数学下册《圆锥的认识》公开课教案_14

圆锥的认识 一.学习内容 《义务教育教科书数学》（人教版）六年级下册第31—32页例1。 二.教学目标 1、认识圆锥，建立圆锥的几何模型，能明确指出圆锥的各部分名称及特征。 2、认识圆锥的高，能准确测量圆锥的高，发挥动手操作的能力，逐步形成严谨求学的科学态度。 3、通过动手制作圆锥图形和旋转实验，直观感知平面图形与立体图形之间的联系，发展空间观念。 三、教学重点 建立圆锥的几何模型，能明确指出圆锥各部分名称及特征。 四、教学难点 能准确测量圆锥的高。 五、配套资源 实施资源：《圆锥的认识》名师教学课件、圆锥的模型，尺子等 二、教学设计 （一）课前设计 1．预习任务 （1）回忆我们是从哪些方面来认识圆柱特征的？它的特征是什么？用自己喜欢的方式进行整理。 （2）收集生活中圆锥形的物体，并观察它们有什么共同的特点？ （二）课堂设计 1.谈话导入 师：课前大家已经收集一些圆锥形的物体，谁来展示一下？ 找1—2名学生展示。 师：老师也收集了一些，请大家欣赏。我收集的与你们收集的这些物体的形状有什么共同的特点？ 师：这些物体的形状都是圆锥体，简称圆锥。（课件出示圆锥立体图）

这节我们一起来认识圆锥。板书课题。 2.问题探究 （1）圆锥的特征 ①迁移类比，引发思考 师：我们在认识圆柱的时候，是从哪些方面认识它的？ 独立思考后，自由发言。 引导小结：从底面、侧面、高和侧面展开图。 师：现在认识圆锥，它与圆柱有没有相像的地方？你想从哪方面来认识它？ 预设：底面、侧面、侧面展开、高等（根据学生发言板书） ②观察操作，认识特征 师：现在借助手中的圆锥实物来认识它？ 同桌两人合作。 ③汇报展示，归纳小结 预设1：圆锥的面 生汇报交流。 引导小结：底面是一个圆，侧面是一个曲面，圆锥有一个顶点。 预设2：圆锥高的认识 师：高在哪里？谁愿意指给大家看？ 引导学生评价。 师：从圆锥的顶点到底面圆周长上任意一点的距离，是不是圆锥的高？为什么？ 学生评价判断。 师：那什么是圆锥的高呢？ 学生试着用自己的语言描述。 引导小结：从圆锥的顶点到底面圆心的距离叫做高。 师：圆柱的高有无数条，圆锥的高有几条？为什么？ 小结：沿着曲面上的线都不是圆锥的高，圆锥的高只有一条。 课件演示画高，标上字母h。 预设3：圆锥的侧面展开图

高中物理圆锥摆模型全透视

圆锥摆模型全透视 一. 圆锥摆模型 1. 结构特点：一根质量和伸长可以不计的细线，系一个可以视为质点的摆球，在水平面内做匀速圆周运动。 2. 受力特点：只受两个力即竖直向下的重力mg 和沿摆线方向的拉力F T 。两个力的合力，就是摆球做圆周运动的向心力 F n ，如图1所示。 二. 常规讨论 1. 向心力和向心加速度 设摆球的质量为m ，摆线长为l ，与竖直方向的夹角为θ，摆球的线速度为v ，角速度为ω，周期为T ，频率为f 。 F ma mg m v l n n ===tan sin θθ 2 ===m l m T l m f l ωθπ θπθ2222sin ()sin ()sin a g v l l n == =tan sin sin θθ ωθ2 2 ==( )sin ()sin 222 2πθπθT l f l 2. 摆线的拉力 图1

有两种基本思路：当θ角已知时 F mg T = cos θ ；当θ角未知时 F F m l T n = =sin θω2==()()2222π πT l m f l 3. 周期的计算 设悬点到圆周运动圆心的距离为h ，根据向心力公式有 T l g h g ==22π θπcos ，由此可知高度相同的圆锥摆周期相同与m l 、、θ无关。 4. 动态分析 根据m g ml t a n s i n θωθ =2 有cos θω=2g l ，当角速度ω增大时，向心力增 大，回旋半径增大，周期变小。 三. 典型实例 【例1】将一个半径为R 的内壁光滑的半球形碗固定在水平地面上，若使质量为m 的小球贴着碗的内壁在水平内以角速度ω做匀速圆周运动，如图2所示，求圆周平面距碗底的高度，若角速度ω增大，则高度、回旋半径、向心力如何变化 【解析】本题属于圆锥摆模型，球面的弹力类比于绳的拉 力，球面半径类比于绳长。m g mR t a n s i n θωθ=2 ，故cos θω= g R 2 ， 圆周平面距碗底的高度为h R R R g =-=- cos θω 2 。若角速度ω增 图2

信赖域法示例浅析

信赖域法示例浅析 摘要：本文介绍了非单调信赖域算法的基本知识，包括非单调信赖域算法的理论、算法框图及数值运算实例，数值结果表明该算法在求解高维非线性规划问题时比一般算法更有效。 关键词：信赖域法信赖半径Hesse阵Bk 引言 信赖域方法是求解非线性规划问题的常用方法之一，因其具有良好的可靠性和强健的收敛性备受非线性优化领域专家们的关注[1]，信赖域方法与线搜索技术一样，也是优化算法中的一种保证全局收敛的重要技术。它们的功能都是在优化算法中求出每次迭代的位移，从而确定新的迭代点。漂亮的收敛性和有效的计算性确定了信赖域算法是一类重要和实用的方法[2]。因此研究约束优化问题的信赖域算法具有重要的意义。 1、算法的基本理论 与线搜索技术相比不同的是：线搜索技术是先产生位移方向（亦称为搜索方向），然后确定位移的长度（亦称为搜索步长）。而信赖域技术则是直接确定位移，产生新的迭代点。信赖域方法的基本思想是：首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后，通过求解这个区域内的“信赖域子问题”（目标函数的二次近似模型）的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量，则接受该候选位移作为新的位移，并保持或扩大信赖域半径，继续新的迭代。否则，说明二次模型与目标函数的近似度不够理想，需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。 2、信赖域方法解决无约束线性规划的基本算法结构 设■是第■次迭代点，记是Hesse阵■的第■次近似，则第■次迭代步的信赖域子问题具有如下形式： 其中■是信赖域半径，■是任一种向量范数，通常取2-范数或∞-范数。定义■为■在第■步的实际下降量： 定义■对应的预测下降量： 定义他们的比值为：。一般的，我们有■。因此，若■，则■，■不能作为下一个迭代点，需要缩小信赖半径重新求解问题。若■比较接近于1，说明二次模型与目标函数在信赖与范围内有很好的相似，此时■可以作为新的迭代点，同时

信赖域方法概论

非线性优化中的信赖域方法及其应用 摘要 信赖域方法是非线性优化的一类重要的数值计算方法它在近二十年来受到了非线性优化研究界非常的重视。特别是最近几年，一直是非线性优化的研究热点。目前，信赖域方法已经和传统的线收索方法并列为非线性规划的两类主要数值方法。 关键词：信赖域法非线性优化约束条件 引言 非线性最优化是20世纪50年代发展起来的，它讨论非线性决策问题的最佳选择之特性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现。随着电子计算机的发展和应用，非线性最优化理论和方法有了很大发展。目前，它已成为运筹学的一个重要分支，并且在自然科学，工程技术，经济管理，系统工程，特别是“优化设计”等诸多领域得到广泛的应用，成为一门十分活跃的学科。 非线性优化的传统方法几乎都是线搜索类型的方法，即每次迭代时产生一搜索方向，然后在搜索方向上进行精确的或不精确的一维搜索，以得到下一个迭代点。信赖域方法是一类很新的方法，它和线搜索法并列为目前求解非线性规划的两类主要的数值方法。信赖域方法思想新颖，算法可靠，具有很强的收敛性，它不仅能很快地解决良态问题 ,而且也能有效地求解病态(ill-conditioned)的优化问题。因而对信赖域方法的研究是近20年来非线性规划领域的一个重要的研究方向，是当今寻求如何构造新的优化计算方法的主要途径。 信赖域方法的研究起源于Powell 1970 年的工作，他提出了一个求解无约束优化问题的算法，该算法在每次迭代时强制性地要求新的迭代点与当前的迭代点之间的距离不超过某一控制量。引入控制步长是因为传统的线搜索方法常常由于步长过大而导致算法失败，特别是当问题是病态时尤为如此。控制步长实质上等价于在以当前迭代点为中心的一个邻域内对一个近似于原问题的简单模型求极值。这种技巧可理解为只在一个邻域内对近似模型信赖，所以此邻域被称为信赖域(trust region)。利用这一技巧的方法也就被称为信赖域法。信赖域的大小通过迭代逐步调节。一般来说,如果在当前迭代模型较好地逼近原问题，则信赖域可扩大，否则信赖域应缩小。后来，人们发现信赖域方法的基本技巧在一定意义下等价于十分著名的求解非线性最小二乘问题的Levenberg - 2Marquadt方法。 一、算法理论 信赖域方法与线搜索技术一样，也是优化算法中的一种保证全局收敛的重要技术。它们的功能都是在优化算法中求出每次迭代的位移，从而确定新的迭代点.所不同的是: 线搜索技术是先产生位移方向(亦称为搜索方向)，然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移，产生新的迭代点。

信赖域方法

信赖域方法 信赖域方法在当前搜索点附近具有一个区域，其中关于局部极小化的二次模型 被"信赖"为正确的，并且步骤被选择留在该区域内. 在搜索的过程中，区域大小根据模型和实际函数计算的符合程度被修改. 非常典型地，信赖域采取的是一个满足的椭圆. 是一个对角缩放（通常采用近似 Hessian 的对角），而是信赖域半径，它在每个步骤被更新. 当基于二次模型的步骤本身位于信赖域之内的时候，那么就认为函数值在变小，因而采用这一步骤. 因此，正如线搜索方法中一样，步控制不会干涉算法在二次模型表现良好的极小值附近的收敛效果. 当基于二次模型的步骤位于信赖域之外时，则采用一个只到边界位置的步骤，以使得该步骤成为二次模型在信赖域边界处的近似极小化步骤. 一旦一个步骤被选择，该函数就在新的点被计算，而实际函数值与通过二次模型预测所得到的值互相对照. 真正计算的是实际与预测减少量的比率. 如果接近1，那么该二次模型是一个相当不错的预测器，该区域的大小可以扩大. 另一方面，如果太小，则该区域的大小就要被降低. 当低于某一阈值时，该步骤被拒绝并重新计算. 您可以使用方法选项"AcceptableStepRatio"->控制这一阈值. 通常情况下，是相当小的，以避免走向极小值的步骤也被拒绝. 然而，如果在一个点获取二次模型相当昂贵（例如，计算Hessian 需要花费相对较长的时间），一个较大值的将降低Hessian 计算的次数，但是它可能增加函数计算的次数. 要开始信赖域算法，需要确定一个初始半径. 默认情况下，Mathematica使用基于受比较宽松的相对步长限制的模型(1) 的步骤的大小. 然而，在某些情况下，这可能使您离开您原来感兴趣的区域，所以您可以使用选项指定一个初始半径 . 该选项在它的名字中包含Scaled，因为信赖域半径使用了对角缩放，所以这不是一个绝对的步长. 这里加载一个包含一些功用函数的程序包. In[1]:= 这里显示在搜索一个与Rosenbrock函数类似的函数的局部极小值的过程中，所采用的步骤和计算，用的是了利用信赖域步控制的牛顿法.

关于无约束最优化问题的信赖域解法

关于无约束最优化问题的信赖域解法 一、引言 无约束优化问题是实际工程中最常见的问题之一。这类问题虽然形式比较简单，但是对于某些大规模的或者非线性很强的问题，求解它们仍然是有相当难度的。 无约束问题的算法大致分成两类：一类在计算过程中要用到目标函数的导数，另一类则只要求目标函数值。本文中所讲述的信赖域法，与牛顿法、最速下降法、共轭梯度法一样，同属于第一类方法。 二、信赖域法的主要内容 2.1 信赖域法的基本思想 虽然信赖域法与最速下降法等同属于一大类，但是在基本思想上还是有所不同。其他几种方法的基本策略是：给定点x(k)后，定义搜索方向d(k),再从x(k)出发沿d(k)作一维搜索，信赖域法则不然，下面重点阐述一下其基本思想：首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭代。否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。 2.2 信赖域法的数学分析

三、 运用信赖域法求解具体问题 考虑无约束问题 432 1122min () 45f x x x x x =++-+ 取初点(1)00x ?? =????，信赖域半径r 1=1，取μ=0.25，η=0.75.用信赖域法求解过 程： 1) 将初值代入目标函数求得函数值f(x (1))=5，目标函数的梯度

最优化方法——信赖域法

2012-2013（1）专业课程实践论文 信赖域法 董文峰，03，R数学08-1班 伊广旭，03，R数学08-1班 李超，04，R数学08-1班

一、算法理论 信赖域方法与线搜索技术一样, 也是优化算法中的一种保证全局收敛的重要技术. 它们的功能都是在优化算法中求出每次迭代的位移, 从而确定新的迭代点.所不同的是: 线搜索技术是先产生位移方向(亦称为搜索方向), 然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移, 产生新的迭代点。 信赖域方法的基本思想是:首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭代。否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。 信赖域方法解决无约束线性规划

f(x)R x ∈min 的基本算法结构。设k x 是第k 次迭代点，记)f(x f k k =，)f(x g k k ?=，k B 是Hesse 阵)f(x k 2?的第k 次近似，则第k 次迭代步的信赖域子问题具有如下形式： ,2 1g (d)min T k d B d d q k T k += k d t s ?≤. . 其中k ?是信赖域半径，?是任一种向量范数，通常取2-范数或∞-范数。 定义k f ?为f 在第k 步的实际下降量： ),d f(x f Δf k k k k +=- 定义k q ?对应的预测下降量： ()().-0k k k k d q q q =? 定义他们的比值为： k k k q f r ??= 一般的，我们有0>?k q 。因此，若0