当前位置：文档之家 › 等式约束优化的信赖域法

等式约束优化的信赖域法

  • 格式：pdf
  • 大小：190.23 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

MA对偶-信赖域算法在非线性不等式约束优化问题中的应用研究

MA对偶-信赖域算法在非线性不等式约束优化问题中的应用研究

MA对偶-信赖域算法在非线性不等式约束优化问题中的应用
研究
任志明;姜冬菊;李磊;丁侦原
【期刊名称】《应用力学学报》
【年(卷),期】2014(0)5
【摘要】针对含有非线性不等式约束条件的优化问题,提出了MA对偶-信赖域算法。

在每次迭代过程中,基于信赖域方法和问题的逼近属性,构造了原优化问题中目标函数和约束函数的移动渐进线函数,由此建立简单的子优化问题。

运用对偶方法求解子问题得到原优化问题的下降方向,再用线搜索方法取得搜索步长,最后得到下一步的迭代点。

应用数学推理证明了该算法的全局收敛性。

以悬臂梁最小柔度问题为例,应用MA对偶-信赖域算法对优化问题进行了求解,数值算例的结果表明,MA 对偶-信赖域算法在求解非线性约束优化问题时比MMA和GCMMA算法的迭代次数少,收敛速度快。

【总页数】9页(P789-795)
【作者】任志明;姜冬菊;李磊;丁侦原
【作者单位】河海大学力学与材料学院;江苏省交通规划设计院股份有限公司【正文语种】中文
【中图分类】O178
【相关文献】
1.一类线性不等式约束优化问题的信赖域算法
2.线性不等式约束优化问题的仿射内点信赖域子空间算法
3.线性不等式约束优化问题的强信赖域算法
4.非线性不等式约束优化问题的一个修正BFGS信赖域算法
5.带非线性不等式约束优化问题的信赖域算法
因版权原因，仅展示原文概要，查看原文内容请购买。

信赖域算法非线性优化问题课件

信赖域算法非线性优化问题课件

非ห้องสมุดไป่ตู้性优化问题的求解方法
总结词
非线性优化问题的求解方法主要包括梯度法、牛顿法、 拟牛顿法、共轭梯度法等。此外，还有一些启发式算 法如模拟退火、遗传算法等也被广泛应用于求解非线 性优化问题。
详细描述
梯度法是最早用于求解非线性优化问题的方法之一， 其基本思想是沿着目标函数的负梯度方向搜索。牛顿 法基于泰勒级数展开，构造一个二次模型逼近目标函 数，并在此基础上求解极小值。拟牛顿法是牛顿法的 改进，通过构造一个正定的拟牛顿矩阵来逼近海森矩 阵。共轭梯度法结合了梯度法和牛顿法的思想，在每 一步迭代中沿着当前搜索方向的前一方向共轭的方向 进行搜索。
可解释性与透明度
研究如何提高信赖域算法的可解释性和透明度，使其在关键领域（如 医疗、金融等）得到更广泛的应用。
信赖域算法的挑战和机遇
挑战
非线性、非凸、大规模、多模态等复杂优化问题对信赖域算法提出了更高的要求。同时，算法的稳定性和收敛速 度也是需要克服的难题。
机遇
随着计算能力的提升和算法理论的不断发展，信赖域算法有望在更多领域发挥重要作用。例如，在数据科学、机 器学习、人工智能、控制系统等领域，信赖域算法具有广阔的应用前景。同时，与其他先进技术的结合也为信赖 域算法的发展提供了新的机遇。
信赖域算法的未来发展
深度学习与机器学习集成
探索将信赖域算法与深度学习、机器学习等先进技术相结合，以解决 复杂、高维的非线性优化问题。
智能优化
结合人工智能和优化算法，开发能够自适应学习和进化的智能优化系 统。
强化学习与优化算法结合
利用强化学习中的智能体与环境交互学习的特点，与信赖域算法结合， 实现更高效的优化。
• 可以处理约束优化问题。
信赖域算法的优缺点

信赖域方法概论

信赖域方法概论

信赖域方法概论非线性优化中的信赖域方法及其应用摘要信赖域方法是非线性优化的一类重要的数值计算方法它在近二十年来受到了非线性优化研究界非常的重视。

特别是最近几年，一直是非线性优化的研究热点。

目前，信赖域方法已经和传统的线收索方法并列为非线性规划的两类主要数值方法。

