2026-08-07-Note

非线性规划与差分方程方法

Ref: assets/2026-08-07/非线性规划.pdf · assets/2026-08-07/差分.pdf

一、非线性规划（NLP）

一般形式与标准式

$$\min z=f(x),\text{s.t.}{h}_j(x)=0(j=1,\dots ,q),g_i(x)\ge 0(i=1,\dots ,p)$$

其中 $x=(x_1,\dots ,x_N{)}^T$；$f$ 为目标函数，$h_j$ 为等式约束，$g_i$ 为不等式约束。标准式约定：$max$ 改 $min(-f)$；$\le$ 约束乘 $-1$ 变成 $\ge$。

分类

类型	特点
无约束 NLP	只有目标函数，无约束
约束 NLP	含等式/不等式约束
二次规划（QP）	目标二次、约束线性
凸规划	目标凸 + 可行域凸 ⟹ 局部最优 = 全局最优
非凸规划	可能多个局部最优，求解更困难

理解

LP 是”顶点上的游戏”——最优解在可行域顶点；NLP 是”山坡上的游戏”——没有顶点可查，只能沿着梯度爬坡/下坡。凸性决定爬到哪算数：凸问题爬到哪都是全局最优，非凸问题爬到的可能是局部陷阱。所以建模第一步永远是问：目标函数和可行域是凸的吗？

无约束问题的解法

• 梯度下降（最速下降）：$x^{(k+1)}=x^{(k)}-{\lambda }_k\nabla f(x^{(k)})$，只利用一阶信息；等高线被拉长（病态 Hessian）时收敛很慢；
• 牛顿法：利用二阶信息（Hessian），收敛快但每步计算量/存储量大；
• 共轭梯度：介于两者之间，适合大规模问题。

约束问题的解法

• 拉格朗日乘子法（等式约束）：$\mathcal{L}=f-{\sum }_j{\lambda }_j{h}_j$，令各偏导为 0；
• KKT 条件：不等式约束的推广（乘子 + 互补松弛条件），是判断”候选点是否最优”的标尺；
• 惩罚函数法：把约束”买进”目标——

$$Q(x;M)=f(x)+M\left[\sum _{i=1}^p{\left(\min (0,g_i(x))\right)}^2+\sum _{j=1}^q{h}_j^2(x)\right]$$

在可行域内 $Q=f$，可行域外 $Q>f$（被惩罚）；取 $M=M_1>0$ 求解无约束问题，若解还不可行则 $M\leftarrow 10M$ 再解，直到约束满足（罚函数法）。

• 求解工具：Python scipy.optimize.minimize（SLSQP / trust-constr）、MATLAB fmincon。

案例

案例 1：容器设计（体积固定，材料费最小）

$$\min f(x)=40x_1{x}_2+20x_1^2,\text{s.t.}{x}_1\cdot 2x_2=12,12x_1{x}_2+2x_1^2\le 68,x\ge 0$$

目标含乘积项（非线性），体积约束是等式——典型的约束 NLP。

案例 2：机场选址：6 个城市（坐标 + 权重）加权欧氏距离和最小：

$$\min f(x,y)=\sum _i{W}_i\sqrt{(x-x_i{)}^2+(y-y_i{)}^2}$$

约束含”避开禁建区”（线性半平面 + 圆形禁区）——目标与约束都是非线性。

案例 3：2022 ICM Problem E（森林碳汇）：

• 生长用 Chapman-Richards 方程 $C_{grow}(i,t)=k_i(1-e^{-b_{i}t}{)}^{c_i}{x}_{i,t}$；
• 采伐收益 $C_{harvest}=\alpha y_{i,t}+\beta (y_{i,t}{)}^{1.5}$；
• 约束：土地面积归一、轮伐周期、折现后经济非负、Shannon 多样性指数区间、采伐量不超过生长量上限（$y\le 0.8C_{grow}$）。

目标函数和约束全是非线性 → 只能上 NLP。

二、差分方程方法（离散动态建模）

为什么需要差分

很多变量天生按离散周期变化：存款按年结息、出口按月统计、人口按年普查。预测未来 = 建立”下一个 = 现在的函数”：

$$y_{t+1}=f(y_t,y_{t-1},\dots )$$

基本概念

• 一阶差分 $\Delta y_t=y_{t+1}-y_t$；高阶差分 ${\Delta }^2{y}_t=y_{t+2}-2y_{t+1}+y_t$；
• 差分方程的阶 = 未知函数下标的最大差数（$y_{t+2}+a{y}_{t+1}+b{y}_t=f(t)$ 是二阶）；
• 线性、齐次/非齐次：$f(t)\equiv 0$ 齐次，否则非齐次。

建模案例

模型	差分方程	结论
Malthus 人口	$P_{n+1}=k{P}_n$	$P_n=k^n{P}_0$；倍增时间 $=\ln 2/\ln k$
Verhulst 逻辑斯蒂	$\Delta P=bP-c{P}^2$	加入”个体竞争”阻滞项，人口有限增长
贷款还款	$L_{n+1}=L_n(1+r/100)-R$	每期固定还款，余额递推
Fibonacci 兔子	$u_{n+2}=u_{n+1}+u_n$	特征根为黄金分割 $\frac{1\pm \sqrt{5}}{2}$
凯恩斯乘数动力学	差分方程组	国民收入、消费、投资的联动
蛛网模型	供给滞后一期	价格产量振荡，收敛性由供需斜率决定
传染病 SEIR	离散仓室方程组	疫情逐日推演、干预评估

求解方法：特征方程法

• 一阶 $y_{t+1}+a{y}_t=0$：设 $y_t={\lambda }^t$，特征方程 $\lambda +a=0$ ⟹ 通解 $y_t=C(-a{)}^t$；
• 二阶 $y_{t+2}+a{y}_{t+1}+b{y}_t=0$：特征方程 ${\lambda }^2+a\lambda +b=0$——
  • 相异实根：$y_t=C_1{\lambda }_1^t+C_2{\lambda }_2^t$；
  • 二重根：$y_t=(C_1+C_{2}t){\lambda }^t$；
  • 共轭复根 $\alpha \pm i\beta$：$y_t=r^t(C_1\cos \omega t+C_2\sin \omega t)$，$r=\sqrt{b}$；
• 非齐次：待定系数法——$f(t)={\rho }^t{P}_m(t)$ 时特解取 ${\rho }^t{Q}_m(t)$，$\rho$ 是单/重特征根时分别再乘 $t$ 或 $t^2$；
• 差分方程组：$C(n+1)=FC(n)$ ⟹ $C(n)=F^{n}C(0)$（矩阵迭代）。

稳定性直觉

差分方程长期行为由特征根的模决定：$|\lambda |<1$ 收敛（衰减），$|\lambda |>1$ 发散（爆炸），共轭复根对应振荡。蛛网模型是否稳定、Malthus 人口是否爆炸，本质都是看特征根。

“四个面向”里的差分

量子计算（Crank-Nicolson 离散薛定谔方程）、AI（RNN/LSTM 的隐藏状态递推、梯度更新本身就是差分）、电力价格（ARIMA）、火箭烧蚀（有限差分 + Stefan 边界）、疫情（SEIQR）——差分是把连续世界搬进计算机的通用语言。