几类无约束最优化问题全局最优解的Matlab实现

2022-09-11

第二次世界大战以来, 最优化理论和方法获得了蓬勃发展[1], 并逐步应用到生产、管理、商业以及军事和决策等领域。其基本的想法是对各种实际问题寻求最优解, 构造求解的计算方法, 并研究这些计算方法的理论性质和实际计算结果。最直接的做法是利用已有的物理、化学、生物、经济等各种领域中的规律, 建立数学模型, 然后寻求自变量范围内目标函数的最优解。在已有的一些算法中, 如:最速下降法, Newton法, 共轭梯度法和拟Newton法等, 只能获得初始点附近的局部最优解。而一般来说, 只有全局收敛性才具有实际意义, 于是如何寻求目标函数的全局最优解引起了研究者的极大兴趣并取得了众多的成果[2]。另一方面, 如果我们能够找到全局最优点的近似值然后把它作为初始值, 再利用已有的局部最优化算法, 也能获得目标函数的全局最优解, 目前被广泛采用的Matlab数学软件[3~4], 从某种程度上能够实现这种想法。

本文试图采用Matlab强大的数值计算和可视化功能, 先找到目标函数全局最优解的近似值, 然后利用Matlab最优化工具箱中的函数, 获得目标函数的全局最优解, 也为增强《最优化方法》教学中的趣味性和探索性提供了一条可行的途径。

1 全局最优解

下面分别考虑几类无约束最优化问题的全局最优解。

1.1 一维最优化问题

单变量函数的最优化问题的求解一般采用线性搜索法, 如:Fibonacci法, 黄金分割法, 进退法和不精确一维搜索Wolfe算法等。Matlab最优化工具箱中求解单变量极值的函数fminbnd也只能求得某一个极值点, 不能得到全局最优解。于是, 我们先通过画出单变量函数的图形找到最优点的近似坐标, 然后利用fminbnd函数寻求目标函数的全局最优解。我们考虑下面的最优化问题:

该函数有多个极值点, 我们首先利用Matlab的作图功能画出其图形 (图1) , 并找到全局最优点的近似坐标 (0.9274, -1.3693) , 对应的Matlab程序为:

再利用fminbnd函数, 获得了目标函数的全局最优点 (0.9399, -1.3706) , Matlab程序实现如下:

而如果直接把x的范围写为[0, 5], 即以上程序修改为:[x1, fval]=fminbnd (y1, 0, 5)

则只能得到f (x) 的一个极值点 (3.0340, -1.0456) , 不能得到f (x) 的全局最小点。

1.2 二维最优化问题

当目标函数有两个变量时, 其全局最优解的获得自然比单变量函数要复杂, 但还是可以通过做图法求解。比如求解下列最优化问题:

利用Matlab的画图功能, 得到三维图2, 以及网格划分后的全局最小点近似坐标 (0, 2.2, -5.06) , 然后以 (0, 2.2) 为初始值, 由函数fminsearch或者fminunc可得目标函数的全局最小点为 (0.0333, 2.2666, -5.0633) 。相应的Matlab程序为:

1.3 多维最优化问题

多元函数的全局最优化问题的理论和方法远没有局部最优化方法那么成熟和完善, 到目前为止甚至还没有一个全局性的判断准则。然而也有一些方法能够近似的得到目标函数的全局最优解, 如:区间方法, 模拟退火法和遗传算法等。本文却先根据模拟退火法给出多元目标函数全局最小值的近似值, 然后进一步采用局部最优化算法获得全局最优解。如考虑下列最优化问题:

利用[4]中提供的模拟退火法函数Opt_Simu, 编辑Matlab程序为:

得到全局最优解的近似值1.5187, 最小值点为x1= (-1.6483, -1.5148, 1.2168) , 进一步, 取x1为初始点, 采用函数fminsearch和fminunc可得目标函数的最小值1.2415, 最小值点x1相应的修改为 (-1.4187, -1.4187, 1.4188) 。