《非线性规划2011》由会员分享，可在线阅读，更多相关《非线性规划2011（21页珍藏版）》请在金锄头文库上搜索。
1、非线性规划,沈阳工业大学 理学院 陈岩,非线性规划,优化问题三要素：决策变量decision variable；目标函数objective function；约束条件constraints,等约束equality constraint,不等约束inequality constraint,非线性规划问题的一般形式,非线性规划,可行解feasible solution（满足约束）与可行域feasible region（可行解的集合）最优解optimal solution（取到最小minimum大值maximum的可行解,对应最优值optimal value）,局部最优解或相对最优解local/re
2、lative optimizer,全局或整体最优解global optimizaer,优化模型的基本类型,无约束优化 unconstrained optimization,约束优化 constrained optimization,特殊：等式（不等式）方程组 system of equations(inequations),非线性规划,数学规划mathematical programming 或连续优化continuous optmization,线性规划(LP) 目标和约束均为线性函数Linear programming 非线性规划(NLP) 目标或约束中存在非线性函数Nonlinear p
3、rogramming二次规划(QP) 目标为二次函数、约束为线性Quadratic programming,约束优化constrained optimization的简单分类,非线性规划,整数规划(IP) 决策变量(全部或部分)为整数 Integer programming整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP), 混合整数规划(MIP) Pure (mixed) Integer programming 一般整数规划，0-1（整数）规划 Zero-one programming,离散优化discrete optimization 或组合优化combinatoria
4、l optimization,非线性规划,无约束问题一维搜索,求解 y = f (x)极小值的数值迭代算法：一维搜索算法中的黄金分割法(0.618法).,分割法原理：设函数 f (x) 在闭区间 a, b 上是下单峰函数, 即在 (a, b) 内 f (x) 由唯一的极小点x*, 在x* 的左边 f (x) 严格单调下降, 在x* 的右边f (x)严格单调上升. 那么对于(a, b)内任意两点x1x2, 如果 f (x1) f (x2 ), 则x*a, x2；否则x*x1, b. 如右图,非线性规划,给定下单峰区间 a, b 及控制误 差0, 黄金分割法(0.618法)的 迭代步骤：,取 x2
5、 = a + 0.618 (b - a), f2 = f (x2), 转向.取 x1 = a + 0.382 (b - a), f1 = f (x1), 转向.若 | b - a | , 则取x* = (a + b )/2, 停. 否则转向. 若f1 f2 , 则取b = x2 , x2 = x1, f2 = f1 , 转向;若f1 f2 , 则取a = x1, b = x2, 转向;若f1 f2 , 则取a = x1, x1= x2, f1 = f2 , 转向. 取 x2 = a + 0.618 (b - a), f2= f (x2), 转向.,非线性规划,下面我们再给出一个求初始区间的进退
6、算法, 在所求出的区间上 f (x) 是下单峰函数. 给定初始点x0和初始步长0, 进退算法的迭代步骤：,取 x1 = x0 + , 计算 f (x0 ), f (x1). 若f (x0) f (x1), 则转向；否则转向. 取 = 2 , x2 = x1 + , 计算 f (x2 ). 若f (x2) f (x1), 则得到区间 x0 , x2 为初始区间, 停；否则转向. 取 x0 = x1 , x1 = x2 , f (x0 ) = f (x1 ), f (x1) = f (x2 ), 转向. 取 =2 , x2 = x0 - , 计算 f (x2 ). 若f (x2 ) f (x0 )
7、, 则得到区间 x2 , x1 为初始区间, 停；否则转向. 取 x1 = x0 , x0 = x2, f (x1 ) = f (x0 ), f (x0 ) = f (x2 ), 转向.,非线性规划,无约束问题min f (x) x R,下面给出一个基于最速下降方向的算法, 它是由Cauchy(1847)提出的, 是求无约束极值的最早的数值算法. 给定控制误差 0和初始点xk (k = 0), 最速下降法的迭代步骤：, 计算g(xk ).,梯度, 若| g (xk )| , 则取x*= xk , 停；否则, 令pk = - g (xk ), 由一维搜索求步长k , 使得,f (xk + k p
8、k ) = min f (xk+pk) | 0., 令xk+1 = xk+k pk , k = k + 1, 转向.,非线性规划,最速下降法的优点是具有整体收敛性, 计算量小, 初始点要求不高；缺点是整体收敛速度慢(所谓最速下降方向仅反映f (x )在xk 的局部性质).,最速下降法适用于寻优过程的前期迭代,当接近极值点时,宜选用其它收敛快的算法如牛顿法、阻尼牛顿法、拟牛顿法.,非线性规划,有约束问题,非线性规划,罚函数法,转化为无约束最优化问题：,算法分析：,设可行域为S，构造函数：,M为足够大的正数,罚因子,非线性规划,罚函数法,求无约束问题得最优解为X(M),直观看出， 只有当X(M)
9、S才可能真正取得极小值，若,就加大罚因子M，使X(M) 向S逼近，,当M时，点列,非线性规划,计算步骤：（第k次迭代）,非线性规划,Matlab中的有约束问题,其中f (x )是标量函数；A, B, Aeq, Beq是相应维数的矩阵和向量；C(x),Ceq(x)是非线性向量函数。,非线性规划,Matlab中的命令是,X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTION),如果没有线性约束，则A=,B=,Aeq=,Beq=;没有上下界，则LB=,UB=,;如果无下界LB=inf, 如果无上界UB=inf; NONLCON是用M文件定义的非线性向量函数
10、C(x),Ceq(x),OPTION定义了优化参数。,非线性规划,算例,编写M文件fun1.m和M文件fun2.m,funtion f=fun1(x); f=x(1)2+x(2)2+8;,funtion f=fun2(x); g=-x(1)2+x(2); h=-x(1)-x(2)2+2;%等式约束,options=optimset; x,y=fmincon(fun1,rand(2,1),zeros(2,1),fun2,options);,非线性规划,算例,编写M文件，定义目标函数：,function f =fun44(x) f=-(sqrt(x(1)+sqrt(x(2)+sqrt(x(3)+s
11、qrt(x(4);,编写M文件，定义约束条件：,function g,ceq =mycon1(x) g(1)=x(1)-400; g(2)=1.1* x(1)+ x(2)-440; g(3)=1.21*x(1)+1.1x(2)+x(3)-484; g(4)=1.331*x(1)+1.21*x(2)+1.1*x(3)+x(4)-532.4; Ceq=0;,非线性规划,算例,x0=1;1;1;1;lb=0;0;0;0;ub=;A=;b=;Aeq=;beq=; x,fval=fmincon(fun44,x0,A,b,Aeq,beq,lb,ub,mycon1 ),非线性规划,竞赛试题,非线性规划,美国数学建模的准备,
