非线性规划2011

非线性规划沈阳工业大学理学院 陈岩非线性规划优化问题三要素： 决策变量 decision variable； 目标函数 objective function； 约束条件 constraints约束条件决策变量目标函数等约束 equality constraint不等约束 inequality constraint非线性规划问题的一般形式非线性规划 可行解 feasible solution（满足约束）与可行域feasible region（可行解的集合） 最优解 optimal solution（取到最小 minimum大值maximum的可行解 ,对应最优值 optimal value）局部最优解或相对最优解 local/relative optimizer全局或整体最优解 global optimizaer优化模型的基本类型无约束优化 unconstrained optimization约束优化 constrained optimization特殊：等式（不等式）方程组 system of equations(inequations)非线性规划数学规划 mathematical programming或连续优化 continuous optmization 线性规划 (LP) 目标和约束均为线性函数Linear programming 非线性规划 (NLP) 目标或约束中存在非线性函数Nonlinear programming二次规划 (QP) 目标为二次函数、约束为线性Quadratic programming约束优化 constrained optimization的简单分类非线性规划整数规划 (IP) 决策变量 (全部或部分 )为整数Integer programming 整数 线性 规划 (ILP)，整数 非线性 规划 (INLP) 纯整数规划 (PIP), 混合整数规划 (MIP) Pure (mixed) Integer programming 一般整数规划， 0-1（整数）规划Zero-one programming离散优化 discrete optimization或组合优化 combinatorial optimization非线性规划无约束问题 一维搜索求解 y = f (x)极小值的数值迭代算法：一维搜索算法中的 黄金分割法 (0.618法 ). 分割法原理 ：设函数 f (x) 在闭区间 a, b 上是 下单峰函数 , 即在 (a, b) 内 f (x) 由唯一的极小点 x*, 在 x* 的左边 f (x) 严格单调下降 , 在 x* 的右边 f (x)严格单调上升 . 那么对于 (a, b)内任意两点 x1 x2, 如果 f (x1) f (x2 ), 则 x* a, x2； 否则x* x1, b. 如右图 非线性规划给定下单峰区间 a, b 及控制误差 0, 黄金分割法 (0.618法 )的迭代步骤： 取 x2 = 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), 转向 . 非线性规划下面我们再给出一个求初始区间的 进退算法 , 在所求出的区间上 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 ), 则得到区间 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 pk ) = min f (xk+pk) | 0. 令 xk+1 = xk+k pk , k = k + 1, 转向 .非线性规划最速下降法的优点是具有整体收敛性 , 计算量小 , 初始点要求不高；缺点是整体收敛速度慢 (所谓最速下降方向仅反映 f (x )在 xk 的局部性质 ).最速下降法适用于寻优过程的前期迭代 ,当接近极值点时 ,宜选用其它收敛快的算法如牛顿法、阻尼牛顿法、拟牛顿法 .非线性规划有约束问题非线性规划罚函数法转化为无约束最优化问题：算法分析：设可行域为 S，构造函数：M为足够大的正数 ,罚因子非线性规划罚函数法求无约束问题得最优解为 X(M),直观看出，只有当 X(M) 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文件定义的非线性向量函数C(x),Ceq(x),OPTION定义了优化参数。非线性规划算例编写 M文件 fun1.m和 M文件 fun2.mfuntion 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)+sqrt(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=;