非线性规划理论与算法.pptVIP

*最大最小对偶举例——博弈第30页，共81页，星期日，2025年，2月5日*最大最小对偶鞍点条件:对相关结论：——弱对偶定理——对偶间隙若有点则称(x*,y*)满足鞍点条件。——强对偶定理满足鞍点条件。第31页，共81页，星期日，2025年，2月5日*原规划:Lagrange对偶Lagrange函数Lagrange对偶弱对偶性:——弱对偶定理——对偶间隙原规划凹函数第32页，共81页，星期日，2025年，2月5日*Lagrange对偶举例第33页，共81页，星期日，2025年，2月5日*像集第34页，共81页，星期日，2025年，2月5日*第35页，共81页，星期日，2025年，2月5日*第36页，共81页，星期日，2025年，2月5日*连续可微凸规划:强对偶定理：连续可微凸规划，满足一约束规格，则Lagrange对偶的强对偶定理f、g可微凸，h线性1)：若原问题有解，则对偶问题也有解；2)：若原问题与对偶问题分别有可行解，则他们是最优解的充分必要条件是他们对应相同的目标值(对偶间隙为0).证1)：即证可微凸规划的最优解与其KKT条件的乘子满足鞍点条件！证2)：利用鞍点条件可得。3)：对偶问题无上界，则原问题不可行；原问题无下界，则对偶问题不可行。第37页，共81页，星期日，2025年，2月5日*连续可微凸规划:Wolfe对偶：Wolfe对偶f、g可微凸，h线性1)：若原问题有解，则对偶问题也有解；2)：若原问题与对偶问题分别有可行解，则他们是最优解得充分必要条件是他们对应相同的目标值(对偶间隙为0).Lagrange函数Wolfe对偶定理：连续可微凸规划，满足一约束规格，则第38页，共81页，星期日，2025年，2月5日*凸规划对偶举例(Q正定)二次规划(Q正定)推广一：推广二：Lagrange对偶共轭对偶、广义Lagrange对偶——参阅《非线性规划及其理论》(应玖茜、魏权龄)第6章第39页，共81页，星期日，2025年，2月5日罚函数法第40页，共81页，星期日，2025年，2月5日*惩罚函数法将有约束优化问题转化为一系列无约束优化问题进行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法类型：外点法（外惩法）内点法（内惩法）3、问题：第41页，共81页，星期日，2025年，2月5日*4、外点法（外部惩罚函数法）第42页，共81页，星期日，2025年，2月5日*第43页，共81页，星期日，2025年，2月5日*第44页，共81页，星期日，2025年，2月5日*（1）几何解释第45页，共81页，星期日，2025年，2月5日*（2）算法步骤（外点法）：第46页，共81页，星期日，2025年，2月5日*yesNo（3）外点法框图第47页，共81页，星期日，2025年，2月5日*（4）应注意的问题第48页，共81页，星期日，2025年，2月5日*例:第49页，共81页，星期日，2025年，2月5日*参阅P207——例2关于2个约束的例子!第50页，共81页，星期日，2025年，2月5日*（5）一般模型的外点法算法步骤相同第51页，共81页，星期日，2025年，2月5日*(6)算法收敛性详见P202，引理8.1，定理8.2.详见P203，定理8.4.第52页，共81页，星期日，2025年，2月5日*5、内点法（障碍函数法）（1）集合结构第53页，共81页，星期日，2025年，2月5日*（2）算法思想内点法（障碍函数法）的迭代点是在可行域点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。第54页，共81页，星期日，2025年，2月5日*（3）算法分析第55页，共81页，星期日，2025年，2月5日*第56页，共81页，星期日，2025年，2月5日*（4）算法步骤（内点法）：第57页，共81页，星期日，2025年，2月5日关于非线性规划理论与算法第1页，共81页，星期日，2025年，2月5日非线性规划及其最优性条件第2页，共81页，星期日，2025年，2月5日*约束集或可行域:非线性规划x*是整体(全局)极小点x*是严格整体(全局)极小点x