使用GNU Octave GLPK求解含绝对值目标函数的优化问题异常排查

问题背景 #

需要最小化的目标函数（绝对值形式）：

|0.2126R₁ + 0.7152G₁ + 0.0722B₁ - 7(0.2126R₂ + 0.7152G₂ + 0.0722*B₂) - (7-1)*0.05|

约束条件：

0.2126R₁ + 0.7152G₁ + 0.0722B₁ - (0.2126R₂ + 0.7152G₂ + 0.0722B₂) ≥ 0

用户编写的GLPK代码：

ratio = 7;

objective_coefficients  = [ 0.2126,  0.7152,  0.0722, ratio * -0.2126, ratio * -0.7152, ratio * -0.0722, (1 - ratio) * 0.05]';
constraint_coefficients = [ 0.2126,  0.7152,  0.0722,         -0.2126,         -0.7152,         -0.0722];
constraint_right_hand_side_values = [0]';
variable_lower_bounds = [0, 0, 0, 0, 0, 0, 1]';
variable_upper_bounds = [1, 1, 1, 1, 1, 1, 1];
constriant_types = "L";
variable_types = "CCCCCCC";
sense = 1;

parameters.messsage_level = 1;
parameters.iterations_limit = 100;

[xmin, fmin, status, extra] = glpk(objective_coefficients,
                                   constraint_coefficients,
                                   constraint_right_hand_side_values,
                                   variable_lower_bounds,
                                   variable_upper_bounds,
                                   constriant_types,
                                   variable_types,
                                   sense,
                                   parameters);

运行后得到xmin全为1，需排查解决。

核心问题排查 #

1. 绝对值目标函数建模错误 #

GLPK仅支持线性目标函数，无法直接求解带绝对值的目标。你直接将绝对值展开为线性表达式的做法完全错误——绝对值|X|必须通过引入辅助变量+添加两个线性约束的方式线性化，不能当作普通线性项处理。

2. 目标函数系数逻辑错误 #

当前objective_coefficients的最后一项(1-ratio)*0.05，是把绝对值内的常数项直接加到线性目标中，完全违背绝对值的求解逻辑，导致求解器被错误引导，最终得到全1的极端解。

3. 约束类型方向错误 #

约束条件要求A - B ≥ 0，但你设置constriant_types = "L"（表示≤），与实际需求的≥完全相反，导致求解器满足错误的约束条件，输出不合理结果。

4. 冗余变量干扰求解 #

你引入的第7个变量被固定为1（上下界均为1），既不是绝对值线性化所需的辅助变量，也无对应数学意义，属于冗余变量，干扰求解过程。

修正后的代码示例 #

ratio = 7;
constant_term = (ratio - 1)*0.05; % 对应(7-1)*0.05=0.3

% 变量：R1, G1, B1, R2, G2, B2, t（辅助变量，用于绝对值线性化）
num_vars = 7;

% 目标函数：最小化辅助变量t，仅t的系数为1，其余为0
objective_coefficients = zeros(num_vars, 1);
objective_coefficients(7) = 1;

% 约束矩阵：3个约束（原约束+绝对值拆分为两个约束）
% 约束1: A - B >= 0 → 转换为 -A + B <= 0
constraint1 = [0.2126, 0.7152, 0.0722, -0.2126, -0.7152, -0.0722, 0];
% 约束2: A - ratio*B - constant_term <= t → A - ratio*B - t <= constant_term
constraint2 = [0.2126, 0.7152, 0.0722, -ratio*0.2126, -ratio*0.7152, -ratio*0.0722, -1];
% 约束3: -(A - ratio*B - constant_term) <= t → -A + ratio*B - t <= -constant_term
constraint3 = [-0.2126, -0.7152, -0.0722, ratio*0.2126, ratio*0.7152, ratio*0.0722, -1];
constraint_coefficients = [constraint1; constraint2; constraint3];

% 约束右侧值
constraint_right_hand_side_values = [0; constant_term; -constant_term];
% 约束类型：均为<=，用"L"
constraint_types = "LLL";

% 变量上下界：R1-R2/G1-G2/B1-B2在0-1之间，t≥0无上限
variable_lower_bounds = [0, 0, 0, 0, 0, 0, 0]';
variable_upper_bounds = [1, 1, 1, 1, 1, 1, Inf]';
% 变量类型：全为连续变量
variable_types = "CCCCCCC";
% 最小化目标，sense=1
sense = 1;

parameters.message_level = 1; % 修正原代码拼写错误：messsage → message
parameters.iterations_limit = 100;

[xmin, fmin, status, extra] = glpk(objective_coefficients,
                                   constraint_coefficients,
                                   constraint_right_hand_side_values,
                                   variable_lower_bounds,
                                   variable_upper_bounds,
                                   constraint_types,
                                   variable_types,
                                   sense,
                                   parameters);

额外注意点 #

• 修正了原代码中messsage_level的拼写错误，确保参数正常生效。
• 辅助变量t的上界设为Inf，保证求解器可自由调整其值以最小化绝对值。
• 所有约束的类型和方向必须严格匹配数学定义，避免符号错误。

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