最优化模型与算法

《最优化模型与算法》由会员分享，可在线阅读，更多相关《最优化模型与算法（34页珍藏版）》请在金锄头文库上搜索。

1、最优化模型与算法2内容概要n优化模型简介n优化模型分类n优化算法及其分类 nMatlab优化工具箱n现代智能优化算法3优化模型简介概念、基本形式n什么是优化？就是从各种方案中选取一个最好的。从数学角度看，优化 理论就是研究如何在状态空间中寻找到全局最优点。n一般的优化具有下面形式： min f (x1, x2, , xn) s.t. g(x) 0，xD 其中x1, x2, , xn（即问题的可行域，代表问题参数的选择范围 ），即minf (X)，其中X（矢量形式）。f(x)是决策问题的数学模型， 也是决策问题的目标函数，g(x) 0是决策问题的约束条件， X是决策问 题的决策变量，D是决策问题

2、的定义域（可行域）。问题归结为求极值 。极值点非常多，需要找到全局最小点。 注：求问题的最大和最小是同一个问题，算法完全一样。n分布模型的参数估计问题是典型的优化问题，最大似然估计模型是典型 的优化模型。4优化模型分类n1.根据是否存在约束条件有约束模型，无约束模型注：有约束问题通常采用转换方法将有约束模型转换为无约束模型再 求解。n2.根据目标函数和约束条件表达式的性质线性规划，非线性规划，二次规划，多目标规划等注：最常见的优化模型为非线性规划模型。n3.根据决策变量的连续性连续性优化模型，离散性优化模型（典型的组合优化问题，最短路）注：两类模型在求解方法上有较大不同，本次讲解针对前一种。5

3、优化算法及其分类n什么是优化算法？专门用于求解优化模型的方法叫做优化算法，优化算法与优化模型有本 质区别。n优化算法可分为两大类1 梯度类算法牛顿法、二分法、共轭梯度法、梯度下降法、单纯形法等，该类算法也 称为局部优化算法，明显缺陷是局部优化。Matlab优化工具箱多用该类算法 。2 非梯度类算法（1）遍历搜索法，在组合优化中称为穷举法，计算量大，适用于小规模计算 求解。（2）随机搜索法，包括遗传算法、模拟退火算法、群类算法、禁忌搜索法等 ，又称为现代优化算法，是一类全局最优算法，求解的准确性与时间长度、 迭代次数直接相关。常用的优化功能函数l求解线性规划问题的主要函数是linprog。l求解

4、二次规划问题的主要函数是quadprog。l求解无约束非线性规划问题的主要函数是fminbnd、fminunc和fminsearch。l求解约束非线性规划问题的函数是 fmincon 。l多目标优化问题的MATLAB函数有fgoalattain和fminimax。MATLAB优化工具箱优化求解一般步骤建立目标函数文件针对具体工程问题建立 优化设计的数学模型不等式约束条件表 示成g(X) 0的形 式建立调用优化工具函数 的M文件或命令文件建立约束函数文件运行优化工具函数的M文 件或命令文件求解min f (x1, x2, , xn) s.t. g(x) 0无约束非线性规划问题的MATLAB函数f

5、minbnd要求目标函数为连续函数只求解单变量问题fminunc可求解单变量和多变量问题适用于简单优化问题可求解复杂优化问题fminsearchxopt,fopt,exitflag=fminsearch(fun,x0,options)无约束多元函数最小值函数fminsearch 调用格式设置优化选项参数初始点目标函数返回最优设计变量返回目标函数值返回算法的终止 指示变量值例 求y=2x13 +4x1x23-10x1x2+x22 的最小值点.解：X=fminsearch(2*x(1)3+4*x(1)*x(2)3- 10*x(1)*x(2)+x(2)2, 0,0) 结果为: X =1.0016 0

6、.8335 或在MATLAB编辑器中建立函数文件. function f=myfun(x) f=2*x(1)3+4*x(1)*x(2)3-10*x(1)*x(2)+x(2)2; 保存为myfun.m，在命令窗口键入 X=fminsearch (myfun, 0,0) 或 X=fminsearch(myfun, 0,0) 结果为： X =1.0016 0.8335有约束的多元函数最小值 数学模型形式：min f （X）s.t. AXb （线性不等式约束）AeqX=beq （线性等式约束）C(X)0 （非线性不等式约束条件）Ceq(X)=0（非线性等式约束）Lb X Ub （边界约束条件） 其中：

7、x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、 Ceq(x)是返回向量的函数，f(x)为目标函数，f(x)、C(x)、 Ceq(x)可以是非线性函数.函数 fmincon 格式 x = fmincon(fun,x0,A,b) x = fmincon(fun,x0,A,b,Aeq,beq) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) x,fval =

8、fmincon() x,fval,exitflag = fmincon() x,fval,exitflag,output = fmincon() x,fval,exitflag,output,lambda = fmincon() x,fval,exitflag,output,lambda,grad = fmincon() x,fval,exitflag,output,lambda,grad,hessian = fmincon()参数说明： fun为目标函数，它可用前面的方法定义； nonlcon的作用是通过接受的向量x来计算非线性不等 约束和非线性等式约束分别在x处的估计C和Ceq，通 过指定

