Skip to content

非线性规划 ​

方法速览 ​

  • 主要用途 求解目标或约束含非线性的连续决策问题。
  • 必要输入 变量及定义域、非线性目标和约束、参数及其有效范围。
  • 适用条件 非线性有业务或机理依据,且能在决策范围内可靠求值。
  • 典型不适用情况 不可拆分的配置是关键决策,却只用连续变量描述。
  • 最低限度的验证方式 代回约束并复算目标。非凸问题至少比较多个代表性初值。

哪类决策含有真实非线性 ​

当决策可以连续调整,而能耗、损失或产出随决策幅度变化,就需要考虑非线性规划。例子包括能耗随负载加速增加,或某项约束同时含两个变量的乘积。先问非线性从哪里来、有效范围是什么,以及是否能可靠估计相应参数。业务规则中的离散选择仍应另外表达,连续非线性求解器直接给出的分数台设备往往无法执行。

数学形式与凸性的作用 ​

一种连续最小化形式为

minxf(x)s.t.gi(x)≤0,hj(x)=0.

如果目标 f 和各 gi 都是凸函数,等式是仿射的,决策定义在凸域上,便是典型的凸优化。对凸问题,取得的局部最小也全局最小。对非凸问题,起点不同可能得到不同可行解。即使求解器报告已收敛,也要分清是满足局部最优条件、步子变小,还是取得全局证明。可导问题常检查约束违背量与最优性残差。Boyd 与 Vandenberghe《Convex Optimization》§4.2

分配负载的假设算例 ​

设两台设备的负载 x,y 均非负,总负载至少为 4。假设损耗为 x2+3y2。若 x+y>4,按相同比例缩小到总量 4 会减少损耗,所以最优点满足 y=4−x。代入得到

f(x)=x2+3(4−x)2,f′(x)=8x−24.

x∈[0,4],驻点为 x=3,对应 y=1、损耗 12。二次系数为正,区间端点损耗分别为 48 和 16,手算可确认这是全局最优。平均分配 (2,2) 同样可行,但损耗为 16。损耗增长较快的设备因此获得较少负载。

如何与线性方法取舍 ​

单位代价在实际范围内接近常数时,可比较线性规划,便于解释约束何时起作用。目标是二次函数且约束是线性的,可优先识别为二次规划。复杂函数可以分段线性近似,但要验证结论是否受分段精度影响。若函数来自黑盒模拟且不光滑,梯度方法可能难以工作,需要另选方法并报告计算和解质量。

最常见的求解误差 ​

忽略变量的定义域会出现对负数取对数或把分母推向零。不同量纲的变量差上若干数量级,也可能使求解器对较小量不敏感。起点不可行时须看求解方法是否支持。为了得到答案私自放松约束,会把问题改成另一种运营规则。目标很小而约束违背明显时,先处理可行性。

第一次应用怎么验证 ​

写一组手工可行点,检验目标与约束在典型值、边界值的输出。用小规模解析、网格或线性近似作对照。复算候选解的目标、所有关键约束和边界。若使用自编梯度,可在内部点与有限差分比较。对非凸模型试几个有代表性的初值并记录解的差异。改变关键参数做敏感性分析,核对决策是否在合理范围内。

双语言实验 ​

同一个目标,为什么走到了两个谷底 ​

考虑一项可正可负的调节量 x。假设设备靠近 x=±1 时损耗较低,线性偏置略微偏向负值。用无量纲模拟目标展示机制,暂时省去其他约束。

f(x)=(x2−1)2+0.2x,f′(x)=4x(x2−1)+0.2,f″(x)=12x2−4.

一阶近似 f(x+Δ)≈f(x)+f′(x)Δ。取 Δ=−αf′(x) 且步长 α>0,线性近似中的变化量为 −α[f′(x)]2。因此小步通常沿当前斜坡下降。因为 f″(0)=−4,目标在原点附近有一段向下弯的区域。驻点方程有三个实根,约为 −1.0241,0.0501,0.9740。代入二阶导数,外侧两根是极小值,中间一根是极大值。又因为 |x|→∞ 时 f(x)→+∞,比较全部驻点的函数值就能确定本例的全局最优。

两次实验分别从 −1.6 和 1.6 开始,每次按 xk+1=xk−0.05f′(xk) 更新,共 80 步。图中的前几步展示了两个起点如何进入不同谷底,下面的损耗曲线显示两者收敛后的高度差。右侧终点梯度也接近零,目标值却约为 0.197434,左侧则约为 −0.202440。一般的多变量问题很难列全驻点,要结合凸性、上下界或多起点证据评估最优性。

独立运行 ​

Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_nonlinear.py。MATLAB 将 mmf_nonlinear.m 放入当前文件夹,在命令窗口运行 result = mmf_nonlinear(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。

下载 Python 源码 · 下载 MATLAB 源码

对凸二次函数执行投影梯度下降。无约束最优点在 3,盒约束上限为 2;最后停在上边界,目标值 1。完整实践再处理非凸情况下的多初值。

最简版依赖 Python:无第三方依赖。MATLAB:基础功能,无需额外工具箱。

在源码所在目录运行 python mmf_min_nonlinear.py

py
import json
x = 0.0
rate = 0.25
upper = 2.0
path = [x]
for _ in range(4):
    # 对 (x-3)^2 做梯度步,再投影回可行区间 [0,2]。
    trial = x - rate * 2 * (x - 3)
    x = min(upper, max(0.0, trial))
    path.append(x)
value = (x - 3) ** 2
assert all(0 <= point <= upper for point in path) and x == upper and value == 1
result = {"path": path, "minimum": value}
print("LAB_RESULT " + json.dumps(result, ensure_ascii=False))
下载当前源码

Python 脚本用 ** 逐元素求幂,MATLAB 代码明确使用 .^ 和 .*。两种实现的 end_x 应约为 [-1.024120, 0.973994],end_gradient 两个分量均应小于 10−8。critical_x 给出驻点全集,global_x 应为其最左侧一项。比较小数结果时用容差。

用有界一维求解器复核两个极小值 ​

将问题拆成 [−1.5,0] 和 [0.1,1.5] 两个含有不同谷底的区间。Python 可选装 scipy,MATLAB 基础环境已有 fminbnd,这些函数各给出一个局部极小值;这里能复核两个极小值,因为每段区间已通过驻点分析。 SciPy minimize_scalar · MathWorks fminbnd

python
from scipy.optimize import minimize_scalar

def f(x):
    return (x**2 - 1)**2 + 0.2 * x

for interval in [(-1.5, 0), (0.1, 1.5)]:
    fit = minimize_scalar(f, bounds=interval, method="bounded",
                          options={"xatol": 1e-10})
    assert fit.success, fit.message
    print(fit.x, fit.fun)
matlab
f = @(x) (x.^2 - 1).^2 + 0.2 * x;
opts = optimset('TolX', 1e-10);
[xLeft, fLeft] = fminbnd(f, -1.5, 0, opts);
[xRight, fRight] = fminbnd(f, 0.1, 1.5, opts);
disp([xLeft fLeft; xRight fRight])
参数练习与参考结论

将偏置 tilt 改为 0,保留两个起点与步长。左右终点应分别接近 −1 和 1,目标值均接近 0。此时两个谷底并列全局最优。代码的 global_x 只输出目标最小的一项,若问题要求报告全部最优解,需要在容差内保留所有并列驻点。再将原偏置恢复为 0.2,只改变其中一个初值到 0,该轨迹应进入左侧谷底,因为最初的梯度为 0.2,更新方向向左。

关联文章 ​

MathModel FAQ · 数学建模知识库