logo

第 8 章 优化与非线性方程

作者
Modified on
Reading time
13 分钟阅读:..评论:..

优化问题在工程实践中十分常见,如何利用数学模型和计算机算法高效求解优化问题,是每一个科研工作者和工程师必须掌握的重要技能。MATLAB 作为一款强大的数值计算软件,内置了丰富的优化算法和工具箱,使得求解优化问题和非线性方程组变得十分便捷。

8.1 优化问题概述

优化问题在数学和工程领域有着广泛而重要的应用。从生活中的购物选择、资源分配,到工业生产的过程优化、成本控制,再到人工智能中的模型训练与调参,处处都有优化问题的身影。

8.1.1 优化问题的基本概念

一个标准的优化问题可以用以下数学模型描述:

其中:

  • 称为目标函数,表示我们希望最小化的性能指标。
  • 和
    称为约束条件,对决策变量
    的取值进行限制。
  • 决策变量
    是一个
    维实数向量,代表我们可以调节的参数。
  • 最优解
    是满足约束条件下目标函数取得最小值时的
    值。

举个简单的例子,假设我们要制造一种混合果汁,目标是用最少的成本达到最佳的口感。我们可以调节苹果汁、橙汁、芒果汁的比例(即决策变量

),同时要求各种果汁比例非负且和为 1(约束条件),并且希望最小化成本(目标函数)。这就是一个典型的优化问题。

8.1.2 优化问题的分类

根据目标函数和约束条件的不同,优化问题可以分为以下几类:

  1. 线性规划(Linear Programming) 目标函数和约束条件都是决策变量的线性函数,如:
    其中
    是
    矩阵,
    和
    分别是
    维和
    维列向量。
  2. 非线性规划(Nonlinear Programming) 目标函数或约束条件中至少有一个是决策变量的非线性函数,没有其他特殊结构的优化问题。
  3. 二次规划(Quadratic Programming) 目标函数是决策变量的二次函数,约束条件是线性的,如:
    其中
    是
    的半正定矩阵。
  4. 整数规划(Integer Programming) 部分或全部决策变量要求是整数。当决策变量限制为 0-1 整数时,称为 0-1 整数规划。
  5. 多目标规划(Multi-objective Programming) 有多个目标函数需要同时优化,通常目标之间存在矛盾和冲突。

MATLAB 的优化工具箱提供了丰富的函数来求解以上各类优化问题。不同类型的问题在建模和求解上有不同的特点,需要根据具体问题选择合适的优化算法。 接下来我们将重点介绍几类常见优化问题的 MATLAB 求解方法。限于篇幅,我们只能介绍一些基本用法,更多的算法细节和参数设置还需要大家在实践中去探索。

8.2 线性规划

线性规划(LP)是优化领域历史最悠久、应用最广泛的一类问题。它的特点是目标函数和约束条件都是决策变量的线性函数,整个问题只涉及一次项而没有高次项。许多实际问题如资源分配、生产计划、运输问题等都可以建模为线性规划。

8.2.1 线性规划的基本模型

线性规划的标准形式如下:

其中,
是决策变量,
是约束矩阵,
和
分别是目标函数和约束条件的系数向量。 除标准形式外,线性规划还可以有其他等价的形式,如松弛形式:
以及变量无非负限制的形式:
不同的问题形式,在建模和求解时需要进行适当的转化。

8.2.2 线性规划的求解方法

求解线性规划的主要方法是单纯形法(Simplex Method),它是一种迭代搜索的算法,通过不断沿着可行域的边界移动,直到找到最优解。单纯形法的基本步骤如下:

  1. 将问题转化为标准形式。
  2. 构造初始可行解,作为第一个单纯形。
  3. 检查是否满足最优性条件,如果满足则当前解即为最优解,算法终止;否则转 4。
  4. 确定一个可以改进目标函数的移动方向,得到新的单纯形。
  5. 回到步骤 3,直到找到最优解或确定问题无界。

除单纯形法外,还有内点法(Interior Point Method)等现代优化算法可以求解线性规划。这些算法通过启发式的方法在可行域内部搜索,不需要经过可行域的顶点,在大规模问题上往往比单纯形法更有效。

