第 8 章 优化与非线性方程
- 作者
- Name
- 青玉白露
- Github
- @white0dew
- Modified on
- Reading time
- 13 分钟
阅读:.. 评论:..
优化问题在工程实践中十分常见,如何利用数学模型和计算机算法高效求解优化问题,是每一个科研工作者和工程师必须掌握的重要技能。MATLAB 作为一款强大的数值计算软件,内置了丰富的优化算法和工具箱,使得求解优化问题和非线性方程组变得十分便捷。
8.1 优化问题概述
优化问题在数学和工程领域有着广泛而重要的应用。从生活中的购物选择、资源分配,到工业生产的过程优化、成本控制,再到人工智能中的模型训练与调参,处处都有优化问题的身影。
8.1.1 优化问题的基本概念
一个标准的优化问题可以用以下数学模型描述:
其中:- 称为目标函数,表示我们希望最小化的性能指标。
- 和称为约束条件,对决策变量的取值进行限制。
- 决策变量是一个维实数向量,代表我们可以调节的参数。
- 最优解是满足约束条件下目标函数取得最小值时的值。
举个简单的例子,假设我们要制造一种混合果汁,目标是用最少的成本达到最佳的口感。我们可以调节苹果汁、橙汁、芒果汁的比例(即决策变量
),同时要求各种果汁比例非负且和为 1(约束条件),并且希望最小化成本(目标函数)。这就是一个典型的优化问题。8.1.2 优化问题的分类
根据目标函数和约束条件的不同,优化问题可以分为以下几类:
- 线性规划(Linear Programming) 目标函数和约束条件都是决策变量的线性函数,如: 其中是矩阵,和分别是维和维列向量。
- 非线性规划(Nonlinear Programming) 目标函数或约束条件中至少有一个是决策变量的非线性函数,没有其他特殊结构的优化问题。
- 二次规划(Quadratic Programming) 目标函数是决策变量的二次函数,约束条件是线性的,如: 其中是的半正定矩阵。
- 整数规划(Integer Programming) 部分或全部决策变量要求是整数。当决策变量限制为 0-1 整数时,称为 0-1 整数规划。
- 多目标规划(Multi-objective Programming) 有多个目标函数需要同时优化,通常目标之间存在矛盾和冲突。
MATLAB 的优化工具箱提供了丰富的函数来求解以上各类优化问题。不同类型的问题在建模和求解上有不同的特点,需要根据具体问题选择合适的优化算法。 接下来我们将重点介绍几类常见优化问题的 MATLAB 求解方法。限于篇幅,我们只能介绍一些基本用法,更多的算法细节和参数设置还需要大家在实践中去探索。
8.2 线性规划
线性规划(LP)是优化领域历史最悠久、应用最广泛的一类问题。它的特点是目标函数和约束条件都是决策变量的线性函数,整个问题只涉及一次项而没有高次项。许多实际问题如资源分配、生产计划、运输问题等都可以建模为线性规划。
8.2.1 线性规划的基本模型
线性规划的标准形式如下:
其中, 是决策变量, 是约束矩阵, 和 分别是目标函数和约束条件的系数向量。 除标准形式外,线性规划还可以有其他等价的形式,如松弛形式: 以及变量无非负限制的形式: 不同的问题形式,在建模和求解时需要进行适当的转化。8.2.2 线性规划的求解方法
求解线性规划的主要方法是单纯形法(Simplex Method),它是一种迭代搜索的算法,通过不断沿着可行域的边界移动,直到找到最优解。单纯形法的基本步骤如下:
- 将问题转化为标准形式。
- 构造初始可行解,作为第一个单纯形。
- 检查是否满足最优性条件,如果满足则当前解即为最优解,算法终止;否则转 4。
- 确定一个可以改进目标函数的移动方向,得到新的单纯形。
- 回到步骤 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)
等,可以提高求解效率。