关键词：信赖域法非线性优化约束条件引言非线性最优化是20世纪50年代发展起来的，它讨论非线性决策问题的最佳选择之特性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现。

随着电子计算机的发展和应用，非线性最优化理论和方法有了很大发展。

目前，它已成为运筹学的一个重要分支，并且在自然科学，工程技术，经济管理，系统工程，特别是“优化设计”等诸多领域得到广泛的应用，成为一门十分活跃的学科。

非线性优化的传统方法几乎都是线搜索类型的方法，即每次迭代时产生一搜索方向，然后在搜索方向上进行精确的或不精确的一维搜索，以得到下一个迭代点。

信赖域方法是一类很新的方法，它和线搜索法并列为目前求解非线性规划的两类主要的数值方法。

信赖域方法思想新颖，算法可靠，具有很强的收敛性，它不仅能很快地解决良态问题,而且也能有效地求解病态(ill-conditioned)的优化问题。

因而对信赖域方法的研究是近20年来非线性规划领域的一个重要的研究方向，是当今寻求如何构造新的优化计算方法的主要途径。

信赖域方法的研究起源于Powell 1970 年的工作，他提出了一个求解无约束优化问题的算法，该算法在每次迭代时强制性地要求新的迭代点与当前的迭代点之间的距离不超过某一控制量。

引入控制步长是因为传统的线搜索方法常常由于步长过大而导致算法失败，特别是当问题是病态时尤为如此。

控制步长实质上等价于在以当前迭代点为中心的一个邻域内对一个近似于原问题的简单模型求极值。

这种技巧可理解为只在一个邻域内对近似模型信赖，所以此邻域被称为信赖域(trust region)。

利用这一技巧的方法也就被称为信赖域法。

0327 信赖域法

0327 信赖域法

qk f ( x ) q( s )
k k
Step5: 然后,令
k 1
1 f k Page 8 if 0.1 2 k qk f k k if 0.1 0.75 qk f k if 0.75 2 k qk
若记 x
k 1
arg min p( x ), s arg min q( s )
k x x k k s k
则 q( s k ) p( x k 1 )
s k x k 1 x k
关键问题 (1) Bk 怎么构造?
Page 5
有很多选择, 这次只讲按BFGS公式构造的.
的步长,这就是阻尼牛顿法,该方法具有整体收敛性. 这一节, 将介绍另一种新的保证算法整体收敛的 方法 —信赖域法.
Page 2
§ 3.7
信赖域法
牛顿法的另一种改进策略.
一 基本思想
首先用迭代点 x k 处的某二次近似函数 p( x )
Page 3
作为原函数的近似 ,然后给出一个邻域半径 k , 并由此定义 x k 的一个邻域 k x : x x k k ,
qk f ( x k ) q( s k ) f ( x k ) p( x k 1 )
f k rk qk
定义比值:
来衡量函数的近似程度.
rk 越接近1, 表明近似程度越好.
这样的话,下一步应加大信赖域半径.
二. 信赖域算法
Page 7
Step1: 给出 x 0 R n , B0 I , 0 1, k 0 给定邻域半径 0 0.
Page 1
上一节学习了牛顿法,传统的牛顿法属于局部收敛

第8讲信赖域方法

第8讲信赖域方法
ɶ ɶ (3). 对于某个正的常数η , sk 2 ≤ η∆ k .
对于二次模型函数 ，定义其柯西点: 对于二次模型函数(2)，定义其柯西点 二次模型函数
s c = −τ k k ∆k gk , gk
其中, 其中
T 1, if g k Bk g k ≤ 0; gk 3 τk = min ∆ g T B g ,1 , or. k k k k
7
5．信赖域算法 ．信赖域算法 Step1. 给 出 初 始 点 x0 ， 信 赖 域 半 径 的 上 界 ∆ , ∆ 0 ∈ ( 0, ∆ ) , 0 ≤ ε ,
0 < η1 ≤ η 2 < 1, 0 < γ 1 ≤ 1 < γ 2 , k := 0 .
Step2. 如果 g k ≤ ε ,停止 停止. 停止 Step3. (近似 求解子问题 得到 sk . 近似)求解子问题 近似 求解子问题(2),得到 Step4. 计算 f ( xk + sk ) 和 rk .令 令
xk + sk , if rk ≥ η1 . xk +1 = or. xk ,
Step5.校正信赖域半径 令 校正信赖域半径.令 校正信赖域半径
∆ k +1 ∈ ∆ k , min {γ 2 ∆ k , ∆}
∆ k +1 ∈ ( 0, γ 1∆ k ] ∆ k +1 ∈ [γ 1∆ k , ∆ k ]
if rk < η1; if rk ∈ [η1 ,η2 ) ;
if rk ≥ η 2 .
8
5．信赖域算法 ．信赖域算法 Step6. 产生 Bk +1 ，校正 q( k ) ，令 k := k + 1, 转 Step 2. 很成功迭代: 很成功迭代 成功迭代: 成功迭代 不成功迭代: 不成功迭代 算法参数选择建议: 算法参数选择建议

