西莫电机圈

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

手机号码,快捷登录

查看: 553|回复: 0

[分享] MATLAB极小值优化

[复制链接]

签到天数: 1 天

连续签到: 1 天

[LV.1]初来乍到

发表于 2019-7-3 19:13 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

x
极小值优化
1.标量最小值优化
求解单变量最优化问题的方法有多种,根据目标函数是否需要求导,可以分为两类,即直接法和间接法。直接法不需要对目标函数进行求导,而间接法则需要用到目标函数的导数。
常用的一维直接法主要有消去法和近似法两种。
(1)消去法:该法利用单峰函数具有的消去性质进行反复迭代,逐渐消去不包含极小点的区间,缩小搜索区间,直到搜索区间缩小到给定的允许精度为止。一种典型的消去法为黄金分割法(Golden Section Search)。黄金分割法的基本思想是在单峰区间内适当地插入两点,将区间分为3段,然后通过比较这两点函数值的大小来确定是删去最左段还是最右段,或同时删去左右两段,而保留中间段。重复该过程可以使区间无限缩小。插入点的位置放在区间的黄金分割点及其对称点上,所以该法称为黄金分割法。该法的优点是算法简单,效率较高,稳定性好。
(2)多项式近似法:该法用于目标函数比较复杂的情况。此时搜索一个与它近似的函数代替目标函数,并用近似函数的极小点作为原函数极小点的近似。常用的近似函数为二次和三次多项式。二次插值法的计算速度比黄金分割法快,但是对于一些强烈扭曲或可能多峰的函数,该法的收敛速度会变得很慢,甚至失败。
间接法需要计算目标函数的导数,优点是计算速度很快。常见的间接法包括牛顿切线法、对分法、割线法和三次插值多项式近似法等。优化工具箱中用得较多的是三次插值法。如果函数的导数容易求得,一般来说应首先考虑使用三次插值法,因为它具有较高的效率。在只需要计算函数值的方法中,二次插值法是一个很好的方法,它的收敛速度较快,特别是在极小点所在区间较小时尤为如此。黄金分割法则是一种十分稳定的方法,并且计算简单。基于以上分析,MATLAB优化工具箱中使用得较多的方法是二次插值法、三次插值法、二次三次混合插值法和黄金分割法。
MATLAB优化工具箱提供了fminbnd函数来进行标量最小值问题的优化求解,其调用语法如下。
(1)x = fminbnd(fun,x1,x2):返回标量函数fun在条件x1 < x < x2下取最小值时自变量x的值。
(2)x = fminbnd(fun,x1,x2,options):用options参数指定的优化参数进行最小化。
(3)x = fminbnd(problem):求解problem的最小值,其中problem是一个用输入变量来表达的结构数组。
(4)[x,fval] = fminbnd(...):返回解x处目标函数的值fval。
(5)[x,fval,exitflag] = fminbnd(...):返回exitflag值描述fminbnd函数的退出条件。
(6)[x,fval,exitflag,output] = fminbnd(...):返回包含优化信息的结构数组output。
其中fun为需要最小化的目标函数。fun函数需要输入标量参数x,返回x处的目标函数标量值f。fun可以是一个匿名函数的函数句柄,如下所示:
x = fminbnd(inline('sin(x*x)'),x0)
同样,fun参数也可以是一个包含函数名的字符串,对应的函数可以是M文件、内部函数或MEX文件。options为优化参数选项,用户可以用optimset函数设置或改变参数的值。至于options参数的具体设置,读者可自行查阅帮助文档。
【例11-1】  对边长为3m的正方形铁板,在4个角处剪去相等的正方形,以制成方形无盖水槽,问如何剪才能使水槽的容积最大?
假设剪去的正方形的边长为x,则水槽的容积为:

现在要求在区间(0,1.5)上确定一个x,使V最大化。因为优化工具箱中要求目标函数最小化,所以需要对目标函数进行转换:V1=-V,即要求V1的最小值。
首先编写此问题的函数M文件:
myfun1.m
function f = myfun1(x)
f = -(3-2*x).^2 * x;
然后在命令行调用fminbnd函数:
>> x = fminbnd(@myfun1,0,1.5)
x =
    0.5000
