数学建模-优化问题..ppt

般优化问题概述约束优化constrainedoptimization的简单分类数学规划mathematicalprogramming或连续优化continuousoptmization线性规划LP)目标和约束均为线性函数Linearprogramming非线性规划(NLP)目标或约束中存在非线性函数NonlinearprogrammingD次规划(QP目标为二次函数、binatorialoptimization整数规划(P)决策变量(全部或部分)为整数Integerprogramming整数线性规划(LP),整数非线性规划(INLP)纯整数规划(PIP,混合整数规划MIPPure(mixed)Integerprogramming般整数规划,0-1(整数)规划O-Oneprogramming无约束最优化问题求解无约束最优化问题的的基本思想无约束最优化问题的基本算法返求解无约束最优化问题的基本思想标准形式:minf(X)其中fE"→Emaxf()=min[-f(X)X∈E求解的基本思想(以二元函数为例)∫(x1x2)x2f(X0)>f(X1)>f(X2)可xf(x1x)=x2+(共轭梯度法)算法步骤:(1)给定初始点X∈E",允许误差>0,令k=0(2)计算V(x4)(3)检验是否满足收敛性的判别准则:X≤E,若满足,则停止迭代,得点X≈X,否则进行(4()令S4=-V(x),从出发,沿←进行一维搜索,即求气使得:mn(x+1)=八(x4+1s)(5)令k=k+1返回(2)最速下降法是一种最基本的算法,,存储变量较少,初始点要求不高;缺点是收敛慢修法适用于寻优过程的前期达代或作为间插步骤,(1)选定初始点X∈E,给定允许误差>0,令k=0;)求v(x),((x+),检验:若y(x)。,则停止迭代,,,转向(3)(3)令S*=-V2/(x)v(x3)(牛顿方向)(4)xk4=xk+S6,=k+1,转回(2)如果f是对称正定矩阵A的二次函数,则用牛顿法经过一次迭代就可达到最优点,如不是二次函数,则牛顿法不能一步达到极值点但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的牛顿法的收敛速度虽然较快,但要求Hessian矩阵要可逆,要计导数和逆矩阵,就加大了计算机计算量和存储量Mat](=fminbnd('F,x,x,)无约束极小MinF(X)X=fminunc('F,Xo)X=fminsearch(F,,X线性规划X=linprog(c,a,b)=bnxTHx+cx次规划Ⅹ=quadprog(H,c,A,b)约束极小MinF(X)(非线性规划)(X)<=0X=fmincon(‘FG,X)(x)-wr<-goalX=fgoalattain(F,x,goal,w)MinmaxF:(x)问题[Fi(x)JX=fminimax(FG’,x0)(x)<=0