约束最优化问题的解法电子教案.ppt

l 第九章 可行方向法第四部分 约束最优化问题的解法l 第十章 罚函数法和广义乘子法l 可行方向法：在可行域内寻找使目标函数下降的 点列.l 广义乘子法: 在罚函数法的基础上，借助Lagrange乘子 来构造罚函数.l 罚函数法: 利用原问题的目标函数和约束条件构造 新的目标函数-罚函数, 把约束最优化问题转化为 相应的罚函数的无约束最优化问题来求解.改进第四部分 约束最优化问题的解法 第九章 可行方向法 (Feasible Direction Methods)l 可行方向法是其中的一类求解(线性)约束最优化问题的方法 此类方法可看做无约束下降算法的自然推广l 可行方向法的基本思想是从可行点出发，沿可行下降方向进 行搜索，求出使目标函数值下降的新的可行点l 算法包括选择搜索方向和确定搜索步长两个主要方面 搜索方向的选择方式不同就形成不同的可行方向法简介Zoutendijk可行方向法l Zoutendijk可行方向法是Zoutendijk于1960年提出的.l Zoutendijk可行方向法中选择搜索方向包括: 起作用约束构造可行方向和起作用约束构造可行方向.l Zoutendijk可行方向法可以求解线性约束优化问题和 非线性约束优化问题.线性约束情形Zoutendijk可行方向法考虑线性约束问题线性约束情形Zoutendijk可行方向法基本原理 (1) 利用起作用约束构造可行下降方向线性约束情形Zoutendijk可行方向法基本原理 (1) 利用起作用约束构造可行下降方向线性规划问题线性约束情形Zoutendijk可行方向法基本原理 (1) 利用起作用约束构造可行下降方向 (2) 确定一维搜索步长线性约束情形Zoutendijk可行方向法基本原理 (2) 确定一维搜索步长 带约束的 一维优化 问题 利用可行方向条件与起作用约束简化(9.1.11)线性约束情形Zoutendijk可行方向法基本原理 (2) 确定一维搜索步长 (a) 简化 (a)(9.1.5)线性约束情形Zoutendijk可行方向法基本原理 (2) 确定一维搜索步长分两种情况讨论(9.1.5) :(9.1.14)的约束条件问题(9.1.11)一维搜索问题线性约束情形算法步骤Step1Step2Step3Step4Step5Zoutendijk可行方向法线性约束情形举例Zoutendijk可行方向法 参见P243 例9.1.1非线性约束情形Zoutendijk可行方向法非线性约束情形基本原理 (1) 利用起作用约束构造可行下降方向定理1.2.3定理3.3.2点 x 处的可行下降方向d 满足：线性规划问题 结论(9.1.22)Zoutendijk可行方向法非线性约束情形基本原理 (1) 利用起作用约束构造可行下降方向 (2) 确定一维搜索步长非线性约束情形算法步骤Step1Step2 束Step3Step4Step5Zoutendijk可行方向法非线性约束情形算法特点 计算实践和理论分析表明，该算法可能失效或出现锯齿现象，使算法收敛很慢甚至不收敛到最优点或KT点Zoutendijk法的改进 对于线性和非线性不等式约束问题，前面我们仅使用起作用约束来确定搜索方向当某迭代点在一个约束的边界上时，如果可行方向取得不恰当，那么沿该方向可能因接近另一个约束边界而只能作一个微小的移动，否则，就会使迭代点跑出边界为防止这一现象发生，设想在约束条件的边界上设立一道“安全带”，迭代点进入“安全带”时，只允许它往可行域内部移动，而不许向边界靠近为此引入 起作用约束的概念，即在构造可行方向时，既把通过当前迭代点的约束边界看作起作用约束，也把充分家近当前这代点的边界约束考虑在内问题的提出Zoutendijk可行方向法定义Zoutendijk法的改进 起作用约束可行方向法k 起作用约束指标集.起作用约束可行方向算法步骤Zoutendijk法的改进Step1Step2Step3Step4Step6Step5Zoutendijk可行方向法简介Zoutendijk法的改进 Topkis-Veinott 可行方向法l 为防止锯齿现象，还可考虑起作用约束和不起作用约束在 确定搜索方向中都起作用l 这种全作用约束方向法是Topkis和Veinott (1967)提出并保证 收敛于Fritz-John点基本原理Zoutendijk可行方向法Zoutendijk法的改进 Topkis-Veinott 可行方向法基本原理 结论Topkis-Veinott可行方向算法步骤Zoutendijk法的改进Step1Step2Step3Step4。