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

THUTHU DAE ￿1 机械最优化设计课程机械最优化设计作业机械最优化设计作业THUTHU DAE ——信赖域方法THUTHU DAE ￿2 机械最优化设计课程1.信赖域方法的综述信赖域方法的综述 信赖域法和线性搜索方法是求解非线性优化问题的两类主要的数值方法信赖域法也是一种迭代算法，即从给定的初始解出发，通过逐步迭代，不断改进，直到获得满意的近似最优解为止 特点：思想新颖，具有可靠性、有效性和很强的收敛性与线性搜索方法相比，信赖域方法直接通过模型求解得到试探步长，而不是先确定搜索方向，再寻找步长 线搜索方向可以看成是信赖域半径充分大时的信赖域步；而信赖域方法得出的信赖步可看成是将二次逼近模型加上一个惩罚项之后所导致的线搜索方向THUTHU DAE 基本思想基本思想机械最优化设计课程￿3 在每次迭代中给出一个信赖域，这个信赖域一般是当前迭代点 的一个小邻域然后在这个邻域内求解一个子问题，得到试探步长（trial step） ，接着用某一评价函数来决定是否接受该试探步长以及决定下一次迭代的信赖域如果试探步长被接受，则： ，否则， 。

新的信赖域的大小取决于试探步长的好坏，粗略地说，如果试探步长较好，在下一步信赖域扩大或保持不变，否则下一步减小信赖域THUTHU DAE 算法模型算法模型机械最优化设计课程￿4 ￿￿￿￿￿￿￿￿设当前点 的邻域定义为： 其中， 称为信赖域半径 利用二次逼近，构造如下信赖域子问题：其中，THUTHU DAE 算法模型算法模型机械最优化设计课程￿5 设 是信赖域子问题（2）的解，定义目标函数第k步的真实下降量为：称二次模型函数 的下降量为预测下降量： 定义比值： 它衡量了二次模型与目标函数的逼近程度 越接近于1，表明接近程度越好因此用它来确定下次迭代的信赖域半径THUTHU DAE 信赖域半径的选择信赖域半径的选择机械最优化设计课程￿6 （1） 越接近于1，表明接近程度越好，这时可以增大 以扩大信赖域；（2） >0但是不接近于1，保持 不变；（3）如果 接近于0，减小 ，缩小信赖域。

或者其他 的选择方法（后面介绍）THUTHU DAE 信赖域算法信赖域算法机械最优化设计课程￿7 Step1. 给出初始点￿￿￿￿￿，信赖域半径的上界Step2. 计算￿￿￿￿￿，如果￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿，停止；否则，计算￿￿￿￿￿￿￿Step3. （近似）求解子问题（2），得到￿￿￿￿￿Step4. 计算￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿，令Step5. 校正信赖域半径，令THUTHU DAE 信赖域算法信赖域算法机械最优化设计课程￿8 Step6. 令k=k+1,转Step2. 很成功迭代：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿，信赖域扩大； 成功迭代：￿￿￿ 不成功迭代：￿￿￿￿￿￿￿￿￿￿￿，信赖域缩小算法参数选择：THUTHU DAE 解信赖域子问题解信赖域子问题机械最优化设计课程￿9 ￿￿￿￿￿￿￿￿信赖域方法在每步迭代中求解下列形式的子问题：其中， S为待求变量。

当￿￿￿￿￿￿变化时，S的解形成一条空间曲线，称为最优曲线 Powell[1970]给出了求解（2）的单折线法，当￿￿￿￿￿可逆时用连接初始点、￿￿￿￿￿￿￿￿￿￿￿￿的单折线近似最优曲线，在折线上取点￿￿￿￿￿￿使得￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿作为（2）的解￿￿￿￿￿THUTHU DAE 解信赖域子问题解信赖域子问题机械最优化设计课程￿10 THUTHU DAE 解信赖域子问题解信赖域子问题机械最优化设计课程￿11 THUTHU DAE 解信赖域子问题解信赖域子问题机械最优化设计课程￿12 THUTHU DAE 数值实验数值实验机械最优化设计课程￿13 方法迭代次数函数值误差最优点误差信赖域81.2*e^(-13)7.8*e^(-7)共轭方向169.4*e^(-9)1.5*e^(-5)变尺度329.4*e^(-9)1.5*e^(-5)THUTHU DAE 机械最优化设计课程￿14 THUTHU DAE 对步长接收准则的讨论对步长接收准则的讨论机械最优化设计课程￿15 。