0

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

我开始使用 lsqlin，它允许约束并且能够将变量限制为 > 0.0，但在添加更多约束方面我不知所措。有没有办法将整数约束添加到最小二乘，或者有没有办法用 MILP 解决这个问题？

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

编辑：根据 ErwinKalvelagen 的建议，我正在尝试使用 CPLEX 及其二次求解器，但是直到现在我还没有设法让它工作。我创建了一个最小的“不工作”示例，并在此处上传了数据并在下面上传了代码。问题是 matlabs LS 求解器lsqlin能够求解，但是 CPLEXcplexlsqnonneglin返回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
4

1 回答 1

2

我可以重现 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

请参阅此处了解一些详细信息。

更新：在 Matlab 中，这变成：

在此处输入图像描述

于 2018-01-15T15:43:58.823 回答