主题
非线性规划
方法速览
- 主要用途 求解目标或约束含非线性的连续决策问题。
- 必要输入 变量及定义域、非线性目标和约束、参数及其有效范围。
- 适用条件 非线性有业务或机理依据,且能在决策范围内可靠求值。
- 典型不适用情况 不可拆分的配置是关键决策,却只用连续变量描述。
- 最低限度的验证方式 代回约束并复算目标。非凸问题至少比较多个代表性初值。
哪类决策含有真实非线性
当决策可以连续调整,而能耗、损失或产出随决策幅度变化,就需要考虑非线性规划。例子包括能耗随负载加速增加,或某项约束同时含两个变量的乘积。先问非线性从哪里来、有效范围是什么,以及是否能可靠估计相应参数。业务规则中的离散选择仍应另外表达,连续非线性求解器直接给出的分数台设备往往无法执行。
数学形式与凸性的作用
一种连续最小化形式为
如果目标
分配负载的假设算例
设两台设备的负载
如何与线性方法取舍
单位代价在实际范围内接近常数时,可比较线性规划,便于解释约束何时起作用。目标是二次函数且约束是线性的,可优先识别为二次规划。复杂函数可以分段线性近似,但要验证结论是否受分段精度影响。若函数来自黑盒模拟且不光滑,梯度方法可能难以工作,需要另选方法并报告计算和解质量。
最常见的求解误差
忽略变量的定义域会出现对负数取对数或把分母推向零。不同量纲的变量差上若干数量级,也可能使求解器对较小量不敏感。起点不可行时须看求解方法是否支持。为了得到答案私自放松约束,会把问题改成另一种运营规则。目标很小而约束违背明显时,先处理可行性。
第一次应用怎么验证
写一组手工可行点,检验目标与约束在典型值、边界值的输出。用小规模解析、网格或线性近似作对照。复算候选解的目标、所有关键约束和边界。若使用自编梯度,可在内部点与有限差分比较。对非凸模型试几个有代表性的初值并记录解的差异。改变关键参数做敏感性分析,核对决策是否在合理范围内。
双语言实验
同一个目标,为什么走到了两个谷底
考虑一项可正可负的调节量
一阶近似
两次实验分别从
独立运行
Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_nonlinear.py。MATLAB 将 mmf_nonlinear.m 放入当前文件夹,在命令窗口运行 result = mmf_nonlinear(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。
对凸二次函数执行投影梯度下降。无约束最优点在 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 两个分量均应小于 critical_x 给出驻点全集,global_x 应为其最左侧一项。比较小数结果时用容差。
用有界一维求解器复核两个极小值
将问题拆成 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,保留两个起点与步长。左右终点应分别接近 global_x 只输出目标最小的一项,若问题要求报告全部最优解,需要在容差内保留所有并列驻点。再将原偏置恢复为