9、函数名或函数名句柄来使用，如： x = fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,mycon) ，先建立非线性约束函数，并保存为mycon.m： function C,Ceq = mycon(x) C = % 计算x处的非线性不等约束的函数值. Ceq = % 计算x处的非线性等式约束的函数值. lambda是Lagrange乘子，它体现哪一个约束有效. output输出优化信息； grad表示目标函数在x处的梯度； hessian表示目标函数在x处的Hessian值.控制参数options序号功能默认值及其含义说明 1输出形式0，无中间结果 输出Options(1

10、)=1,按照表格输出结果 Options(1)=-1,隐藏警告信息 2解x的精度1e-4Options(2)设置x解的终止条件 3函数f的精度1e-4Options(3)设置函数f的终止条件4约束g的精度1e-6Options(4)设置约束g的终止条件 5选择主要算法0Options(5)选择主要优化算法 6搜索方向算法0fmin()函数为无约束优化搜索方向提 供3种算法： Options(6)=0,拟牛顿法BFGS公式 Options(6)=1,拟牛顿法DFP公式 Options(6)=2,梯度法 7步长一维搜索0fmin()函数为无约束优化的步长一维 搜索提供2种算法： Options(7

11、)=0,二次和三次混合插值法 Options(7)=1,三次多项式插值法控制参数options 序号功能默认值及其含义说明 8函数值输出Options(8)输出最终迭代函数值 9梯度检验0，不检验Options(9)比较梯度 10函数计算次数Options(10)输出函数计算次数11梯度计算次数Options(11)输出函数梯度计算次数 12约束计算次数Options(12)输出约束计算次数 13等式约束个数0，等式约束为0 Options(13)输入等式约束个数 14最大迭代次数100n （n为变量维数 ）Options(14)输入最大迭代次数15目标个数0Options(15)输入目标个数

12、 16差分步长 最小值1e-8Options(16) 步长的下限或变量的最小梯度值 17差分步长 最大值0.1Options(17) 步长的上限或变量的最大梯度值 18步长Options(18) 步长参数，第1次迭代时置1【例】求解约束非线性规划： 解:首先建立一个m文件myfun.mfunction y=myfun(x)y=-exp(x(1)*x(2)2*(3-exp(x(1)-x(2)2); 存储为myfun.m首先将问题转化为matlab要求的格式;即求出 fun,A,b,Aeq,Beq,X0,Lb,Ub然后建立一个 m文件 confun.mfunction c,cep=confun(x

13、)c=; % c为非线性不等式cep=exp(x(1)+x(2)2-3; % cep为非线性等式然后存储为confun.m最后在命令窗口中输输入：A=;b=;Aeq=;beq=;Lb=;Ub=;x,f=fmincon(myfun,1;1, confun)题目中有非线性约束条件，所以建立非线性约束m-文件。x = 0.88520.7592 f = 6.2043e-016优化过程演示n为了进一步了解优化模型的求解算法，给 出具体实例的优化过程演示。n例：以共轭梯度优化算法优化某函数进行 演示,并说明计算时间复杂度。18现代优化算法遗传算法模拟退火算法禁忌搜索算法蚁群算法粒子群算法差分进化算法 特点

14、： 基于客观世界中的一些自 然现象； 建立在计算机迭代计算的 基础上； 都属于随机搜索算法，具 有全局优化能力； 具有普适性，可解决实际 应用问题。注：群类算法还有鱼群算法 、蜂群算法、鸟群算法等 。现代优化算法20现代优化算法全局性优化理论的一般性描述n两种搜索方式：单点法和多点法。单点法是一种串行方式，即从一个初始状态（单个个体）出发，按照某种方式转移状态进行全局优化，这种方式通常要消耗较多机时；多点法是一种并行方式，即从可行域的多个初始状态（多个个体）同时进行搜索寻找全局最优解，但是空间开销大。根据各态历经假设，理论上二者可以具有相同的搜索效果。事实上，单CPU情况下的单点法和多点法并没

15、有本质性的区别。模拟退火算法及模型模拟退火算法及模型 算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出 ，1983年Kirkpatrick等将其应用于组合优化。物理退火过程物理退火过程算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排 列状态，然后逐步降温使之冷却，最后分子以低能状 态排列，固体达到某种稳定状态。 物理退火过程物理退火过程模拟退火算法及模型模拟退火算法及模型 Metropolis准则以概率接受新状态物理退火过程物理退火过程固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟，虽然该方 法简单，但必须大量采样才能得到比较精确的结果，计 算量很大。 若在温度T，当前状态i 新状态j 若EjEi，则接受 j 为当前状态； 否则，以概率 p=exp-(Ej-Ei)/kBT 接受j 为当前状态。 即：p大于0,1)区间的随机数，则仍接受状态 j 为当前 状态；否则保留状态 i 为当前状态。模拟退火算法及模型模拟退火算法及模型 Metropolis准则以概率接受新状态p=exp-(Ej-Ei)/kBT 物理退火过程物理退火过程在低温下，只接受与当前状态能