Matlab优化算法

主讲人：饶志欢

现代优化算法

什么是优化？就是从各种方案中选取一个最好的。从数学角度看，优化理论就是研究如何在状态空间中寻找到全局最优点。

比如水泥混凝土的性能，涉及到水、沙、石子、水泥和其他掺杂物比例。学校课程表排课问题、售票员上岗问题、公司内部人员安排出效益等。降低成本、提高效益是问题的

关键。

1.1 MATLAB解优化问题的主要函数

1.2 优化函数的输入变量

1.3 优化函数的输出变量下表

1.4 控制参数options的设置

(1)Display: 显示水平.取值为’off’时,不显示输出; 取值为’iter’时,显示每次迭代的信息;取值为’final’时,显示最终结果.默认值为

’final’.

(2)MaxFunEvals: 允许进行函数评价的最大次数,取值为正整数

.

(3) MaxIter: 允许进行迭代的最大次数,取值为正整数

控制参数options可以通过函数optimset创建或修改。命令

的格式如下：

(1) options=optimset(‘optimfun’)

创建一个含有所有参数名,并与优化函数optimfun相关的默

认值的选项结构options.1.4 控制参数options的设置

(2)options=optimset(‘param1’,value1,’param2’,value2,...)

创建一个名称为options的优化选项参数,其中指定的参数

具有指定值,所有未指定的参数取默认值.

(3)options=optimset(oldops,‘param1’,value1,’param2’,

value2,...)

创建名称为oldops的参数的拷贝,用指定的参数值修改

oldops中相应的参数.

例：opts=optimset(‘Display’,’iter’,’TolFun’,1e-8)

该语句创建一个称为opts的优化选项结构,其中显示参数

设为’iter’, TolFun参数设为1e-8.

2.1 一元函数无约束优化问题

一元函数无约束优化问题

常用格式如下：

（1）x= fminbnd (fun,x1,x2)

（2）x= fminbnd (fun,x1,x2，options)

（3）[x，fval]= fminbnd（...）

（4）[x，fval，exitflag]= fminbnd（...）（5）[x，fval，exitflag，output]= fminbnd（...）函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只

给出局部最优解。

2.1 一元函数无约束优化问题

例在0程序如下：

f='2*exp(-x).*sin(x)';

fplot(f,[0,8]); %作图语句

[xmin,ymin]=fminbnd (f, 0,8)

f1='-2*exp(-x).*sin(x)';

[xmax,ymax]=fminbnd (f1, 0,8)

运行结果：

xmin = 3.9270 ymin = -0.0279

xmax = 0.7854 ymax = 0.48

2.2 多元函数无约束优化问题

标准型为：min F(X)

命令格式为:

（1）x= fminunc（fun,X0）

或x=fminsearch（fun,X0）

（2）x= fminunc（fun,X0，options）；

或x=fminsearch（fun,X0，options）

（3）[x，fval]= fminunc（...）；

或[x，fval]= fminsearch（...）

（4）[x，fval，exitflag]= fminunc（...）；

或[x，fval，exitflag]= fminsearch （5）[x，fval，exitflag，output]= fminunc（...）；

或[x，fval，exitflag，output]= fminsearch（.3 多元函数无约束优化问题

说明:

• fminsearch是用单纯形法寻优. fminunc的算法见以下几点说明：

[1] fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控

制：

LargeScale=’on’(默认值),使用大型算法

LargeScale=’off’(默认值),使用中型算法

[2] fminunc为中型优化算法的搜索方向提供了4种算法，由

options中的参数HessUpdate控制：

HessUpdate=’bfgs’（默认值），拟牛顿法的BFGS公式；

HessUpdate=’dfp’，拟牛顿法的DFP公式；

HessUpdate=’steepdesc’，最速下降法

[3] fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数

LineSearchType控制：

LineSearchType=’quadcubic’(缺省值)，混合的二次和三次多项式插值；

LineSearchType=’cubicpoly’，三次多项式插

使用fminunc和 fminsearch可能会得到局部最优解

2.2 多元函数无约束优化问题

例min f(x)=(4*x1^2+2*x2^2+4*x1*x2+2*x2+1)*exp(x1)

1、编写M-文件 fun1.m:

function f = fun1 (x)

f = exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

2、输入M文件wliti3.m如下:

x0 = [-1, 1];

x=fminunc(‘fun1’,x0);

y=fun1(x)

3、运行结果:

x= 0.5000 -1.0000

y = 1.3029e-10

2.3 二次规划

用MATLAB软件求解,其输入格式如下:

1. x=quadprog(H,C,A,b);

2. x=quadprog(H,C,A,b,Aeq,beq);

3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);

4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0);

5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options);

6. [x,fval]=quaprog(...);

7. [x,fval,exitflag]=quaprog(...);

8. [x,fval,exitflag,output]=quaprog(...);

2.3 二次规划

例 min f(x1,x2)=-2*x1-6*x2+x1^2-2*x1*x2+2*x2^2

s.t. x1+x2≤2

-x1+2x2≤2

x1≥0, x2≥0

1、写成标准形式：

2、输入命令：

H=[1 -1; -1 2];

c=[-2 ;-6];A=[1 1; -1 2];b=[2;2];

Aeq=[];beq=[]; VLB=[0;0];VUB=[];

[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)

3、运算结果为：

x =0.6667 1.3333 z = -8.22222.4 一般非线性规划

标准型为min F(X)

s.t AX<=b G(X)

Ceq(X)=0 VLB X VUB

其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：

1. 首先建立M文件fun.m,定义目标函数F（X）:

function f=fun(X);

f=F(X);

2. 若约束条件中有非线性约束:G(X)或Ceq(X)=0,则建立M文件

nonlcon.m定义函数G(X)与Ceq(X):