8.2.3 MATLAB 中的线性规划函数

MATLAB 优化工具箱提供了linprog函数来求解线性规划问题。它的基本语法为:

x = linprog(c,A,b,Aeq,beq,lb,ub)

其中:

  • c: 目标函数系数向量
  • A,b: 不等式约束系数矩阵和右端向量
  • Aeq,beq: 等式约束系数矩阵和右端向量
  • lb,ub: 决策变量下界和上界向量

除了以上必需的输入参数外,linprog还可以设置一些可选参数,如:

options = optimoptions('linprog','Display','iter','Algorithm','interior-point');
[x,fval,exitflag,output] = linprog(c,A,b,[],[],[],[],[],options);
  • 'Display': 控制迭代输出的级别,如'iter'为输出每一步迭代信息。
  • 'Algorithm': 指定优化算法,如'interior-point'为使用内点法。
  • exitflag: 求解终止代码,表示求解结果的状态。
  • output: 求解输出结构体,包含算法性能信息如迭代次数、目标函数值等。

下面我们看一个线性规划的简单例子。 例 1 考虑如下的生产计划问题:

其中,
和
分别表示产品 1 和产品 2 的生产数量,目标是使总利润最大化。约束条件反映了生产资源的限制。 利用 MATLAB 求解上述问题的代码如下:

c = [-2; -3];  % 目标函数系数向量
A = [1 1; 2 1];  % 不等式约束矩阵
b = [8; 10];  % 不等式约束右端向量
lb = [0; 0];  % 决策变量下界
[x,fval,exitflag,output] = linprog(c,A,b,[],[],lb);
fprintf('最优解为: x1 = %.2f, x2 = %.2f\n',x(1),x(2));
fprintf('最优目标函数值为: %.2f\n',-fval);

输出结果为:

最优解为: x1 = 2.00, x2 = 6.00
最优目标函数值为: 22.00

可见,在给定约束下,最优生产计划是生产 2 个产品 1 和 6 个产品 2,总利润为 22。 linprog函数功能非常强大,可以处理各种不同形式的线性规划问题。感兴趣的读者可以进一步探索它的用法,并将其应用到实际问题中。

8.3 非线性规划

现实世界中的许多优化问题是非线性的,即目标函数或约束条件中含有决策变量的高次项、三角函数、指数函数等。非线性规划问题的求解比线性规划更具挑战性,需要用到数值优化的各种算法。

8.3.1 非线性规划的基本模型

一般的非线性规划问题可以表示为:

其中目标函数
和约束函数
,
是
的非线性函数。与线性规划相比,非线性规划有以下特点:

  • 目标函数可能是非凸的,存在多个局部最优解。
  • 约束条件定义的可行域可能是非凸集。
  • 不能用单纯形法等图解法直观求解。
  • 需要用迭代算法逼近最优解,通常无法给出精确解。

常见的非线性规划问题如:

  • 非线性最小二乘问题
  • 二次规划问题

8.3.2 非线性规划的求解方法

非线性规划的常用求解方法有:

  • 罚函数法:将约束问题转化为一系列无约束问题求解
  • 序列二次规划(SQP):用二次规划子问题逼近原问题
  • 内点法:沿着中心路径搜索可行点和最优点
  • 遗传算法等启发式算法:模拟生物进化过程搜索最优解

在MATLAB中可以用fmincon函数求解一般的非线性规划问题,例如:

fun = @(x) (x(1)-5)^2 + (x(2)-8)^2;  % 目标函数
A = [1 2];  % 不等式约束矩阵
b = 10;  % 不等式约束右端向量
Aeq = [1 1];  % 等式约束矩阵
beq = 7;  % 等式约束右端向量
lb = [0 0];  % x的下界
ub = [5 5];  % x的上界
x0 = [0 0];  % 初始点

[x,fval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)

8.3.3 MATLAB 非线性规划实例

我们来考虑一个典型的非线性规划问题——投资组合优化。假设有n种风险资产可供投资,预期收益率向量为r,协方差矩阵为V,求最小化投资组合方差的最优权重向量w。该问题可以表述为:

