第5讲约束优化分解.ppt

* * 第6章 约束优化 约束优化的实例 约束非线性规划的基本原理和解法 MATLAB求解约束非线性规划 优化问题的数学模型 无约束优化（只有(1)）与 约束优化（(1),(2)） 实例：供应与选址 某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨） 假设：料场和工地之间有直线道路 caseplot.m 线性规划模型 决策变量： ci j ~12维 (料场j到 工地i运量） 2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。 决策变量： ci j，(xj,yj)~16维 非线性规划模型 6.1 约束非线性规划的基本原理与解法 f, hi, gj有非线性函数 带约束的非线性规划（Nonlinear Programming） 只有等式约束 拉格朗日乘子法，构造拉格朗日函数 转化为无约束优化问题 利用无约束优化最优解的必要条件求解 不等式约束 6.1.1 可行方向与下降方向 一、起作用约束与不起作用约束 设x*为可行解，使 gj(x*)=0, j∈J1； gj(x*)0, j∈J2 J1∩J2 为空集且J1∪J2 = {1,2,…,l} gj≤0 (j∈J1) ~ x*的起作用约束（积极约束、有效约束） gj≤0 (j∈J2) ~ x*的不起作用约束 x*的起作用约束 在x*处的微小变动都可能导致约束条件被破坏 x*的不起作用约束 在x*处的微小变动不会破坏约束条件 g2=0 g1=0 g3=0 gj0 可行域 Ω： gj(x)≤0（j=1,2,3） 设x*为可行解，位于约束边界 x* g1(x) ≤0 x*的起作用约束 g2(x) ≤0 x*的不起作用约束 g3(x) ≤0 x*的不起作用约束 二、x 处的可行方向 d x 在 d 的方向移动后，仍为可行解 g2=0 g1=0 g3=0 gj0 x 不起作用约束 当λ足够小，可保证约束条件满足 起作用约束 当λ足够小，可保证约束条件满足 任意方向d都是可行方向 ≤0 三、x 处的下降方向 d d为x处的下降方向 若x∈Ω，d既是可行方向又是下降方向，则x继续沿方向d移动时，目标函数f将减少，则x不是最优解 若x为最优解，则一定不存在可行且下降方向 6.1.2 最优解的必要条件 x为最优解 不存在同时满足(1),(2)的d 库恩-塔克(Kuhn-Tucker)条件 ~ K-T条件 且 线性无关，则存在 若x为最优解， 最优解一定是K-T点 互补性条件 Q P x2 x1 0 最优解在P(3,1)取得 ? (7,3) 验证P是K-T点，而Q不是 在P、Q，g1、g2是起作用约束，g3是不起作用约束， g3(x)≠0 λ3 = 0 g1 g2 g3 x2 x1 0 Q P 在P、Q，g1、g2是起作用约束，g3是不起作用约束， g1 g2 g3 g3(x)≠0 λ3 = 0 代入式子 解得： P点是K-T点 同样可以得到不存在λ1,λ2≥0 满足式子： Q点不是K-T点 一般形式的K-T条件 6.1.3 二次规划(QP)及其解法 当H为对称阵，称二次规划（Quadratic Programming） 当H正定时，称凸二次规划 凸二次规划性质： 最优解 ? K-T点； 局部最优解?全局最优解； 等式约束 下 的Lagrange乘子法 最优解方程 L函数 解二次规划的有效集方法 基本思想：对于不等式约束的二次规划，在某可行点 处将不起作用约束去掉，起作用约束视为等式约束， 通过求解等式约束的二次规划来改进可行点。 6.1.4 非线性规划(NLP)的解法 线性逼近法、可行方向法、罚函数法、梯度投影法...　 逐步二次规划法(Sequential Quadratic Programming) SQP的基本原理 构造NLP的拉格朗日函数 用二次函数近似 L(x,?,?), NLP化为QP, 再解一系列QP子问题。 6.2 用MATLAB优化工具箱求解非线性规划 6.2.1 二次规划的解法 输入项 x=quadprog(H,c,A1,b1); x=quadprog(H,c,A1,b1,A2,b2); x=quadprog(H,c,A1,b1,A2,b2,v1,v2); x=quadprog(H,c,A1,b1,A2,b2,v1,v2,x0); x=quadprog(H,c,A1,b1,A2, b2,v1,v2,x0,options) 省缺项用[ ]占位 标准形式 quadprog 输出项 [x,fval]=quadprog(...) [x,fval,exitflag]=quadprog(...) [x,fval,exitflag,ou