function [G,Ceq]=nonlcon(X)

G=...

Ceq=...

2.4 一般非线性规划

3. 建立主程序.非线性规划求解的函数是

fmincon,命令的基本格式如下：

(1) x=fmincon(‘fun’,X0,A,b)

(2) x=fmincon(‘fun’,X0,A,b,Aeq,beq)

(3) x=fmincon(‘fun’,X0,A,b, Aeq,beq,VLB,VUB)

(4)

x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)

(5)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’

,options)

(6) [x,fval]= fmincon(...)

(7) [x,fval,exitflag]= fmincon(...)

(8)[x,fval,exitflag,output]= fmincon(...)2.4 一般非线性规划

注意：

[1] fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为’on’），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。

[2] fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。

[3] fmincon函数可能会给出局部最优解，这与

初值X0的选取有关。

2.4 一般非线性规划

例

2.4 一般非线性规划

2、先建立M-文件 fun3.m:

function f=fun3(x);

f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2

3、再建立主程序youh2.m：

x0=[1;1];

A=[2 3 ;1 4]; b=[6;5];

Aeq=[];beq=[];

VLB=[0;0]; VUB=[];

[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)

4、运算结果为：

x = 0.77 1.0588

fval = -2.0294

2.5 线性规划问题

线性规划问题

线性规划问题是目标函数和约束条件均为线性函数的问题，MATLAB6.0 解决的线性规划

问题的标准形式为：

min f(x)

sub.to：

x A ≤b ⋅ x Aeq = beq⋅ub≤ x≤ lb

其中 f、x、b、beq、lb、ub 为向量，A、Aeq 为矩阵。其它形式的线性规划问题都可经过适当变换化为此标准形式。

x = linprog(f,A,b,Aeq,beq,lb,ub,x0) %设置初值 x03 MATLAB优化工具箱

1 工具箱

（1）求解无约束条件非线性极小值；（2）求解约束条件下非线性极小值，包括目标逼近问题、极大-极小值问题和半无限极小值

问题；

（3）求解二次规划和线性规划问题；

（4）非线性最小二乘逼近和曲线拟合；

（5）非线性系统的方程求解；

（6）约束条件下的线性最小二乘优化；

（7）求解复杂结构的大规模优化问题。

3 MATLAB优化工具箱

2 工具箱函数

一元函数极小值X=fminbnd(‘F’,x1,x2)

无约束极小X=fminunc(‘F’,X0)

X=fminsearch(‘F’,X0)

线性规划X=linprog(c,A,b)

0-1整数规划X=bintprog(F) 二次规划X=quadprog(H,c,A,b)

约束极小值（非线性规划）

X=fmincon(‘FG’,X0)

非线性最小二乘X=lsqnonlin(F,X0) 目标达到问题X=fgoalattain(‘F’,x,goal,w)极小极大问题X=fminimax(‘FG’,x0)3.1 GUI优化工具

命令行输入optimtool；

Start->Toolboxes->Optimization->Optimization

tool(optimtool)

3.2 使用步骤

1.选择求解器solver和优化算法algorithm；

2.选定目标函数（objective function）；

3.设定目标函数的相关参数；

4.设置优化选项；

5.单击“start”按钮，运行求解；

6.查看求解器的状态和求解结果；

7.将目标函数、选项和结果导入\\导出。

3.2 使用步骤

3.3 应用实例一

无约束优化（fminunc求解器）

求f(x)=x^2+4*x-6极小值，初始点取x=0。

解：

1.首先建立目标函数文件FunUnc.m文件：

function y=FunUnc(x)

y=x^2+4*x-6;

2. 然后启动优化工具3.3 应用实例一

3.3 应用实例一

Algorithm有两个选择：Large scale和Medium scale，设置完参数点击start即可得到上图中

的结果。

3.4 应用实例二

无约束优化（fminsearch求解器）

求f(x)=|x^2-3*x+2|的极小值，初始点取x=-7

解：

1.解：启动优化工具；

用fminunc时设置参数如图

2. 运行得到结果

3.4 应用实例二4 高级优化算法

习惯上，将优化算法分为两类：局部优化算法和全局性优化算法。前者可以称为经典优化算法，已经得到了人们广泛深入的研究。线性规划、整数规划、0–1规划、非线性规划、排队论、决策论。后者习惯上称为现代优化算法，是20世纪80年代兴起的新型全局性优化算法，主要包括禁忌搜索、模拟退火、遗传算法、神经网络等，其主要应用对象是优化问题中的难解问题，即NP–

hard问题

4.1 算法简介

为了找出地球上最高的山，一群有志气的兔

子们开始想办法。

4.1 算法简介

方案一：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。

遗传算法

4.1 算法简介

方案二：兔子们朝着比现在高的地方跳去，它们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。其实，它们这种做法只是自己心理上认为找到了最高的山，并不能保证局部最优值就是全局最优值。

局部搜索法4.1 算法简介

方案三：兔子们知道一个兔子的力量是渺小的。于是，它们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻找的策略。

禁忌搜索法

4.1 算法简介

方案四：兔子们用酒将自己灌醉了。它们随机地跳了很长时间。在这期间，它们可能走向高处，也可能踏入平地。但是，随着时间的流逝，它们渐渐清醒了并朝最高方

向跳去。

模拟退火法

2015/4/24

4.2 遗传算法基本思想

遗传算法流程图如下

编码和初始集团生成

集团中个体适应度的检测评估

选择

交叉

变异

图1 遗传算法的基本流程

4.3 模拟退火算法简介

1) 任选一初始状态作为初始解，并设初

始温度；

2) 调用采样算法，然后返回到当前解；

3) 按一定的方式将降温

4) 检查退火过程是否结束，否则转到 2)；

5) 以当前解作为最优解输出。

19