数学建模-优化问题.ppt

文档介绍：约束优化constrained optimization的简单分类数学规划mathematical programming或连续优化continuous optmization?线性规划(LP)目标和约束均为线性函数Linear programming?非线性规划(NLP)目标或约束中存在非线性函数Nonlinear programming二次规划(QP)目标为二次函数、约束为线性Quadratic programming一般优化问题概述整数规划(IP)决策变量(全部或部分)为整数Integer programming?整数线性规划(ILP),整数非线性规划(INLP)?纯整数规划(PIP), 混合整数规划(MIP) Pure (mixed) Integer programming一般整数规划,0-1(整数)规划Zero-one programming离散优化discrete binatorial optimization一般优化问题概述无约束最优化问题求解无约束最优化问题的的基本思想*无约束最优化问题的基本算法返回??XfnEX?min其中1:EEfn?标准形式:求解无约束最优化问题的基本思想求解的基本思想( 以二元函数为例)1x2x)(21xxf01x2x05310X1X2X)(0Xf)(1Xf?)(2Xf?连续可微??XfnEX?max =??][minXfnEX???f0??f唯一极小(全局极小)2122212121322)(xxxxxxxxf?????搜索过程21221221)1()(100)(minxxxxxf????最优点(1 1)初始点(-1 1)1x2xf--------8返回⑴给定初始点nEX?0,允许误差0??,令k=0;⑵计算??kXf?;⑶检验是否满足收敛性的判别准则:?????kXf,若满足,则停止迭代,得点kXX?*,否则进行⑷;⑷令??kkXfS???,从kX出发,沿kS进行一维搜索,即求k?使得:????kkkkkSXfSXf???????0min;⑸令kkkkSXX????1,k=k+1返回⑵.无约束优化问题的基本算法最速下降法是一种最基本的算法,,存储变量较少,初始点要求不高;缺点是收敛慢,最速下降法适用于寻优过程的前期迭代或作为间插步骤,当接近极值点时,(共轭梯度法)算法步骤::(1) 选定初始点nEX?0,给定允许误差0??,令k=0;(2)求??kXf?,????12??kXf,检验:若?????kXf,则停止迭代,kXX?*.否则, 转向(3);(3) 令????kkkXfXfS?????12][(牛顿方向);(4)kkkSXX???1,1??kk,转回(2).如果f是对称正定矩阵A的二次函数,则用牛顿法经过一次迭代就可达到最优点,如不是二次函数,则牛顿法不能一步达到极值点,但由于这种函数在极值点附近和二次函数很近似,,但要求Hessian矩阵要可逆,要计算二阶导数和逆矩阵, F(x)<x<x2x=fminbnd(‘F’,x1,x2)无约束极小Min F(X)X=fminunc(‘F’,X0)X=fminsearch(‘F’,X0)线性规划Min <=bX=linprog(c,A,b)二次规划Min 21xTHx+. Ax<=bX=quadprog(H,c,A,b)约束极小(非线性规划)Min F(X). G(X)<=0X=fmincon(‘FG’,X0)达到目标问题Min . F(x)-wr<=goalX=fgoalattain(‘F’,x,goal,w)极小极大问题Min max {Fi(x)}X {Fi(x)}. G(x)<=0X=fminimax(‘FG’,x0)