代码之家 › 专栏 › 技术社区 › Jesse RJ

曲线的线性组合,以匹配具有整数约束的单个曲线

mixed-integer-programming least-squares linear-programming matlab

Jesse RJ · 技术社区 · 8 年前

我有一组向量(曲线),我想匹配到一条曲线。问题不仅仅是找到一组曲线的线性组合,这些曲线将与单个曲线最为匹配(这可以通过最小二乘法Ax=B来实现)。我需要能够添加约束,例如将拟合中使用的曲线数量限制为特定数量,或者曲线彼此相邻。这些约束条件可以在混合整数线性规划优化中找到。

我已经开始使用lsqlin,它允许约束,并且能够将变量限制为>0.0,但在添加更多约束方面,我感到不知所措。有没有一种方法可以将整数约束添加到最小二乘法中,或者有没有一种方法可以用MILP来解决这个问题?

非常感谢在正确方向上的任何帮助!

编辑: 根据ErwinKalvelagen的建议,我正在尝试使用CPLEX及其Quadratic解算器,但到目前为止,我还没有成功地使其工作。我创建了一个最小的“notworking”示例,并上传了 data here 和下面的代码。问题是matlabs LS solver lsqlin 能够解决,但是CPLEX cplexlsqnonneglin 退货 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

1 回复 | 直到 8 年前

Erwin Kalvelagen 8 年前

我可以重现Cplex问题。这里有一个变通方法。不要求解第一个模型,而是使用非线性程度较低的模型:

第二个模型使用Cplex进行精细求解。这个问题在某种程度上是一个公差/数字问题。对于第二个模型,我们有一个性能更好的Q矩阵(对角线)。本质上,我们将一些复杂性从目标转移到了线性约束中。

您现在应该看到如下内容:

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中,这变成: