下载文档原格式
2012-2013（1）专业课程实践论文信赖域法董文峰，0818180123，R数学08-1班伊广旭，0818180113，R数学08-1班李超，0818180114，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 次迭代步的信赖域子问题具有如下形式：,21g (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 =∆定义他们的比值为：kk k q f r ∆∆= 一般的，我们有0>∆k q 。
最优化方法信赖域方法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.混合模糊优化信赖域方法在混合模糊优化领域也有应用，可以用来解决特殊类型的模糊控制优化问题，来有效地提高优化中的效率和准确性。
最优化方法信赖域方法例题信赖域方法是求解无约束优化问题的一种常用方法，其基本思想是在当前点附近构造一个局部模型，并利用这个模型来引导下一步搜索方向，以期望加速收敛。
以下是一个信赖域方法的例题：假设要求解如下无约束优化问题：minimize f(x) = 2x1^2 + x2^2 - 2x1x2 - 4x1其中x = (x1, x2)T为变量向量。
根据信赖域方法的思路，首先需要在当前点xk处构造一个局部二次模型来近似目标函数f(x)，即：m(k)(p)=f(xk)+g(k)Tp+0.5TpTB(k)T p其中p表示搜索方向，g(k)和B(k)分别表示目标函数在xk处的梯度和Hessian矩阵。
然后，需要找到信赖域半径δk，使得在搜索方向p的范数不超过δk的条件下，局部模型能够较好地近似目标函数。
具体来说，需要最小化如下子问题：minimize m(k)(p)subject to ||p||<=δk对于上述例题，可以通过以下步骤来求解：1. 初始点为x0 = (0, 0)T，初始信赖域半径为δ0 = 1。
2. 计算目标函数在x0处的梯度和Hessian矩阵：g(0) = (-4, 0)TB(0) = [[4, -2], [-2, 2]]3. 解信赖域子问题，得到搜索方向pk和对应的模型改进量mk： pk = argmin m(k)(p)subject to ||p||<=δkpk = (0.5, -0.5)Tmk = -0.254. 计算实际改进量rk和相应的系数ηk：rk = f(xk) - f(xk+pk)γk = rk/mkif γk < 0.25:δk+1 = 0.5δkelse if γk > 0.75:δk+1 = 2δkelse:δk+1 = δk5. 根据信赖域半径更新规则，计算下一次迭代的点xk+1和信赖域半径δk+1：if γk > 0:xk+1 = xk + pkelse:xk+1 = xkδk+1 = δk6. 重复步骤2-5，直到收敛。
无约束最优化问题的信赖域解法关于无约束最优化问题的信赖域解法一、引言无约朿优化问题是实际工程中最常见的问题之一。
这类问题虽然形式比较简单，但是对于某些大规模的或者非线性很强的问题，求解它们仍然是有相当难度的。
无约束问题的算法大致分成两类：一类在计算过程中要用到LI标函数的导数，另一类则只要求LI标函数值。
本文中所讲述的信赖域法，与牛顿法、最速下降法、共辘梯度法一样，同属于第一类方法。
二、信赖域法的主要内容2.1信赖域法的基本思想虽然信赖域法与最速下降法等同属于一大类，但是在基本思想上还是有所不同。
其他儿种方法的基本策略是：给定点宀后，定义搜索方向少,再从x的出发沿d （k）作一维搜索，信赖域法则不然，下面重点阐述一下其基本思想：首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。
然后，通过求解这个区域内的“信赖域子问题”（1」标函数的二次近似模型）的最优点来确定“候选位移”。
若候选位移能使U标函数值有充分的下降量，则接受该候选位移作为新的位移，并保持或扩大信赖域半径，继续新的迭代。
否则，说明二次模型与H标函数的近似度不够理想，需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。
如此重复下去，直到满足迭代终止条件。
2.2信赖域法的数学分析考虑无约束问题：min /（x）, xeR"（2-1）将f（x）在给定点x（k）展开，取二次近似可得：/37（严）+巧（严）匕-严）+斗匕-严）9予（占）匕-严）（2-2）记d=x- x （k ）,得到二次模型血）=/（严）+巧（■严）7 〃 +扣9丁（严）〃 乙 为了在x ⑹附近用輕“）近似f （x （k ）+d ）,限定d 的取值，令||d||<r k , rk 是给定的常数，称为信赖域半径，这样求函数f （x ）的极小点归结为解一系列子问题def 1min 探（d ） =+ ⑷『力 + — ”丁可’/匕⑹）〃 2M Mil" 若d （k ）是2-1式的最优解，则存在乘子enO,使得：V 2/(V ))6/,k>+V/(x a )) + ——-一 d ⑷=0(/叭/⑹)亍(2-5)讪严卜4) = 0得到护）为最优解的必要条件Py （严）（严>+血严=_yy （卅））负㈣-几）=0co>0严I"设0丁（严）+创可逆，由式2-7可得,Ill'll = ||（V 2/U （* ‘）+ 创尸巧（卅）||（2-8）由上述条件易知，式2-7的解d （k ）与信赖域半径rk 取值有关，如果Fk 充分大，"的 值有可能很小，从而d ⑹与牛顿法中的牛顿方向接近，即d (k} ^-v 2f (x ik)y l vf (x ik})如果以趋近于0,则可得：df —丄巧（泸）CO 山此可知，当信赖域半径n III 小到大逐渐增大时，d<k ）在最速下降方向与牛顿方 向之间连续变化。
