Zoutendijk可行方向法(0002)课件

第九章可行方向法第四部分约束最优化问题的解法第十章罚函数法和广义乘子法可行方向法：在可行域内寻找使目标函数下降的点列.广义乘子法:在罚函数法的基础上，借助Lagrange乘子来构造罚函数.罚函数法:利用原问题的目标函数和约束条件构造新的目标函数--罚函数,把约束最优化问题转化为相应的罚函数的无约束最优化问题来求解.改进第四部分约束最优化问题的解法

第九章可行方向法

(FeasibleDirectionMethods)可行方向法是其中的一类求解(线性)约束最优化问题的方法．此类方法可看做无约束下降算法的自然推广．可行方向法的基本思想是从可行点出发，沿可行下降方向进行搜索，求出使目标函数值下降的新的可行点．算法包括选择搜索方向和确定搜索步长两个主要方面．

搜索方向的选择方式不同就形成不同的可行方向法．

Zoutendijk可行方向法梯度投影法(GradientProjectionMethod)

既约梯度法

(ReducedGradientMethod)Frank-Wolfe方法

第九章可行方向法简介Zoutendijk可行方向法

Zoutendijk可行方向法是Zoutendijk于1960年提出的.

Zoutendijk可行方向法中选择搜索方向包括:

起作用约束构造可行方向和ε起作用约束构造可行方向.

Zoutendijk可行方向法可以求解线性约束优化问题和

非线性约束优化问题.线性约束情形Zoutendijk可行方向法考虑线性约束问题线性约束情形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可行方向法非线性约束情形算法特点

计算实践和理论分析表明，该算法可能失效或出现锯齿现象，使算法收敛很慢甚至不收敛到最优点或K—T点．Zoutendijk法的改进

对于线性和非线性不等式约束问题，前面我们仅使用起作用约束来确定搜索方向．当某迭代点在一个约束的边界上时，如果可行方向取得不恰当，那么沿该方向可能因接近另一个约束边界而只能作一个微小的移动，否则，就会使迭代点跑出边界．为防止这一现象发生，设想在约束条件的边界上设立一道“安全带”，迭代点进入“安全带”时，只允许它往可行域内部移动，而不许向边界靠近．为此引入ε起作用约束的概念，即在构造可行方向时，既把通过当前迭代点的约束边界看作起作用约束，也把充分家近当前这代点的边界约束考虑在内．问题的提出Zoutendijk可行方向法定义Zoutendijk法的改进–ε

起作用约束可行方向法εk

起作用约束指标集.ε起作用约束可行方向算法步骤Zoutendijk法的改进Step1Step2Step3Step4Step6Step5Zoutendijk可行方向法简介Zoutendijk法的改进–Topkis-Veinott可行方向法

为防止锯齿现象，还可考虑起作用约束和不起作用约束在确定搜索方向中都起作用．这种全作用约束方向法是Topkis和Veinott(1967)提出并保证收敛于Fritz-John点．基本原理Zoutendijk可行