曲线的线性组合以匹配具有整数约束的单条曲线
linear combination of curves to match a single curve with integer constraints
我有一组向量(曲线),我想将其匹配到一条曲线。问题不仅仅是找到最接近匹配单条曲线的一组曲线的线性组合(这可以用最小二乘 Ax = B 来完成)。我需要能够添加约束,例如将拟合中使用的曲线数量限制为特定数量,或者曲线彼此相邻。这些约束可以在混合整数线性规划优化中找到。
我开始使用允许约束的 lsqlin,并且能够将变量限制为 > 0.0,但在添加进一步约束方面我不知所措。有没有办法将整数约束添加到最小二乘法,或者有没有办法用 MILP 解决这个问题?
非常感谢任何正确方向的帮助!
编辑: 根据 ErwinKalvelagen 的建议,我正在尝试使用 CPLEX 及其二次求解器,但直到现在我还没有设法让它工作。我创建了一个最小的 'notworking' 示例,并在下面上传了 data here 和代码。问题是 matlabs LS 求解器 lsqlin
能够求解,但是 CPLEX cplexlsqnonneglin
returns CPLEX 错误 5002:%s 不是凸的 同样的问题。
function [ ] = minWorkingLSexample( )
%MINWORKINGLSEXAMPLE for LS with matlab and CPLEX
%matlab is able to solve the least squares, CPLEX returns error:
% Error using cplexlsqnonneglin
% CPLEX Error 5002: %s is not convex.
%
%
% Error in Backscatter_Transform_excel2_readMut_LINPROG_CPLEX (line 203)
% cplexlsqnonneglin (C,d);
%
load('C_n_d_2.mat')
lb = zeros(size(C,2),1);
options = optimoptions('lsqlin','Algorithm','trust-region-reflective');
[fact2,resnorm,residual,exitflag,output] = ...
lsqlin(C,d,[],[],[],[],lb,[],[],options);
%% CPLEX
ctype = cellstr(repmat('C',1,size(C,2)));
options = cplexoptimset;
options.Display = 'on';
[fact3, resnorm, residual, exitflag, output] = ...
cplexlsqnonneglin (C,d);
end
我可以重现 Cplex 问题。这是一个解决方法。不要求解第一个模型,而是使用非线性程度较低的模型:
第二个模型使用 Cplex 求解得很好。这个问题有点像 tolerance/numeric 问题。对于第二个模型,我们有一个表现更好的 Q 矩阵(对角线)。本质上,我们将一些复杂性从 objective 转移到线性约束中。
您现在应该看到如下内容:
Tried aggregator 1 time.
QP Presolve eliminated 1 rows and 1 columns.
Reduced QP has 401 rows, 443 columns, and 17201 nonzeros.
Reduced QP objective Q matrix has 401 nonzeros.
Presolve time = 0.02 sec. (1.21 ticks)
Parallel mode: using up to 8 threads for barrier.
Number of nonzeros in lower triangle of A*A' = 80200
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec. (3.57 ticks)
Summary statistics for Cholesky factor:
Threads = 8
Rows in Factor = 401
Integer space required = 401
Total non-zeros in factor = 80601
Total FP ops to factor = 21574201
Itn Primal Obj Dual Obj Prim Inf Upper Inf Dual Inf
0 3.3391791e-01 -3.3391791e-01 9.70e+03 0.00e+00 4.20e+04
1 9.6533667e+02 -3.0509942e+03 1.21e-12 0.00e+00 1.71e-11
2 6.4361775e+01 -3.6729243e+02 3.08e-13 0.00e+00 1.71e-11
3 2.2399862e+01 -6.8231454e+01 1.14e-13 0.00e+00 3.75e-12
4 6.8012056e+00 -2.0011575e+01 2.45e-13 0.00e+00 1.04e-12
5 3.3548410e+00 -1.9547176e+00 1.18e-13 0.00e+00 3.55e-13
6 1.9866256e+00 6.0981384e-01 5.55e-13 0.00e+00 1.86e-13
7 1.4271894e+00 1.0119284e+00 2.82e-12 0.00e+00 1.15e-13
8 1.1434804e+00 1.1081026e+00 6.93e-12 0.00e+00 1.09e-13
9 1.1163905e+00 1.1149752e+00 5.89e-12 0.00e+00 1.14e-13
10 1.1153877e+00 1.1153509e+00 2.52e-11 0.00e+00 9.71e-14
11 1.1153611e+00 1.1153602e+00 2.10e-11 0.00e+00 8.69e-14
12 1.1153604e+00 1.1153604e+00 1.10e-11 0.00e+00 8.96e-14
Barrier time = 0.17 sec. (38.31 ticks)
Total time on 8 threads = 0.17 sec. (38.31 ticks)
QP status(1): optimal
Cplex Time: 0.17sec (det. 38.31 ticks)
Optimal solution found.
Objective : 1.115360
有关详细信息,请参阅 here。
更新:在 Matlab 中变为:
我有一组向量(曲线),我想将其匹配到一条曲线。问题不仅仅是找到最接近匹配单条曲线的一组曲线的线性组合(这可以用最小二乘 Ax = B 来完成)。我需要能够添加约束,例如将拟合中使用的曲线数量限制为特定数量,或者曲线彼此相邻。这些约束可以在混合整数线性规划优化中找到。
我开始使用允许约束的 lsqlin,并且能够将变量限制为 > 0.0,但在添加进一步约束方面我不知所措。有没有办法将整数约束添加到最小二乘法,或者有没有办法用 MILP 解决这个问题?
非常感谢任何正确方向的帮助!
编辑: 根据 ErwinKalvelagen 的建议,我正在尝试使用 CPLEX 及其二次求解器,但直到现在我还没有设法让它工作。我创建了一个最小的 'notworking' 示例,并在下面上传了 data here 和代码。问题是 matlabs LS 求解器 lsqlin
能够求解,但是 CPLEX cplexlsqnonneglin
returns CPLEX 错误 5002:%s 不是凸的 同样的问题。
function [ ] = minWorkingLSexample( )
%MINWORKINGLSEXAMPLE for LS with matlab and CPLEX
%matlab is able to solve the least squares, CPLEX returns error:
% Error using cplexlsqnonneglin
% CPLEX Error 5002: %s is not convex.
%
%
% Error in Backscatter_Transform_excel2_readMut_LINPROG_CPLEX (line 203)
% cplexlsqnonneglin (C,d);
%
load('C_n_d_2.mat')
lb = zeros(size(C,2),1);
options = optimoptions('lsqlin','Algorithm','trust-region-reflective');
[fact2,resnorm,residual,exitflag,output] = ...
lsqlin(C,d,[],[],[],[],lb,[],[],options);
%% CPLEX
ctype = cellstr(repmat('C',1,size(C,2)));
options = cplexoptimset;
options.Display = 'on';
[fact3, resnorm, residual, exitflag, output] = ...
cplexlsqnonneglin (C,d);
end
我可以重现 Cplex 问题。这是一个解决方法。不要求解第一个模型,而是使用非线性程度较低的模型:
第二个模型使用 Cplex 求解得很好。这个问题有点像 tolerance/numeric 问题。对于第二个模型,我们有一个表现更好的 Q 矩阵(对角线)。本质上,我们将一些复杂性从 objective 转移到线性约束中。
您现在应该看到如下内容:
Tried aggregator 1 time.
QP Presolve eliminated 1 rows and 1 columns.
Reduced QP has 401 rows, 443 columns, and 17201 nonzeros.
Reduced QP objective Q matrix has 401 nonzeros.
Presolve time = 0.02 sec. (1.21 ticks)
Parallel mode: using up to 8 threads for barrier.
Number of nonzeros in lower triangle of A*A' = 80200
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec. (3.57 ticks)
Summary statistics for Cholesky factor:
Threads = 8
Rows in Factor = 401
Integer space required = 401
Total non-zeros in factor = 80601
Total FP ops to factor = 21574201
Itn Primal Obj Dual Obj Prim Inf Upper Inf Dual Inf
0 3.3391791e-01 -3.3391791e-01 9.70e+03 0.00e+00 4.20e+04
1 9.6533667e+02 -3.0509942e+03 1.21e-12 0.00e+00 1.71e-11
2 6.4361775e+01 -3.6729243e+02 3.08e-13 0.00e+00 1.71e-11
3 2.2399862e+01 -6.8231454e+01 1.14e-13 0.00e+00 3.75e-12
4 6.8012056e+00 -2.0011575e+01 2.45e-13 0.00e+00 1.04e-12
5 3.3548410e+00 -1.9547176e+00 1.18e-13 0.00e+00 3.55e-13
6 1.9866256e+00 6.0981384e-01 5.55e-13 0.00e+00 1.86e-13
7 1.4271894e+00 1.0119284e+00 2.82e-12 0.00e+00 1.15e-13
8 1.1434804e+00 1.1081026e+00 6.93e-12 0.00e+00 1.09e-13
9 1.1163905e+00 1.1149752e+00 5.89e-12 0.00e+00 1.14e-13
10 1.1153877e+00 1.1153509e+00 2.52e-11 0.00e+00 9.71e-14
11 1.1153611e+00 1.1153602e+00 2.10e-11 0.00e+00 8.69e-14
12 1.1153604e+00 1.1153604e+00 1.10e-11 0.00e+00 8.96e-14
Barrier time = 0.17 sec. (38.31 ticks)
Total time on 8 threads = 0.17 sec. (38.31 ticks)
QP status(1): optimal
Cplex Time: 0.17sec (det. 38.31 ticks)
Optimal solution found.
Objective : 1.115360
有关详细信息,请参阅 here。
更新:在 Matlab 中变为: