keywords: 优化问题,线性规划,非线性规划,非线性方程组,MATLAB 优化工具箱

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

8.1 优化问题概述

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

8.1.1 优化问题的基本概念

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

$ \begin{align} \min \quad & f(x) \ \text{s.t.} \quad & g_i(x) \leq 0, \quad i=1,\ldots,m \ & h_j(x) = 0, \quad j=1,\ldots,p \ & x \in \mathbb{R}^n \end{align} $

其中:

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

举个简单的例子,假设我们要制造一种混合果汁,目标是用最少的成本达到最佳的口感。我们可以调节苹果汁、橙汁、芒果汁的比例(即决策变量 $ x $),同时要求各种果汁比例非负且和为 1(约束条件),并且希望最小化成本(目标函数)。这就是一个典型的优化问题。

8.1.2 优化问题的分类

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

  1. 线性规划(Linear Programming)
    目标函数和约束条件都是决策变量的线性函数,如:
    $ \begin{align} \min \quad & c^T x \ \text{s.t.} \quad & A x \leq b \ & x \geq 0 \end{align} $其中$ A $是$ m \times n $矩阵,$ c $和$ b $分别是$ n $维和$ m $维列向量。
  2. 非线性规划(Nonlinear Programming)
    目标函数或约束条件中至少有一个是决策变量的非线性函数,没有其他特殊结构的优化问题。
  3. 二次规划(Quadratic Programming)
    目标函数是决策变量的二次函数,约束条件是线性的,如:
    $ \begin{align} \min \quad & \frac{1}{2}x^TQx + c^T x \ \text{s.t.} \quad & A x \leq b \ & x \geq 0 \end{align} $其中$ Q $是$ n \times n $的半正定矩阵。
  4. 整数规划(Integer Programming)
    部分或全部决策变量要求是整数。当决策变量限制为 0-1 整数时,称为 0-1 整数规划。
  5. 多目标规划(Multi-objective Programming)
    有多个目标函数需要同时优化,通常目标之间存在矛盾和冲突。

MATLAB 的优化工具箱提供了丰富的函数来求解以上各类优化问题。不同类型的问题在建模和求解上有不同的特点,需要根据具体问题选择合适的优化算法。

接下来我们将重点介绍几类常见优化问题的 MATLAB 求解方法。限于篇幅,我们只能介绍一些基本用法,更多的算法细节和参数设置还需要大家在实践中去探索。

8.2 线性规划

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

8.2.1 线性规划的基本模型

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

$ \begin{align} \min \quad & c^T x \ \text{s.t.} \quad & A x \leq b \ & x \geq 0 \end{align} $

其中,$ x \in \mathbb{R}^n $ 是决策变量,$ A \in \mathbb{R}^{m \times n} $ 是约束矩阵,$ c \in \mathbb{R}^n $ 和 $ b \in \mathbb{R}^m $ 分别是目标函数和约束条件的系数向量。

除标准形式外,线性规划还可以有其他等价的形式,如松弛形式:

$ \begin{align} \min \quad & c^T x \ \text{s.t.} \quad & A x = b \ & x \geq 0 \end{align} $

以及变量无非负限制的形式:

$ \begin{align} \min \quad & c^T x \ \text{s.t.} \quad & A x \leq b \end{align} $

不同的问题形式,在建模和求解时需要进行适当的转化。

8.2.2 线性规划的求解方法

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

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

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

8.2.3 MATLAB 中的线性规划函数

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

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

其中:

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

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

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

下面我们看一个线性规划的简单例子。

例 1 考虑如下的生产计划问题:

$ \begin{align} \max \quad & 2x_1 + 3x_2 \ \text{s.t.} \quad & x_1 + x_2 \leq 8 \ & 2x_1 + x_2 \leq 10 \ & x_1, x_2 \geq 0 \end{align} $

其中,$ x_1 $ 和 $ x_2 $ 分别表示产品 1 和产品 2 的生产数量,目标是使总利润最大化。约束条件反映了生产资源的限制。

利用 MATLAB 求解上述问题的代码如下:

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

输出结果为:

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

可见,在给定约束下,最优生产计划是生产 2 个产品 1 和 6 个产品 2,总利润为 22。

linprog函数功能非常强大,可以处理各种不同形式的线性规划问题。感兴趣的读者可以进一步探索它的用法,并将其应用到实际问题中。

8.3 非线性规划

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

8.3.1 非线性规划的基本模型

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

$ \begin{align} \min \quad & f(x) \ \text{s.t.} \quad & g_i(x) \leq 0, \quad i=1,\ldots,m \ & h_j(x) = 0, \quad j=1,\ldots,p \end{align} $

其中目标函数 $ f(x) $ 和约束函数 $ g_i(x) $, $ h_j(x) $ 是 $ x $ 的非线性函数。与线性规划相比,非线性规划有以下特点:

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

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

  • 非线性最小二乘问题$ \minx | F(x) |_2^2 = \sum{i=1}^m f_i(x)^2 $
  • 二次规划问题$ \min_x \frac{1}{2}x^TQx + c^Tx, \text{ s.t. } Ax \leq b, Aeq \cdot x = beq $

8.3.2 非线性规划的求解方法

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

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

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

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

8.3.3 MATLAB 非线性规划实例

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

$ \begin{align} \min_w \quad & w^T V w \ \text{s.t.} \quad & e^T w = 1 \ & w \geq 0 \end{align} $

其中e为全1向量。这里目标函数是二次的,约束是线性的,因此是一个二次规划问题。

我们用MATLAB求解一个具体例子。假设有3只股票,它们的预期年收益率分别为5%, 7%, 6%,年化收益率的协方差矩阵为:

$ V = \begin{bmatrix} 0.0100 & 0.0018 & 0.0011 \ 0.0018 & 0.0109 & 0.0026 \ 0.0011 & 0.0026 & 0.0199 \end{bmatrix} $

MATLAB实现如下:

  1. r = [0.05; 0.07; 0.06];  % 预期收益率
  2. V = [0.0100 0.0018 0.0011; 
  3.     0.0018 0.0109 0.0026;
  4.     0.0011 0.0026 0.0199];  % 协方差矩阵
  6. H = V;
  7. f = zeros(3,1);
  9. A = ones(1,3);
  10. b = 1;
  11. Aeq = [];
  12. beq = [];
  13. lb = zeros(3,1);
  14. ub = [];
  16. [w,fval] = quadprog(H,f,A,b,Aeq,beq,lb,ub);
  17. fprintf('最优投资组合权重为: \n');
  18. disp(w);
  19. fprintf('最小投资组合方差为: %.4f\n',fval);

运行结果为:

  1. 最优投资组合权重为:
  3.     0.3021
  4.     0.4438
  5.     0.2540
  7. 最小投资组合方差为: 0.0050

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

8.4 非线性方程组

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

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

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

$ \begin{cases} f_1(x_1,\ldots,x_n) = 0 \ \vdots \ f_n(x_1,\ldots,x_n) = 0 \end{cases} $

或者写成向量形式:

$ F(x) = \begin{bmatrix} f_1(x) \ \vdots \ f_n(x) \end{bmatrix} = 0 $

其中 $ x = (x_1,\ldots,x_n)^T $ 是 $ n $ 维未知向量, $ F: \mathbb{R}^n \rightarrow \mathbb{R}^n $ 是非线性向量值函数。

非线性方程组的解不像线性方程组那样有统一的解法,需要根据问题的特点选择适当的数值迭代算法。常用的迭代格式为:

$ x^{(k+1)} = x^{(k)} + \lambda_k p^{(k)} $

其中 $ \lambda_k $ 为步长, $ p^{(k)} $ 为搜索方向。不同的算法在迭代格式中有不同的选择。

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

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

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

这些算法往往需要提供 Jacobi 矩阵的信息,当 $ n $ 很大时计算量很大。

8.4.3 MATLAB 非线性方程组求解

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

fsolve的基本语法为:

  1. x = fsolve(fun,x0)

其中 fun 为计算方程组残差 $ F(x) $ 的函数, x0 为初始迭代点。

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

$ \begin{cases} x^2 - y = 1 \ x^2 + y^2 = 9 \end{cases} $

它对应的向量值函数为:

$ F(x,y) = \begin{bmatrix} x^2 - y - 1\ x^2 + y^2 - 9 \end{bmatrix} $

我们用MATLAB的fsolve函数求解这个方程组。

首先定义向量值函数:

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

然后调用fsolve函数:

  2. x0 = [1; 1];  % 初始点
  3. [x,fval,exitflag] = fsolve(@myfun, x0);
  4. fprintf('方程组的解为:\n');
  5. disp(x);
  7. fprintf('函数值的2-范数为: %e\n',norm(fval));
  8. fprintf('求解终止代码为: %d\n',exitflag);

运行结果为:

  1. 方程组的解为:
  2.     2.0000
  3.     3.0000
  5. 函数值的2-范数为: 2.220446e-16
  6. 求解终止代码为: 1

其中 exitflag 为 1 表示fsolve在函数容差范围内收敛到一个解。可以验证(2,3)确实是原方程组的一个解。

需要注意的是,非线性方程组的解不唯一,迭代算法得到哪个解依赖于初始点的选择。比如将上面代码中的初始点改为:

  1. x0 = [-1; -1];

则得到的解为(-2,3),它也是原方程组的一个解。这启示我们在用数值方法求解非线性问题时,要注意初值的选择对结果的影响。

此外,对于大规模稀疏非线性方程组,MATLAB 还提供了fsolve的稀疏版本fsolve(...,'JacobPattern',S)和预条件版本fsolve(...,'Preconditioner',M)等,可以提高求解效率。