约束最优化的理论与方法课件.ppt

《约束最优化的理论与方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章约束最优化的理论与方法一般形式的约束最优化问题可行域一般形式的无约束最优化问题全局极小点设则称x*为问题的全局极小点；如果成立，则称x*为严格全局极小点.进一步，如果成立，(总体极小点)局部极小点：如果对于某一成立，则称x*是问题的局部极小点，其中则称x*为严格局部极小点.进一步，如果成立，全局极小点是局部极小点√有效约束、无效约束与内点、边界点有效(起作用)约束：对于可行点，，如果就称不等式约束在点是有效约束。并称可行点位于约束的边界。无效约束：对于可行点就称不等式约束是无效约束的内点.E:等式约束指标集I:不等

2、式约束指标集x点处的有效约束集(有效集)是在x点处的有效约束是在x点处的非有效约束假设已知有效约束A(x)定理（一阶必要条件）定理（凸最优性定理）定理（二阶必要条件）定理（二阶充分条件）设函数，若，并且半正定，则是的局部最优解。设是的局部最优解，则在处的下降方向一定不是可行方向。×√定义设f(x)为定义在空间上的连续函数，点，若对于方向存在数使成立则称s为f(x)在处的一个下降方向.在点处的所有下降方向的全体记为定理设函数f(x)在点处连续可微，如存在非零向量使成立则s是f(x)在点处的一个下降方向.给出了在f(x)连续

3、可微是下降方向同函数f(x)的梯度之间的关系.下降方向集序列可行方向可行方向线性化可行方向如果所有的约束函数都在处可微，则有序列可行方向可行方向线性化可行方向序列可行方向线性化可行方向√引理在局部极小点处没有可行下降方向证明:反证法.假设存在可行序列的序列可行方向d并且序列矛盾引理在局部极小点处没有可行下降方向Farkas引理设为矩阵，则下述两组方程中有且仅有一组有解：其中Farkas引理在最优化理论研究中起重要作用Farkas引理的另一种形式设l.l’是两个非负整数，a0,ai(i=1,…,l)和bi(i=1,…,l’

4、)是Rn中的向量，则线性方程组和不等式组无解当且仅当存在实数使得KKT定理驻点条件可行性条件乘子非负条件互补松弛条件KKT条件最优点不一定是KKT点证明方程组无解线性函数约束规范条件(LFCQ):线性无关约束规范条件(LICQ):可以证明(1)如果LFCQ成立，则CQ成立(2)如果LICQ成立，则CQ成立定理:一阶最优性充分条件定理证明:不失一般性，我们可假定矛盾线性化零约束方向集定理(二阶必要性条件)定理(二阶充分性条件)§7.2二次罚函数方法设法将约束问题求解转化为无约束问题求解．具体说：根据约束的特点，构造某种惩罚

5、函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解．二次罚函数法引例：求解等式约束问题:解:图解法求出最优解构造：但是性态极坏，无法用有效的无约束优化算法求解．设想构造：其中求解此无约束问题得：当时，有：是一个非常大的正数等式约束问题二次罚函数的极小点就是原问题的极小点极小点为极小点非常接近