约束最优化理论与方法.pptx

《约束最优化理论与方法.pptx》由会员分享，可在线阅读，更多相关《约束最优化理论与方法.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、度 之间的关系.下降方向集第10页/共34页序列可行方向可行方向第11页/共34页线性化可行方向第12页/共34页如果所有的约束函数都在处可微，则有序列可行方向可行方向线性化可行方向第13页/共34页序列可行方向线性化可行方向第14页/共34页引理在局部极小点处没有可行下降方向第15页/共34页证明:反证法.假设存在可行序列的序列可行方向d并且序列矛盾第16页/共34页引理在局部极小点处没有可行下降方向第17页/共34页Farkas引理设为矩阵，则下述两组方程中有且仅有一组有解：其中Farkas引理在最优化理论研究中起重要作用第18页/共34页Farkas引理的另一种形式设l.l是两个非负整数

4、，a0,ai(i=1,l)和bi(i=1,l)是Rn中的向量，则线性方程组和不等式组无解当且仅当存在实数使得第19页/共34页KKT定理驻点条件可行性条件乘子非负条件互补松弛条件KKT条件第20页/共34页最优点不一定是KKT点第21页/共34页第22页/共34页证明方程组无解第23页/共34页第24页/共34页线性函数约束规范条件(LFCQ):线性无关约束规范条件(LICQ):可以证明(1)如果LFCQ成立，则CQ成立(2)如果LICQ成立，则CQ成立定理:第25页/共34页一阶最优性充分条件定理证明:不失一般性，我们可假定矛盾第26页/共34页线性化零约束方向集定理(二阶必要性条件)定理(二阶充分性条件)第27页/共34页 7.2 二次罚函数方法设法将约束问题求解转化为无约束问题求解具体说：根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解第28页/共34页二次罚函数法引例：求解等式约束问题:解:图解法求出最优解构造：但是性态极坏，无法用有效的无约束优化算法求解第29页/共34页设想构造：其中求解此无约束问题得：当时，有：是一个非常大的正数第30页/共34页等式约束问题二次罚函数的极小点就是原问题的极小点第31页/共34页极小点为极小点非常接近第32页/共34页第33页/共34页感谢您的观看！第34页/共34页