建模技术

第一章

建模

定义：模型是对客观事物抽象出来的原型的替代物。

常见模型：实物模型、物理模型、符号模型（图表）。

数学建模：实际问题转化为数学问题。

 

数学建模的基本方法和步骤

基本方法

• 机理分析：对客观事物特性的认识====>内部机理的数量规律（白箱）
• 测试分析：对量测数据的统计分析====>与数据拟合最好的模型（黑箱）

二者结合：机理分析建立模型结构，测试分析确定模型参数。

（建模主要指机理分析）

 

数学模型和数学建模

第一性原理：看透事物本质的根本方法。

数学建模的一般步骤

• 模型准备：形成清晰的问题。
• 模型假设：合理的，简化的。
• 模型构成：采用简单的数学工具。
• 模型求解
• 模型分析：误差，统计等。
• 模型检验：与实际现象，数据比较。
• 模型应用

数学建模的全过程

实践到理论再到实践。

特点：逼真性，条理性，可行性，渐进性，强健性，局限性，可转移性，非预制性。

 

优化建模

最小作用量原理：物理系统在从一个状态演化到另一个状态的过程中，会选择使作用量取得极值（通常是局部最小值）的路径。

 例如，费马原理：光在传播过程中，无论是直线传播、反射还是折射，都遵循时间最短或路径最短的原理。

 

最优化问题的一般形式及分类

一般数学形式： min_x ∈ Xf(x) 其中，f(x)是目标函数，x是决策变量，X是约束集合或可行域，构成优化问题的三要素。