最优化方法信赖域方法

最优化方法信赖域方法

最优化方法信赖域方法Trusted Domain Method of Optimization Methods一、概述信赖域（Trusted Domain）法是一种针对多目标最优化问题的优化方法，属于启发式优化技术，又被称为受信域法（Credible Domain）法或者受信域增强法（Credible Domain Enhancement）。

它由A.K.Chentsov在1980年提出，目前已经在工业优化、控制优化、混合模糊优化等领域有广泛的应用。

信赖域法使多目标最优化问题中的搜索变得更加有效和快捷，可以很好地处理多目标最优化问题中的非凸性和高维问题，使最优解更容易被获取。

二、原理信赖域方法优化的原理是：在解空间中划分子空间，在每个子空间中进行最优优化，同时进行领域大小的优化，以找到最优解。

（1）划分的子空间划分的子空间由一组不可分割的解空间，即称为“信赖域（Trusted Domain）”确定，有一种收敛性的在同一信赖域上的解空间集合，该信赖域中必须包含一个或多个最优解点。

（2）之分的子空间有效性在信赖域中，有一种收敛性的解空间，该解空间必须包含一个或多个最优解点，且此处解的收敛性可以满足要求。

由此可以看出，划分的子空间有效的充分利用解空间，能够使对最优解的搜索效率更高，更快地找到最优解。

（3）领域大小的优化在划分解空间时，信赖域方法重点考虑领域大小的优化，以缩小搜索空间大小，并引导搜索过程朝最优解的方向发展。

三、应用1.工业优化信赖域方法已经在工业优化领域得到应用，使多目标工业优化问题中的搜索更加有效和快捷，可以很好地处理多目标最优化问题中的非凸性和高维问题，使最优解更容易被获取。

2.控制优化由于信赖域方法能够有效地处理多目标非凸性和高维问题，因此已经在控制优化中得到应用，用于设计准确性好的控制系统。

3.混合模糊优化信赖域方法在混合模糊优化领域也有应用，可以用来解决特殊类型的模糊控制优化问题，来有效地提高优化中的效率和准确性。

信赖域方法 程序

信赖域方法程序信赖域方法是一种常用的数值优化方法，在求解优化问题时具有较高的效率和准确性。

其核心思想是通过构建信赖域模型来近似原始问题，并利用信赖域模型的特性进行优化。

首先，我们来介绍信赖域方法的基本原理。

给定一个优化问题，目标是找到使目标函数达到最小值的自变量。

信赖域方法通过不断迭代的方式逼近最优解，主要分为以下几个步骤：1. 构建信赖域模型：将原始问题近似为一个二次函数模型。

这个模型可以通过利用目标函数的一阶和二阶导数信息进行构建。

2. 模型优化：对信赖域模型进行优化，找到使模型最小化的自变量值。

这一步一般可以通过解析求解或数值优化方法来实现。

3. 信赖域半径更新：根据模型和原始问题的目标函数值来更新信赖域半径。

如果模型的优化效果良好，信赖域半径会增大；反之，如果模型的优化效果不好，则会减小。

4. 收敛判断：根据一定的收敛准则来判断迭代过程是否结束。

常见的准则包括梯度的大小、目标函数的下降程度等。

在信赖域方法的迭代过程中，确保信赖域模型在每一步内都能够产生较好的优化效果对于方法的有效性是十分重要的。

因此，信赖域方法的关键在于如何适应性地调整信赖域半径，以使得模型的变化与实际问题的变化保持一致。

信赖域方法的优点在于其相对简单的求解过程和较好的收敛性质。

由于信赖域方法可以通过对模型的二次型特征化来近似原始问题，所以往往能够在有限的迭代步数内达到较高的精度。