其中e为全1向量。这里目标函数是二次的,约束是线性的,因此是一个二次规划问题。 我们用MATLAB求解一个具体例子。假设有3只股票,它们的预期年收益率分别为5%, 7%, 6%,年化收益率的协方差矩阵为:
MATLAB实现如下:

r = [0.05; 0.07; 0.06];  % 预期收益率
V = [0.0100 0.0018 0.0011; 
    0.0018 0.0109 0.0026;
    0.0011 0.0026 0.0199];  % 协方差矩阵

H = V;
f = zeros(3,1);

A = ones(1,3);
b = 1;
Aeq = [];
beq = [];
lb = zeros(3,1);
ub = [];

[w,fval] = quadprog(H,f,A,b,Aeq,beq,lb,ub);
fprintf('最优投资组合权重为: \n');
disp(w);
fprintf('最小投资组合方差为: %.4f\n',fval);

运行结果为:

最优投资组合权重为:

    0.3021
    0.4438
    0.2540

最小投资组合方差为: 0.0050

可见,在给定的三只股票中,第二只股票权重最大,第三只股票权重最小,最优组合的年化方差约为 0.5%。这反映了投资者在追求高收益的同时,也要控制投资组合风险。

8.4 非线性方程组

非线性方程组求解是优化问题的另一个分支,它的目标是找到一组变量值使得多个非线性方程同时成立。非线性方程组在物理、工程等领域有广泛应用,如求解平衡点、计算化学平衡等。

8.4.1 非线性方程组的基本概念

非线性方程组可以表示为:

或者写成向量形式:
其中
是
维未知向量,
是非线性向量值函数。 非线性方程组的解不像线性方程组那样有统一的解法,需要根据问题的特点选择适当的数值迭代算法。常用的迭代格式为:
其中
为步长,
为搜索方向。不同的算法在迭代格式中有不同的选择。

8.4.2 求解非线性方程组的方法

常用的非线性方程组数值解法有:

  • 牛顿法和拟牛顿法:利用 Taylor 展开逼近,求解线性化方程组
  • Gauss-Newton 法:用最小二乘思想简化牛顿法
  • Levenberg-Marquardt 方法:介于 Gauss-Newton 法和最速下降法之间

这些算法往往需要提供 Jacobi 矩阵的信息,当

很大时计算量很大。

8.4.3 MATLAB 非线性方程组求解

MATLAB 提供了fsolve函数用于求解非线性方程组和系统,它综合了几种数值算法,可以自动选择合适的求解器。 fsolve的基本语法为:

x = fsolve(fun,x0)

其中 fun 为计算方程组残差

的函数, x0 为初始迭代点。

例3 考虑如下非线性方程组:

它对应的向量值函数为:
我们用MATLAB的fsolve函数求解这个方程组。 首先定义向量值函数:

function F = myfun(x)
F = [x(1)^2 - x(2) - 1;
    x(1)^2 + x(2)^2 - 9];
end

然后调用fsolve函数:


x0 = [1; 1];  % 初始点
[x,fval,exitflag] = fsolve(@myfun, x0);
fprintf('方程组的解为:\n');
disp(x);

fprintf('函数值的2-范数为: %e\n',norm(fval));
fprintf('求解终止代码为: %d\n',exitflag);

运行结果为:

方程组的解为:
    2.0000
    3.0000

函数值的2-范数为: 2.220446e-16
求解终止代码为: 1

其中 exitflag 为 1 表示fsolve在函数容差范围内收敛到一个解。可以验证(2,3)确实是原方程组的一个解。 需要注意的是,非线性方程组的解不唯一,迭代算法得到哪个解依赖于初始点的选择。比如将上面代码中的初始点改为:

x0 = [-1; -1];

则得到的解为(-2,3),它也是原方程组的一个解。这启示我们在用数值方法求解非线性问题时,要注意初值的选择对结果的影响。 此外,对于大规模稀疏非线性方程组,MATLAB 还提供了fsolve的稀疏版本fsolve(...,'JacobPattern',S)和预条件版本fsolve(...,'Preconditioner',M)等,可以提高求解效率。

< 第 7 章：图像处理
第 9 章 机器学习与数据挖掘 >