即剪掉的小正方形的边长为0.5m时水槽的容积最大。我们可以调用myfun1函数来计算水槽的最大容积:
>> y= -myfun1(x)
y =
    2.0000
水槽的最大容积为。
2.无约束最小值优化
无约束最优化问题在实际应用中也比较常见,如工程中常见的参数反演问题。另外,许多有约束最优化问题也可以转化为无约束最优化问题进行求解。
求解无约束最优化问题的方法主要有两类,即直接搜索法(Search method)和梯度法(Gradient method)。
直接搜索法适用于目标函数高度非线性,没有导数或导数很难计算的情况。实际工程中很多问题都是非线性的,因此直接搜索法不失为一种有效的解决办法。常用的直接搜索法为单纯形法,此外还有Hooke-Jeeves搜索法、Pavell共轭方向法等,其缺点是收敛速度慢。
在函数的导数可求的情况下,梯度法是一种更优的方法,该法利用函数的梯度(一阶导数)和Hessian矩阵(二阶导数)构造算法,可以获得更快的收敛速度。函数f(x)的负梯度方向即反映了函数的最大下降方向。当搜索方向取为负梯度方向时,称为最速下降法。但当需要最小化的函数有一狭长的谷形值域时,该法的效率则很低。常见的梯度法有最速下降法、Newton法、Marquart法、共轭梯度法和拟牛顿法(Quasi-Newton method)等。在这些方法中,用得最多的是拟牛顿法。
在MATLAB中,有fminunc和fminsearch两个函数用来求解无约束最优化问题。由于MATLAB优化工具箱表11-1中列出的函数调用语法和参数说明都比较类似,同时篇幅有限,所以下面只举例来说明一下这些函数的用法。
【例11-2】  求函数的最小值。
首先编写函数的M文件。需要注意的是:本例中的目标函数具有两个变量,在编写函数的时候需要将这两个自变量作为列向量输入目标函数。M文件的具体内容如下:
myfun2.m
function f = myfun2(x)
f = 3*x(1)^2 + 2*x(1)*x(2) + x(2)^2;    %  目标函数
然后在命令行调用fminunc函数来寻找目标函数在点[1,1]附近的最小值:
x0 = [1,1];
[x,fval] = fminunc(@myfun2,x0)
fminunc函数经过多次迭代之后,给出如下计算结果:
x =                                      %  最小值所对应的x值
  1.0e-006 *
    0.2541   -0.2029
fval =                                  %  最小值的大小
  1.3173e-013
【例11-3】  求banana方程的最小值:

通过分析可知,最小值0所对应的点为(a,a2)。可以在指定a的情况下求这个方程的最小值,例如让a = sqrt(2)。下面来创建一个包含参数a的匿名函数:
>> a = sqrt(2);
>> banana = @(x)100*(x(2)-x(1)^2)^2+(a-x(1))^2;
然后在MATLAB命令行中输入以下命令:
>> [x,fval,exitflag] = fminsearch(banana, [-1.2, 1], ...
   optimset('TolX',1e-8))       %  optimset('TolX',1e-8)用来设置算法终止误差
x =
    1.4142    2.0000
fval =
  4.2065e-018
exitflag =
     1
在点(sqrt(2), 2)得到了函数的最小值,fval非常接近于0,这说明本例中fminsearch函数的优化计算是非常成功的。
3.线性规划
线性规划是处理线性目标函数和线性约束的一种较为成熟的方法,目前已经广泛地应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。线性规划问题的标准形式是:

写成矩阵形式为:

其中:

线性规划的标准形式要求目标函数最小化,约束条件取等式,变量非负。不符合这几个条件的线性模型要首先转换成标准形。线性规划的求解方法主要是单纯形法。
MATLAB优化工具箱提供了linprog函数用来进行线性规划的求解。
【例11-4】  求如下函数的最小值。

首先在MATLAB命令行中输入以下参数:
>> f = [-5; -4; -6];      %  用矩阵表示目标函数
>> A = [1  -1  1
      3   2  4
      3   2  0];          %  用矩阵形式表示约束条件系数
>> b = [20; 42; 30];     %  约束条件
>> lb = zeros(3,1);      %  下界约束
然后调用linprog函数:
>> [x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb);
Optimization terminated.
>> x,lambda.ineqlin,lambda.lower       %  显示结果
x =
    0.0000
   15.0000
    3.0000
