MATLAB: Quadprog ‘interior-point-convex’ failure

active-setfminconOptimization Toolboxquadprog

Dear Matlab Gurus,
I have a problem with Matlab quadprog function.
A few years ago I implemented a code using quadprog with the 'active-set' algorithm, and it worked pretty well. The problem is characterised by a structurally dense hessian and inequality constraint matrix (see data attached).
Now this algorithm is no more available and only 'interior-point-convex' and 'trust-region-reflective' can be used. However, the 'trust-region-reflective' cannot be used with inequality constraints. So the choice is reduced to 'interior-point-convex' that is not able to solve the problem:
clear variables, close all
% load problem


load('testData.mat');
% quadprog setup (R2018b)
opts = optimoptions(@quadprog,...
    'Algorithm','interior-point-convex');
tic
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,[],[],x0,opts);
toc
The output is
The interior-point-convex algorithm does not accept an initial point.
Ignoring X0.
No feasible solution found.
quadprog stopped because it was unable to find a point that satisfies
the constraints within the default value of the constraint tolerance.
<stopping criteria details>
The funny is that I already have a feasible solution x0, but the 'interior-point-convex' algorithm does not accept an initial point:
% feasibility check
any(A*x0-b > 0)
ans =
     0
When using the 'active-set' algorithm with a Matlab version < 2016 everything is fine and the algorithm ends correctly.
clear variables, close all
% load problem
load('testData.mat');
% quadprog setup (R2015b)
opts = optimoptions(@quadprog,...
    'Algorithm','active-set');
tic
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,[],[],x0,opts);
toc
with output
Warning: The 'active-set' algorithm will be removed in a future release. To avoid this warning or a future error, choose a
different algorithm: 'interior-point-convex' or 'trust-region-reflective'.
 
> In quadprog (line 427)
  In test_quadprog_solvers (line 10) 
Optimization terminated.
Elapsed time is 2.239872 seconds.
I have seen that fmincon still have the 'active-set' algorithm and I am wondering if with a proper setup of options I can trick the optimizer to solve a purely quadratic programming. I tried:
clear variables, close all
% load problem
load('testData.mat');
% fmincon setup (R2018b)
opts = optimoptions(@fmincon,...
    'Algorithm','active-set',...
    'SpecifyObjectiveGradient',true);
tic
[xred,fval,exitflag,output,lambda] = fmincon(@(x)quadFcn(x,H,f),x0,A,b,Aeq,beq,[],[],[],opts);
toc
With
function [fval,gval] = quadFcn(x,H,f)
fval = .5*x'*H*x+f'*x;
if nargout > 1 % gradient required
    gval = H*x+f;
end
end
And the result is fine
Local minimum possible. Constraints satisfied.
fmincon stopped because the predicted change in the objective function
is less than the default value of the function tolerance and constraints 
are satisfied to within the default value of the constraint tolerance.
<stopping criteria details>
Elapsed time is 3.966116 seconds.
But the calculation time is almost doubled with respect to the quadprog function with 'active-set' algorithm, and things are worse for more complex problems than this simple benchmark.
Any idea to restore the original behavior or performance?
Thank you in advance

Best Answer

Simply l2-normalizing the rows of A also seems to help,
load('testData-Matt.mat');
opts = optimoptions(@quadprog,'Algorithm','interior-point-convex');
anorm=vecnorm(A,2,2);
AAA=A./anorm;
bbb=b./anorm;
tic;
[y,fval,exitflag,output,lambda] = quadprog(H,f,AAA,bbb,[],[],[],[],[],opts);
toc%Elapsed time is 1.533334 seconds.
>> exitflag
exitflag =
     1
Related Question