同时，信赖域方法在处理非光滑、非凸优化问题时也表现出良好的适应性。

然而，信赖域方法也存在一些限制。

首先，构建信赖域模型需要计算目标函数的一阶和二阶导数信息，而这些信息计算起来往往比较耗时。

其次，信赖域方法对信赖域半径的初始设定比较敏感，如果选择了不合适的初始半径，可能会导致收敛过程过早终止或者迭代步数过多。

总的来说，信赖域方法是一种广泛应用于各个领域的优化方法，其简单有效的优化过程和良好的收敛性质使其成为许多实际问题求解的首选方法之一。

未来，信赖域方法在进一步提高收敛速度和扩展到更复杂的优化问题方面还有很大的发展空间。

解等式约束规划的信赖域SQP滤子方法


严格局 部解 时 ， 全牛 顿步 可能会 使 目标 函数值 和 约束 违 反度 上 升 ， 而不 被 滤子 接 受 ， 是破 坏 了算 法 的 完 从 于
收敛性 ． 文对 文献 ［ ３中的信 赖域 Ｓ 本 ３ ＱＰ滤子 方 法进 行 了修 改 ： 果 完全 步不 被接 受 ， 以通 过 一个 二 阶 校 如 可
能 是 一 个 超 线 性 收敛 步 ， 是 当 迭 代 点 充 分 靠 近 原 问题 的严 格 局 部 解 时 。 全 牛 顿 步可 能会 使 目标 函 数 值 和 约 束 但 完 违 反 度 上升 。 而 不 被 算 法 接 受 ， 是破 坏 了 算法 的 收 敛 性 ． 出 一 种 修 改 后 的 信 赖 域 Ｓ Ｐ滤 子 算 法 ， 完 全 步 从 于 给 Ｑ 当 不 被 接 受 时 ． 算 法 进 行 二 阶校 正 （ＯＣ ， 以 减 小 其 不 可 行 性 ． 改 后 的 算 法 可 以 避 免 Ｍａａｏ 效 应 。 算 法 达 对 Ｓ ）可 修 ｒｔｓ 使
到局部超线 性收敛． ‘
关 键 词 ： ＱＰ方 法 ； 赖 域 ；滤 子 ； 阶 校 正 ；Ｍａａ ｓ 应 ；局 部 收 敛 Ｓ 信 二 ｒｔ 效 ｏ
中 图 分 类 号 ： ） ２ ． （ ２ １２ 文 献标 识 码 ： Ａ 文 章 编 号 ：１ ０ － ７ ５ ２ Ｏ ） １ ｏ Ｏ 一 ５ ０ １ ８ ３ （ｏ ８ Ｏ 一 Ｏ １ Ｏ
基 金 项 目 ：国 家 自然 科 学 基 金 资助 项 目 （０ ７ １ ７ １５１３）
作 者 简介 ：王 华 （９ ９ ） 女 ， 东省 菏 泽 市 人 ， 济 大 学 博 士 研 究 生 ． １７ 一 ， 山 同 主要 从 事 非 线 性 规 划 研 究
维普资讯

解线性约束优化问题的新锥模型信赖域3法