ans =
    0.0000
    1.5000                                  %  主动约束
    0.5000                                  %  主动约束
ans =
    1.0000                                  %  主动约束
    0.0000
    0.0000
Lambda域中向量里的非零元素可以反映出求解过程中的主动约束。在本例的结果中可以看出,第2个和第3个不等式约束(lambda.ineqlin)和第1个下界约束(lambda.lower)是主动约束。
4.二次规划
二次规划是非线性规划中一类特殊的数学规划问题,它的解是可以通过求解得到的。通常通过解其库恩-塔克条件(K-T条件),获取一个K-T条件的解,称为K-T对,其中与原问题的变量对应的部分称为K-T点。二次规划的一般形式为:

其中为对称矩阵。二次规划分为凸二次规划与非凸二次规划两者,前者的K-T点便是其全局极小值点,而后者的K-T点则可能连局部极小值点都不是。若它的目标函数是二次函数,则约束条件是线性的。求解二次规划的方法很多,较简便易行的是沃尔夫法,它是依据K-T条件,在线性规划单纯形法的基础上加以修正而得到的。此外还有莱姆基法、毕尔法、凯勒法等。
MATLAB优化工具箱中提供了quadprog函数用来进行二次规划的求解。
【例11-5】  求下面函数的最小值。

首先,我们注意到这个方程可以用矩阵形式来表示:

其中:

在MATLAB命令行中输入以下参数命令:
>> H = [1 -1; -1 2];
>> f = [-2; -6];
>> A = [1 1; -1 2; 2 1];     %  线性不等式约束
>> b = [2; 2; 3];             %  线性不等式约束
>> lb = zeros(2,1);
然后调用二次规划函数quadprog:
>> [x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb)
Optimization terminated.
x =
    0.6667
    1.3333
fval =
   -8.2222
exitflag =
     1
output =
       iterations: 3
        algorithm: 'medium-scale: active-set'
    firstorderopt: []
     cgiterations: []
          message: 'Optimization terminated.'
lambda =
      lower: [2x1 double]
      upper: [2x1 double]
      eqlin: [0x1 double]
    ineqlin: [3x1 double]
exitflag = 1表示计算的退出条件是收敛于x。output是包含着优化信息的结构数组。lambda返回了x处包含拉格朗日乘子的参数。
5.有约束最小值优化
在有约束最优化问题中,通常要将该问题转换为更简单的子问题,对这些子问题可以求解并作为迭代过程的基础。早期的方法通常是通过构造惩罚函数等,将有约束的最优化问题转换为无约束最优化问题进行求解。现在,这些方法已经被更有效的基于K-T方程解的方法所取代。K-T方程是有约束最优化问题求解的必要条件。
MATLAB优化工具箱提供了fmincon函数用来计算有约束的最小值优化。
【例11-6】  求函数的最小值,搜索的起始值为x = [10;10;10],同时目标函数中的变量要服从以下约束条件:

首先要写一个以x为变量的目标函数myfun3.m,该目标函数要返回一个标量。
myfun3.m
function f = myfun3(x)
f = -x(1) * x(2) * x(3);
其次,改写约束条件为小于或者等于一个常数的形式:

接下来,因为两个约束都是线性的,所以可以将其用矩阵来表示成这种形式,其中:

然后调用fmincon函数进行优化:
>> x0 = [10; 10; 10];    % 求解的起始点
>> A=[-1 -2 -2;1 2 2];
>> b=[0;72];
>> [x,fval] = fmincon(@myfun3,x0,A,b)
x =
   24.0000
   12.0000
   12.0000
fval =
-3.4560e+003
最后可以对约束条件进行验证:
>> A*x-b
ans =
   -72
     0

评分

参与人数 1西莫币 +3 收起 理由
土豆烧洋芋 + 3 感谢分享

查看全部评分

西莫电机论坛微信公众平台正式上线!★详情请点击★ 西莫电机论坛会员交流专用群欢迎您西莫电机论坛加群请注明论坛用户名及所从事专业,否则不予通过
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|小黑屋|手机版|Archiver|西莫电机圈 ( 浙ICP备10025899号-3 浙公网安备:33028202000436号

GMT+8, 2024-3-29 09:27 , Processed in 0.078608 second(s), 25 queries .

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表