MATLAB与scipy中linprog求解绝对误差最小化问题方法

我有如下形式的绝对误差损失函数：

该函数用于将位于曲线f上的数据集点缩放至目标曲线g。
需要最小化的目标函数及对应约束如下：

min: sum_i u_i
s.t.
f_i * a - u_i <= g_i
-f_i * a - u_i <= -g_i

上述约束本质等价于 |f_i * a - g_i| <= u_i，最小化sum(u_i)就是最小化所有点缩放后和目标值的绝对误差之和，其中u_i为每个点的绝对误差上界，a为待求的缩放系数。

以下分别给出MATLABlinprog模块、Scipy库linprog函数的正确配置与求解实现。

MATLAB的linprog求解标准形式为：

min $c^T x$
s.t. $A x \leq b$
支持可选等式约束、变量上下界约束

本次问题的决策变量x长度为n+1：第1个元素是待求缩放系数a，后面n个元素是每个点对应的误差上界u_i（n为曲线f的样本点数量），参数配置逻辑如下：

• 目标函数系数c：a对应的系数为0，每个u_i对应的系数为1（匹配最小化所有u_i之和的目标）
• 不等式约束矩阵A和右端项b：每个样本点对应2行约束，总共2n行
  • 第一类约束f_i*a - u_i <= g_i：对应行第1位填f_i，第i+1位填-1，其余位置填0，右端项填g_i
  • 第二类约束-f_i*a - u_i <= -g_i：对应行第1位填-f_i，第i+1位填-1，其余位置填0，右端项填-g_i
• 变量上下界：u_i为绝对误差上界，需满足u_i >= 0；a无上下界限制。

完整可运行代码：

% 输入曲线数据
scale =  1.5;
x1 = [0,4,6,10,15,20]*scale;
y1 =  [18,17.5,13,12,8,10];
x2 = [0,10.5,28]*scale;
y2= [18.2,10.6,10.3];

% 插值得到目标曲线在x1点位的取值，y1为待缩放曲线f
f = y1;
g = interp1(x2,y2,x1);
n = length(f);

% 配置linprog参数
% 决策变量顺序：[a, u1, u2, ..., un]
c = [0, ones(1, n)]; 
A = zeros(2*n, n+1);
b = zeros(2*n, 1);
lb = [-inf, zeros(1, n)]; % a无下界，u_i>=0
ub = []; % 无上界约束

for i = 1:n
    % 第一类约束：f_i*a - u_i <= g_i
    A(2*i-1, 1) = f(i);
    A(2*i-1, i+1) = -1;
    b(2*i-1) = g(i);
    % 第二类约束：-f_i*a - u_i <= -g_i
    A(2*i, 1) = -f(i);
    A(2*i, i+1) = -1;
    b(2*i) = -g(i);
end

% 求解线性规划
opts = optimoptions('linprog','Display','iter');
[x_opt, fval] = linprog(c, A, b, [], [], lb, ub, opts);

% 提取结果
a_opt = x_opt(1);
u_opt = x_opt(2:end);
fprintf('最优缩放系数a = %.4f，最小绝对误差和 = %.4f\n', a_opt, fval);

Scipy的scipy.optimize.linprog求解标准形式和MATLAB基本一致，高版本默认使用highs求解器，计算效率更高，参数配置逻辑和MATLAB版本完全对齐。
完整可运行代码：

import numpy as np
from scipy.optimize import linprog
from scipy.interpolate import interp1d

# 输入曲线数据
scale = 1.5
x1 = np.array([0,4,6,10,15,20]) * scale
y1 = np.array([18,17.5,13,12,8,10])
x2 = np.array([0,10.5,28]) * scale
y2 = np.array([18.2,10.6,10.3])

# 线性插值得到目标曲线在x1点位的取值
g_interp = interp1d(x2, y2, kind='linear')
f = y1
g = g_interp(x1)
n = len(f)

# 配置linprog参数
# 决策变量顺序：[a, u1, u2, ..., un]
c = np.zeros(n+1)
c[1:] = 1 # 目标函数为sum(u_i)
A_ub = np.zeros((2*n, n+1))
b_ub = np.zeros(2*n)
bounds = [ (None, None) ] # a无上下界
for i in range(n):
    bounds.append( (0, None) ) # u_i >=0
    # 第一类约束
    A_ub[2*i, 0] = f[i]
    A_ub[2*i, i+1] = -1
    b_ub[2*i] = g[i]
    # 第二类约束
    A_ub[2*i+1, 0] = -f[i]
    A_ub[2*i+1, i+1] = -1
    b_ub[2*i+1] = -g[i]

# 求解
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

# 提取结果
a_opt = res.x[0]
fval = res.fun
print(f'最优缩放系数a = {a_opt:.4f}，最小绝对误差和 = {fval:.4f}')

两段代码运行结果完全一致。 #

• 不要遗漏u_i >=0的约束，否则求解会触发无界错误，无法得到有效结果
• 决策变量的顺序要和约束矩阵、目标函数系数的位置严格对应，避免索引错位
• 如果后续需要加入偏移项（即拟合形式为a*f_i + c），只需要在决策变量中新增偏移参数，对应修改约束矩阵即可，整体建模逻辑不变。

内容的提问来源于stack exchange，提问作者Natasha