ｓ ｌ ｅ ｔ ｅ ｔ ａ ｓ ｏ ｍ ｅ ｕ ｒ ｂ ｅ ．Ｔｈ ｌ ｂ ｌｃ ｎ ｅ ｇ ｎ ｅ ｏ ｈ ｅ ｈｏ ｎｄ ｒ ｓ ｍ ｅ ｏ ｖ ｈ ｒ ｎ ｆ ｒ ｄ ｓ ｂｐ ｏ ｌ ｍｓ ｅ ｇ ｏ ａ ｏ ｖ ｒ ｅ ｃ ｆ ｔ ｅ ｍ ｔ ｄ ｕ ｅ ｏ ｒ ａ ｏ ａ ｌ ｏ ｄ ｔｏ ｓ ｉ ｓ ａ ｌ ｈ ｄ ａ ｄ ｐ ｏ ｅ ． Ａ ｏ ｐ ｔ ｒ ｐ ｏ ｒ ｍ ｂ ｓ ｄ ｏ ｈｉ ｅ ｓ ｎ ｂ ｅ ｃ ｎ ｉ ｉ ｎ Ｓ ｅ ｔ ｂ ｉ ｅ ｎ ｒ ｖ ｄ ｓ ｃ ｍ ｕ ｅ ｒ ｇ ａ ａｅ ｎ ｔ ｓ ｍ ｅ ｈｏ ｓ ｐ ｒｏ ｍｅ ｏ ｅ ｔ ｐ ｏ ｌ ｍｓ ｔ ｄ ｈａ ｅ ｆ ｒ ｄ ｆ ｒ ｔ ｓ ｒ ｂ ｅ ．Ｔｈ ｈ ｏ ｅ ｉ ａ ｎ ｕ ｅ ｉａ ｅ ｕｌｓｓ ｏ ｔ ｅ ｅ ｔ ｅ ｒ ｔｃ １ａ ｄ ｎ ｍ ｒｃ ｌ ｓ ｔ ｈ ｗ ｈ ｒ ｅ ｃｅ ｙ ｏ ｈ ｒ ｓ ｅ ｉ ｎ ｍ ｅ ｈ ｄ ｗｉｈ ｎ ｗ ｏ ｉ ｄ ｌ ｎｄ ｇ ｖ ｈ ａ ｅ ｏ ｕ ｔ ｅ 伍 ｉｎｃ ｆ ｔ ｅ ｔ ｕ ｔｒ ｇ ｏ ｔ ｏ ｔ ｅ ｃ ｎ ｃ ｍｏ ｅ ，ａ ｉ ｅ ｔ ｅ ｂ ｓ ｆｆ ｒ ｈ ｒ ｒ ｓ ａ ｃ ｎ ｎ ｎ ｉ ａ ｐ ｉ ｉａ ｉ ｎ ｂ ｓｎ ｅ ｃ ｎ ｃ ｍ ｏ ｅ ． ｅｅ ｒｈ ｏ ｏ ｌ ｎｅ ｒ ｏ ｔｍ ｚ ｔｏ ｙ ｕ ｉ ｇ ｎ ｗ ｏ ｉ ｄ１ Ｋｅ ｙｗｏ ｄｓ０ｐｅ ａ ｉ ｎ ｅ ｅ ｒ ｈ ｃ ｎ ｔ ａｎｅ ｐｔｍ ｉａ ｉ ｎ， ｏ ｉ ｄ ｌ ｄ ｇ ｅ ｅ ｈ ｄ ｒ ｒ ｔｏ ｓ ｓ ａ ｃ ， ｏ ｓ ｒ ｉ ｄ ｏ ｉ ｚ ｔ ｏ ｃ ｎ ｃ ｍｏ ｅ ， ｏ ｌｇ ｍ ｔ ｏ ｒ ｑ ａ ｉＮｅ ｏ ｌ ｏ ｉｈ ， ｒ ｓ ｅ ｉ ｎ ｓ ｂ ｒ ｂ ｅ ｕ ｓ— ｗｔ ｎ ａ ｇ ｒ ｔ ｍ ｔ ｕ ｔｒ ｇ ｏ ｕ ｐ ｏ ｌ ｍ

一种基于信赖域约束的优化问题的求解方法