可行域包含的点x ∈ X是可行解或可行点。 $$ \left\{ \begin{aligned} & \min && f(x) \\& \text{s.t.} && g_i(x) \leq 0, \; i = 1, \cdots, p \\& && h_j(x) = 0, \; j = 1, \cdots, q \end{aligned} \right. $$ 其中，x = (x₁, x₂, ⋯, x_n)^T，f(x)、g_i(x)、h_j(x) 为 x 的实值函数。

引入向量函数符号$g(x) = ( g_1(x), , g_p(x) )^T 和 h(x) = ( h_1(x), , h_q(x) )^T$后： $$ \left\{ \begin{array}{ll} \min & f(x) \\ \text{s.t.} & g(x) \leq 0 \\ & h(x) = 0 \end{array} \right. $$  

定义：

• 对于最优化问题，若有x^* ∈ X，并且有：

f(x^*) ≤ f(x), ∀x ∈ X

则称x^*是最优化问题的整体最优解，f(x^*)是整体最优值。

如果只有<则为严格最优解。

 

• 对于最优化问题，若有x^* ∈ X，并且存在x^*的邻域N_δ(x^*) = {x ∈ Rⁿ且||x − x^*|| < δ}使得：

f(x^*) ≤ f(x), ∀x ∈ N_δ(x^*) ∩ X

则称x^*是最优化问题的局部最优解，f(x^*)是局部最优值。

如果只有<则为严格局部最优解。

 

分类：

• 若f(x)，g_i(x)，h_j(x)皆为线性函数，即为线性规划（LP）；至少一个非线性，则为非线性规划（NLP）。
• 若没有g_i(x)，h_j(x)，即X = ℝⁿ，则为无约束最优化问题。
• 若f(x)，g_i(x)，h_j(x)皆为光滑函数，则为光滑优化，反之则为非光滑优化。

最优化问题的分类

一个优化问题可能属于多个类别。

 

机器学习问题

标准流程

• 数据：模拟学习问题的输入和输出
• 模型：备选预测函数集合
• 算法-表现度量：指导优化的目标函数
• 算法-优化算法：计算优化问题最优解

没有免费的午餐原理：该定理表明，在所有可能的问题中，平均而言，任何算法的性能都是相同的。（有得必有失，守恒，平衡）

奥卡姆剃刀原理：如无必要，勿增实体。

 

组合优化问题

定义：这类问题广泛存在于现实生活的各个领域，如物流、 金融、计算机科学、生物信息学等。它关注于在给定 的约束条件下，从一组可能的解中找出最优解。

1、旅行商问题(TSP)

在物流规划、电路板布线、生物学和交通规划等领域有重要应用。

随着城市数量的增加，问题的求解难度呈指数增长。

常用穷举法，动态规划，贪心，遗传等启发式算法。

2、背包问题

在商业、组合数学、计算复杂性理论、密码学和应用数学等领域。

常用动态规划、分支限界法、遗传算法等。

3、指派问题

一类特殊的线性规划问题，它要求将n项任务分配给n个人去完 成，每个人只能完成一项任务，且每项任务只能由一个人完成。目标是找 到一种分配方案，使得总成本（或总时间、总资源消耗等）最小。

在企业管理、资源分配、任务调度等领域有重要应用。

常用匈牙利算法等有效算法求解。

 

还有调度问题、切割问题、装箱问题等等…

 

 

第二章 连续最优化建模与应用

非线性规划基础

梯度∇f(x)

定义：f(x)的n个偏导数为分量的向量。 $$ \nabla f(x) = \left[ \frac{\partial f(x)}{\partial x_1}, \frac{\partial f(x)}{\partial x_2}, \cdots, \frac{\partial f(x)}{\partial x_n} \right]^T $$

 − ∇f(x)则为梯度下降方向，一般用于最优化问题，即梯度下降法。

常用的梯度公式：

• f(x)为常数，则∇f(x)=0；
• f(x) = b^Tx，则∇f(x) = b；
• f(x) = x，则∇f(x) = I（单位阵）；
• f(x) = x^Tx，则∇f(x) = 2x；
• A为对称矩阵，f(x) = x^TAx，则∇f(x) = 2Ax

 

n元二次函数

一般形式：$f(x_1, x_2, \cdots, x_n) = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_i x_j + \sum_{i=1}^n b_i x_i + c$

加上$\frac{1}{2}$是x_ix_j和x_jx_i重复计算。

矩阵形式：$f(x) = \frac{1}{2} x^T A x + b^T x + c$，其中A = A^T

A是一个对称矩阵。

二次型：$f(x) = \frac{1}{2} x^T A x$

只保留了二次项

矩阵正定性：正定、半正定、负定、不定。

 

Hessian矩阵

定义：多元函数f(x)关于x的二阶导数。 $$ \nabla^2 f(x) = \nabla(\nabla f(x)) = \begin{bmatrix} \dfrac{\partial^2 f(x)}{\partial x_1^2} & \dfrac{\partial^2 f(x)}{\partial x_2 \partial x_1} & \cdots & \dfrac{\partial^2 f(x)}{\partial x_n \partial x_1} \\ \dfrac{\partial^2 f(x)}{\partial x_1 \partial x_2} & \dfrac{\partial^2 f(x)}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f(x)}{\partial x_n \partial x_2} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac{\partial^2 f(x)}{\partial x_1 \partial x_n} & \dfrac{\partial^2 f(x)}{\partial x_2 \partial x_n} & \cdots & \dfrac{\partial^2 f(x)}{\partial x_n^2} \end{bmatrix} $$

当f(x)的所有二阶偏导数连续时，即$\dfrac{\partial^2 f(x)}{\partial x_i \partial x_j}=\dfrac{\partial^2 f(x)}{\partial x_j \partial x_i}$时，Hessian矩阵是对称的。

 

Jacobi矩阵

定义：g(x)是一个向量值函数，Jacobi矩阵即为g(x)在x₀处的导数。 $$ \nabla g(x_0) = \begin{bmatrix} \dfrac{\partial g_1(x_0)}{\partial x_1} & \dfrac{\partial g_1(x_0)}{\partial x_2} & \cdots & \dfrac{\partial g_1(x_0)}{\partial x_n} \\ \dfrac{\partial g_2(x_0)}{\partial x_1} & \dfrac{\partial g_2(x_0)}{\partial x_2} & \cdots & \dfrac{\partial g_2(x_0)}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac{\partial g_m(x_0)}{\partial x_1} & \dfrac{\partial g_m(x_0)}{\partial x_2} & \cdots & \dfrac{\partial g_m(x_0)}{\partial x_n} \end{bmatrix} $$  

Taylor展开

定义：f(x)是连续可微的，p是向量，那么 f(x + p) = f(x) + ∇f(x + tp)^Tp,  其中 0 < t < 1

二阶连续可微，即可进一步$f(x + p) = f(x) + \nabla f(x)^T p + \frac{1}{2} p^T \nabla^2 f(x + tp) p$

 

无约束可约最优化问题

最优性条件

$$ \begin{aligned} & \min && f(x) \\ & \text{s.t.} && x \in \mathbb{R}^n \end{aligned} $$

定理（必要条件）：设f在点x^* ∈ Rⁿ处可微，若x^*是minf(x)的局部最优解，则∇f(x^*) = 0。

梯度为0的点称为函数的驻点，定理说明：这个点一定是驻点，但仅仅是一阶必要条件。

驻点可能是极小/极大，可能都不是，即为鞍点。

定理（二阶充分必要条件）：设f在点x^* ∈ Rⁿ处的Hessian矩阵∇²f(x^*)存在，

• 必要条件：若x^*是f的一个局部极小点，==>∇f(x^*) = 0，那么∇²f(x^*) ≽ 0半正定；
• 充分条件：若∇f(x^*) = 0，∇²f(x^*) ≻ 0正定，那么x^*是minf(x)的严格局部最优解。

设点x^*满足一阶最优性条件，且该点处的Hessian矩阵不是半正定的，则x^*不是一个局部极小点。

事实上，该点是一个鞍点。

 

最小二乘法

损失函数： $$ J_l(\theta) = \frac{1}{2} \sum_{i=1}^n \left( h_\theta(x^{(i)}) - y^{(i)} \right)^2 $$ 应用：曲线拟合、图像配准、信号去噪。

 

线搜索算法

流程

x^k + 1 = x^k + Δx^k

Δx^k = λ_kd^k

d^k为第k轮搜索方向，λ_k为第k轮步长。

 

下降方向（特殊搜索方向）

定义：若存在δ > 0，d ∈ Rⁿ，d ≠ 0，使得f(x + td) < f(x)，∀t ∈ (0, δ)，则称向量d是函数f(x)在点x处下降方向。

若f(x)在x可导，则 − ∇f(x)就是f(x)在x处下降最快的方向。

 

最优步长： f(x^k + λ_kd^k) = min_λ ≥ 0f(x^k + λd^k)

λ_k即为最优步长。

步骤：

• 给出初始点x⁰，令k = 0；
• 按照某种规则，确定d^k；
• 按照某种规则，确定λ_k，使得f(x^k + λ_kd^k) < f(x^k)；
• 令x^k + 1 = x^k + λ_kd^k，k := k + 1；
• 判断x^k是否满足停止条件，是则停止，否则转第2步。

 

算法收敛

定义：算法按d^k和λ_k产生的迭代点列x^k + 1 = x^k + λ_kd^k，如果点列{x^k}收敛于最优解x^*，则称该算法收敛。

如果进一步有$f(x^0)>f(x1)> >f(x^k)> $，则称该算法为下降迭代算法。

常用的收敛性判断条件：

• ∥x^k + 1 − x^k∥ < ε₁
• |f(x^k + 1) − f(x^k)| < ε₂

收敛速度： $$ \frac{\|x^{k+1} - x^*\|}{\|x^k - x^*\|^\alpha} < \lambda, \quad \lambda, \alpha > 0 $$ 则称x^k的收敛阶为α。

α = 1，线性收敛（k充分大）。

1 < α < 2，超线性收敛。

α = 2，二阶收敛。

 

常用最优化算法

梯度法（最速下降法）

定理：

设f(x)在点x̄处可微，若存在d ∈ Rⁿ，使得 ∇f(x̄)^Td < 0 则称向量d是f在点x̄处的下降方向。

 − ∇f是下降速度最快的方向，称为最速下降方向。

函数在某点的梯度不为0，则该梯度方向必定与过该点的等值面垂直。

方向：d^k =  − ∇f(x^k)

步长：

• 可直接选取固定的λ_k；
• 或者最优步长；
• 也可以依赖线搜索算法。

思路：

• 给定初始点x^k ∈ Rⁿ，允许误差ε > 0，置k = 1；
• 计算搜索方向d^k =  − ∇f(x^k)；
• 若∥d^k∥ ≤ ε停止，否则，从x^k出发，沿d^k进行一维搜索求λ_k，找到最优步长；
• 令x^k + 1 = x^k + λ_kd^k，置k := k + 1，转第二步。

特点：线性收敛，容易产生扭摆现象造成早停，当x^k距离最优点x^*较远时，速度快；而接近最优点时，速度下降。

 

牛顿法

定理：

为了由x^k产生x^k + 1，在x^k附近用二次函数Q(x)近似f(x)，用Q(x)的极小点作为x^k + 1。 $$ f(x) \approx Q(x) = f(x^k) + \nabla f(x^k)^T (x - x^k) + \frac{1}{2}(x - x^k)^T \nabla^2 f(x^k)(x - x^k) $$

点x^k处的泰勒展开。

$$ Q(x) = f(x^k) + g_k^T \cdot (x - x^k) + \frac{1}{2}(x - x^k)^T G_k (x - x^k) $$

其中 g_k = ∇f(x^k), G_k = ∇²f(x^k)

即∇Q(x) = g_k + G_k(x − x^k) = 0，若G_k正定，即G_k ≻ 0，则有x^k + 1 = x^k − G_k^− 1g_k，即为牛顿迭代公式。

即d^k =  − G_k^− 1g_k，λ_k = 1。

特点：

• 收敛速度快，为二阶局部收敛。（需要二阶正定）
• 初始点最好选在最优点附近，一般先用最速下降法得到较低精度的解，再用牛顿法加速。

拟牛顿法

用正定矩阵H_k代替G_k^− 1，则有： x^k + 1 = x^k − λ_kH_k∇f(x^k)

当H_k = I时，x^k + 1 = x^k − λ_k∇f(x^k)，最速下降法。

当H_k = G_k^− 1，λ_k = 1时，牛顿法。

拟牛顿条件： H_k + 1Δg_k = Δx^k

g_k为对f(x)在x^k的梯度。

步长可用最优步长。

优点：

• 只需用到函数的一阶梯度
• 下降算法，全局收敛
• 不需要求逆矩阵（计算量小）
• 一般可达超线性收敛（速度快）

衍生：

• DFP算法：

$$ H_{k+1} = H_k + \frac{\Delta x_k^T \Delta x_k}{\Delta x_k^T \Delta g_k} - \frac{H_k \Delta g_k \Delta g_k^T H_k}{\Delta g_k^T H_k \Delta g_k} $$ - BFGS算法：

 

步长线搜索算法

精确线搜索算法：λ_k为最优步长。

非精确线搜索：依照线搜索准则。

• Armijo准则
• Goldstein准则
• Wolfe准则

线搜索回退法

 

约束非线性最优化

最优性条件

$$ \left\{ \begin{array}{ll} \min & f(x) \\ \text{s.t.} & g(x) \geq 0 \\ & h(x) = 0 \end{array} \right. $$

KKT必要条件

构造拉格朗日函数： $$ L(x, \mu, \lambda) = f(x) - \sum_{j=1}^{m} \mu_j h_j(x) - \sum_{j=1}^{l} \lambda_j g_j(x) \\ = f(x) - \mu^T h(x) - \lambda^T g(x) $$

μ和λ即为拉格朗日乘子

则KKT条件可以表示为： $$ \nabla f(x^*) = \lambda^T \nabla g(x^*) + \mu^T \nabla h(x^*) \quad \text{稳定性条件} \\ h(x^*) = 0 \quad\text{原问题可行性} \\ g(x^*) \geq 0 \quad\text{原问题可行性} \\ \lambda \geq 0 \quad\text{对偶可行性} \\ \lambda^T g(x^*) = 0 \quad\text{互补松弛条件} $$

KKT充分条件

定理：设f为凸函数，g_i为凹函数，h_j为线性函数。对于$𝑥^*\in𝑆$，若f，g_i，h_j在点x^*处可微，并且KKT条件成立，则x^*为优化问题的全局极小点。

惩罚函数法

思想：迭代过程中，罚函数法通过对不可行点施加惩罚，迫使迭代点向可行域靠近。一旦迭代点成为可行点，则这个可行点就是原问题的最优解。根据不同的罚函数有不同的罚方法。

也成为序列无约束极小化方法，将有约束优化转换为一系列无约束优化问题进行求解。

外点法（外惩法）

对于有约束原问题： $$ \min f(x) \\ \text{s.t.} \quad g_i(x) \leq 0, \quad i = 1, \cdots, m $$ 转换为： $$ \min f(x) \\ \text{s.t.} \quad x \in D $$

其中D = {x ∣ g(x) ≤ 0}

构造一个φ_k(x)，使得 φ_k(x) = f(x) + λ_kp(x) 其中λ₁ < λ₂ < ⋯ < λ_k( ↑ ) →  + ∞，并且

• p(x) = 0，当x ∈ D时；
• p(x) > 0，当x ∉ D时。

其中φ_k(x)：增广函数；p(x)：惩罚函数；λ_k：惩罚因子。

定理：

当φ_k(x)有最优解x^*,并且x^*(λ_k) ∈ D，即则x^*(λ_k)也是原问题𝑓(𝑥) 的最优解。

一般构造：

$p(x) = \sum_{j=1}^{m} \left( \max\{g_j(x), 0\} \right)^2 + \sum_{k=1}^{p} \left( h_k(x) \right)^2$

x^k + 1 = arg min_{x ∈ ℝⁿ}φ_k(x)

内点法（内惩法）

使得迭代点是在可行域点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，阻碍迭代点穿越边界。

等式约束不适用。

此时 $$ \begin{aligned} D &= \{x \mid g_i(x) \leq 0,\ i = 1, \dots, m\} \\ &= \partial D \cup \operatorname{int} D = \text{边界点集} \cup \text{内点集} \end{aligned} $$ 构造一个φ_k(x)，使得 φ_k(x) = f(x) + μ_kq(x) 一般构造：

$q(x) = \sum_{j=1}^{m} -\frac{1}{g_j(x)} \text{或}q(x) = \sum_{j=1}^{m} \frac{1}{g_j^2(x)};$

x^k + 1 = arg min_{x ∈ ℝⁿ}φ_k(x)

增广拉格朗日乘子法

考虑等式约束问题： $$ \begin{aligned} &\min f(x) \\ &\text{s.t. } h(x) = 0 \end{aligned} $$ 构造增广拉格朗日函数： $$ \varphi(x, v, \mu) = f(x) + \sum_{i=1}^{l} v_i h_i(x) + \frac{1}{2} \sum_{i=1}^{l} \sigma_i h_i^2(x) $$

其中，v为乘子；σ为惩罚因子。

思路：

• 求解min φ(x,v^(k),σ^(k))，得到x^k，k = 0, 1, 2, ...；
• 若h(x^k) = 0，得到x^k以及乘子v^k；
• 否则调整v^(k)。

v^(k)的更新：v_j^(k + 1) = v_j^(k) + σh_j(x^k), j = 1, 2, ..., l

不需要更新σ

 

 

第三章 线性规划

线性规划及其概念

$$ \left\{ \begin{aligned} & \min && f(x) \\& \text{s.t.} && g_i(x) \leq 0, \; i = 1, \cdots, p \\& && h_j(x) = 0, \; j = 1, \cdots, q \end{aligned} \right. $$

若f(x)，g_i(x)，h_j(x)皆为线性函数，即为线性规划（LP）。

LP模型的标准型 $$ \begin{aligned} &\max \quad Z = c^{\mathrm{T}}x \\ &\text{s.t.} \quad \begin{cases} Ax = b \\ x \geq 0 \end{cases} \end{aligned} $$

目标函数最大，约束条件等式，决策变量x非负，资源限量b非负。

如果x_j为自由变量，可令x_j = x_j⁺ − x_j⁻，两个分量都非负即可。

不等式变等式引进松弛变量和剩余变量，例如Ax <  = b转换Ax + si = b（松弛变量）；Ax >  = b转换Ax − si = b（剩余变量）。

定理1：若LP存在可行域，则一定为凸集。

凸集：设K是n维欧式空间的一个点集，x¹ ∈ K，x² ∈ K，x¹ ≠ x²，K中这两点连线上的所有点x = αx¹ + (1 − α)x² ∈ K, (0 < α < 1)，则称K为凸集。

定理2：若LP的可行域非空且有界，则必定有最优解。

定理3：若LP有最优解，则最优解一定可以在其可行域的某个顶点上取得。

定理4：LP问题可行域的顶点与其基本可行解一一对应。

设m个线性无关列是A前m列，B = (P₁, P₂, ..., P_m)，则P_j为基向量，与其对应的变量x_j则为基变量。

例如： $$ \begin{aligned} \left\{ \begin{array}{l} x_1 + 2x_2 \leq 8 \\ x_2 \leq 2 \\ x_1, x_2 \geq 0 \end{array} \right. \quad \Rightarrow \quad \left\{ \begin{array}{l} x_1 + 2x_2 + x_3 = 8 \\ x_2 + x_4 = 2 \\ x_1, x_2, x_3, x_4 \geq 0 \end{array} \right. \end{aligned} $$ 则 $$ A = \begin{pmatrix} 1 & 2 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix} = (P_1, P_2, P_3, P_4) $$

$$ b=\begin{pmatrix} 8\\ 2 \end{pmatrix} $$

就有 $$ B_1=(P_1,P_2)=\begin{pmatrix} 1&2\\ 0&1 \end{pmatrix}, B_2=(P_1,P_4)=\begin{pmatrix} 1&0\\ 0&1 \end{pmatrix},同理B_3-B_5 $$

没有(P₁, P₃)因为P₁ = P₃，所以B的个数 ≤ C_n^m，n为变量个数，m为等式个数。

Ax = b的所有解为： $$ x = \begin{bmatrix} x_B \\ x_N \end{bmatrix} = \begin{bmatrix} B^{-1}b - B^{-1}Nx_N \\ x_N \end{bmatrix} $$ 令所有非基变量x_N = 0，得到一个特解$x=\begin{bmatrix}B^{-1}b\\0\end{bmatrix}$称为基本解。基变量x_B = B^− 1b。

有一个B就有一个基本解，个数也 ≤ C_n^m，但基本解不一定可行，只有x_B = B^− 1b ≥ 0时，基本解为基本可行解，此时B为可行基；只是 > 0称为非退化的可行解。

 

单纯形法

 

线性规划模型应用