MATLAB Answers

Quadprog message: The problem is non-convex

134 views (last 30 days)
S.
S. on 23 Jan 2020
Edited: Matt J on 24 Mar 2020 at 6:27
Hi,
First of all, I am using Matlab 2017b and the optimalization toolbox of 2019. I am using quadprog (not suprisingly ;)) to solve a QP problem. In reality, my problem is convex, however I get in the command window a message from quadprog that my problem is non-convex. I am not using lower and upper bounds, but inequality constraints. Furthermore, I checked if I had negative eigenvalues in my Hessian. This was indeed the case. I had one or two really small negative eigenvalues (-1e20). However, I am using quadprog for multiple timesteps, whereby the lineair term f (in my case F) is updated and therefore changes a little bit after every time step. If I am running the code for example for 10 timesteps, I get 8 times the message that the problem is non-convex and two times that the problem is convex and a minimum has been found. This is in my opinion quite weird, because the Hessian stays the same every timestep (and with that the one or two really small negative eigenvalues).
Does anyone have a potential solution to fix this issue or the cause of it? If you think you need more information, please let me know.
tic;
[X,fval,exitflag,output,lambda] = quadprog(G,F,Aineq_SparseCondensed,bineq_SparseCondesed,[],[],[],[],[],options);
toc
G = (G+G')/2;
Thanks in advance!
Kind regards

  1 Comment

Walter Roberson
Walter Roberson on 9 Mar 2020 at 2:23
You cannot use the 2019 toolboxes with 2017 MATLAB without expecting inexplicable errors.

Sign in to comment.

Accepted Answer

Matt J
Matt J on 23 Jan 2020
Edited: Matt J on 23 Jan 2020
You cannot submit a problem that is borderline convex to quadprog if it is using an algorithm that expects convexity. If you do, quadprog can see the problem as convex or not-convex arbitrarily, depending on floating point numerical errors that essentially contribute random noise to the calculations that it is doing.
I would guess that your Hessian is supposed to be more distinctly positive definite, so you should review the way you set up the problem.

  42 Comments

S.
S. on 23 Mar 2020 at 18:27
Yeah I know.... But how do you know the number of iterations each time it solves a QP? I cannot manage to do that by hand 100 times?
And did you get something from the scripts?
Matt J
Matt J on 23 Mar 2020 at 18:32
The "output" argument from quadprog will contain the number of iterations used, as well as other info.
[x,fval,exitflag,output] = quadprog(___)
I will not have time to look at the scripts anytime soon, but it is irrelevant for now. The computation time per iteration is the first thing you should check.
S.
S. on 23 Mar 2020 at 19:12
Oke, then I know now how to do that.
So I have to check whether the computation per iteration scales with O(N) in stead the computation time of one QP scales with O(N). So only the number of required iterations could also scale with O(N)?
Furthermore, the very last question :), if another solver, gets the same optimized values x, but the fval is different. How is that possible? For example quadprog and Gurobi (another solver) are given me the same x and fval, but GPAD gives me the same x, but an fval, which is a factor 10 bigger compared to quadprog and Gurobi.

Sign in to comment.

More Answers (0)

Sign in to answer this question.