第 ２ 卷 第 ６ ８ 期
２ ０８ 正 ０
高 ａ ｈ ｒ Ｃ ｌ ｇ ｎ ｉｅｓｔ ｏ ｒ ｌ ｆＳ ｉｎ ｅ ｏ ｅ ｃ ｅｓ ｏｌ ｅ ａ ｄ Ｕｎｖ ｒｉ ｎ ｅ ｙ
Ｖｏ． Ｎｏ６ １２８ ． Ｎｏ ｖ． ２ｏ ｏ８
＝，（女 ， 鼋 ） ＋ｇ ＋ ） 令 ＝ Ｇ ，
ｉ ＝ 一 ， 女＝Ｖ （ｔ ， （） 厂 ） Ｇ Ｅｓ Ｉ ｇ ｆ ｘ ） ｇ Ｔ＝ （ ， ＝Ｖ 厂（ ） Ｉ ，
则 ｑ （） ， 在 Ｘ 处 的近 似 ，称 ｇ （） ，（ 在 Ｘ 处 的二 次近似模 型 函数川 是 （） 是 ） ．
关 键词 ：信赖域算 法 ；线性规 划 ；共轭 方向 ；Ｋ— Ｔ点 中图分类 号 ：Ｏ ４ ２１ 文献标识 码 ：Ａ
１ 问题 的描 述
考虑 优化 问题
Ｉ ＥＲ
， （）
Ｓ 口 ＝ｂ，ｉ ． ｔ ∈Ｅ
口 ≥ｂ ， ｉ∈， ｆ
（） １
其中： （） ， 是二次可微的实函数 ； （） Ｖ ， 对称正定 ； Ｅ是等式约束指标集 ； 是不等式约束指标集． （） ， 当， 是一个二次函数时，问题 （ ） １ 就变成 了一个二次规划问题 ， 本文从文献【 中对二次规划问题的求解思路 １ 】 出发 ， 对其进行了一定的改进 ，并参照文献【 中对该问题的相关讨论，构造 出了问题 （ ）的求解算法． ２ ］ １
１ １月
文章 编号 ：１０ — ８ ２ ０ ）０ — ０ ２ ０ ０７ ９３ １（ ０ ８ ６ ０ ３ — ５
一
种基于信赖域 约束 的优化 问题 的求解方法
李学骞 ，邢志栋 ，刘伟
（ 西北 大学 数 学系 ，陕西 西安 ７０２ ） １ １７
摘 要 ：讨论 一类仅含有 线性约束 条件 的优化 问题 ，在 每 次迭代过程 中，用二 次近 似模型近似 目标
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2 T 2
S8: 按( 11) 式计算比值 D k; x k+ 1 = x k + dk xk if D k > 0 其它 ;
k+ 1 = K k + $ k , 其中 $ k 按( 10) 式计算: K K K k, A 2 + d k +2 ] max [ $ k > G 2 D k < G 2 G1 < D k < G 1 D
T
由 ( 2) 式得: B k d k + ck A A k d k + ¨x l ( x k , K k ) + ck A K g k = 0 即有 :
T B k d k + ck A T k A kd k = - ¨ xl( xk, K k ) - ck A K g k
( 3)
1 T -1 假定 B k 是可逆的, ( 3) 式两端分别左乘 k A k B k , 得 c 1 T - 1 T 1 T -1 T - 1 ( + Ak B k A k) Ak d k = A k Bk ¨ xl (xk, K k ) - A k B k A k gk ck ck gk -1 1 + AT -1 k Bk ¨ xl( xk, K k) - ( k B k A k ) gk + = - 1AT ck ck ck = 即有 : 令 则有 :
$ k+ 1 =
k $ k, A 1 + d k +2 ] min[ $
S9: 计算 B k+ 1 , C k+ 1 : = C k , 转 S2.
3
算法的收敛性分析
我们在以下的分析中 , 假设如下的条件成立: 假设 ( 1) { x k } 是一有界序列; ( 2) P x I X = { x g ( x ) = 0 } 有 A ( x ) 列满秩 ; ( 3) Pk, B k 正定且一致有界. 引理 1 = LC , 则一定存在 设 D 是一正定矩阵, L是大于 0 的常数 , 如果( L I + D) C 0 < Q< 1, 使得 + C+2 [ Q+ C +2. 证 因 LX 0, 故有( L I+ D )C = L (I+ D )C = LC L ( 12)
k = ( C k C ck
1 T -1 -1 T -1 xl( xk, K k) + A k B k A k) (g k - Ak B k ¨ ck
( 4)
A k d k = - gk +
信赖域法求解子问题 :
T 1 d T B kd m in ¨ xL (xk, K k , ck ) d + n 2 dI R C k s. t . AT k d + gk = ck +d +2 [ $ k
T m
¨ xl( x, K ) = ¨ f ( x ) + KA ( x )
T
¨ xL (x, K , c) = ¨ xl( x, K ) + cA T ( x ) g( x )
2 2 ¨ x L (x, K , c) = ¨2 xl( x , K ) + c E gi ( x ) ¨ g i ( x ) + cA T ( x ) A ( x ) i= 1
k: = C k + 1 , 转 S4. C
S6: 如果 +g k + 2 + + ¨f k - A T kK k +2 [ E , 则停止计算 ; 否则, 解 ( 5) 、 ( 6) 、 ( 7) 得 d k . 1 2 T 2 S7: 由( 10) 式计算 D k ; 如果 D k \ C k [ + g k +2 - + g k + A k d k +2 ] , 则转 S8; 2 否则 , 令 C k : = 2 Ck , D k : = D k + C k [ +g k +2 - +g k + A k d k +2 ] .
ck 2 [ +g( x k ) +2 2 - +g( x k + d k ) +2 ] ( 9) 2
令
ck T 1 dT T T 2 Dk = - ¨ x l k dk k B k d k - $K k gk + A k dk + [ +g( x k ) +2 2 - +g(x k + d k ) +2 ] ( 10) 2 2 我们把 D k 作为价值函数的预估下降量.
( 8)
我们把 5 k ( x ) 作为价值函数, 故有: 5k ( x k ) - 5k ( x k + dk ) = L( x k , K k , ck ) - L ( x k + d k , K k+ $ K k , ck )
T = l( x k , Kk ) + l( x k + dk , K k) - $ K k g( x k + dk ) +
T - 1 - 1 T - 1 1 k k k k k k x k k k k+ 1 = ( C ck + A B A ) ( g - A B ¨ l ( x , K + C) 故有 : -1 T -1 ( 1 + AT k Bk A k) C k+ 1 = g k - A k B k ¨ xl( xk, K k+ C k) ck -1 T -1 = g k - AT k B k ¨ xl ( x k , K k ) - A k B k A kC k 1 T -1 -1 T -1 C k = ( + A k B k A k ) ( g k - A k B k ¨x l ( x k , K k ) 故有: ck 1 T - 1 T - 1 ( + A kBk A k) C k = gk - A k B k ¨x l ( x k , K k) 即 : ck C k -1 T -1 = gk - A T k Bk ¨ xl( xk, K k) - A kBk A kC k化的信赖域法
531
k 为 5 k ( x ) 的实际下降量与预估下降量的比值, 即 : 令D
5k ( x k ) - 5k ( x k + dk ) D k = Dk
( 11)
2
算法
信赖域算法如下 :
n S1: 给出 x 1 I R n , $ 1 > 0, K 1 I R , c1 > 0, 0< A < 1 , 0< A 1 < 1< A 2 , 0< G 1< G 2 < 1,
令
1 Q = +I + D + 2 , 则 0< Q < 1 L 所以 + C+ 2 [ Q+ C+2 .
引理 2
若 A k 满秩 , B K 正定 , 则 A T k B k A k 正定.
T
证 对 P x X 0, 因 B K 正定 , 则 x B k x > 0 T T T T T 又因 A k 满秩 , 即有 A T k x X 0, 从而( A k x ) B k ( A k x ) > 0, 即 x ( A k B k A k ) x > 0 故 xT ( AT k B kA k ) x > 0 P x X 0 所以 A T k B k A k 正定 . 定理 1 在算法中 , 内循环 S 4 ) ) ) S 5 是有限的 . 证 因
k: = 1, E\0, 计算 B 1 . S2: 如果 g k = 0, 转 S6. S3: 计算 Ck . S4: 如果 A +g k + \
k + +C , 转 S6. ck
1 T - 1 - 1 T - 1 k+ 1 = ( k k k k k k x k k k S5: 计算 C ck + A B A ) ( g - A B ¨ l ( x , K+ C ) 令
( 5) ( 6) ( 7)
其中 , 称 C k 为广义 L agr ange 乘子 为使搜索方向 d k 趋向可行域 , 一方面可使罚因子 c k y ] ; 但另一方面, 如果 C k U 0, 则点 x k + d k 是非常接近可行的 , 而不必罚因子 ck y ] , 故需要选择 ck , 使得 g k A T k d [ 0, 即- g T k g k+ gT kC k +C k + +gk + [ 0 或 +g k + 2 \ , 并且我们进一步把条件加强为: ck ck A+g k + \ +C k + ck 其中 0 < A< 1
T
1 k T -1 1 T - 1 k) ) - ( ( g - A k B k ¨x l ( x k , K + A kBk A k)g k ck ck
1( 1+ AT - 1 - 1 - 1 AT kd k= kBk A k) ( gk - A T k Bk ¨x l ( x k , K k ) ) - gk ck ck
令
B( x , K , c) = ¨ x l( x , K ) + c E gi ( x ) ¨ gi ( x )
2 2 i= 1
m
*
收稿日期 : 2006 - 05 - 09 接收日期 : 2007 - 01 - 25 基金项目 : 国家自然科学基金资助项 目( 70771078, 70471034, A 0324666) 作者简介 : 王芳华 ( 1969 - ) , 男 , 湖南湘潭 , 讲师 , 硕士生 , 研究方向 : 最优化理论与算法 .