Quadprog says the problem is non-convex

17 views (last 30 days)
monkey_matlab on 17 Oct 2016
Edited: Matt J on 17 Oct 2016
Hello, I am trying to get the solution of the SVM algorithm for the two classes listed. I am trying to use quadprog to solve for the variables alpha1 through alpha6.
Can you tell me what I might be doing wrong with setting up quadprog?
Here is my code:
clear all
close all
Class1 = [1 0; 0.5 1; 0.5 1.5];
Class2 = [0 -1; -1 1; 0.5 -1];
x1_c1 = Class1(:,1);
y1_c1 = Class1(:,2);
x2_c2 = Class2(:,1);
y2_c2 = Class2(:,2);
hold on
plot(x1_c1, y1_c1, 'ro');
plot(x2_c2, y2_c2, 'b^');
ClassesA = [Class1; Class2]';
f = [-ones(6,1)]';
b = [zeros(1,6)]';
y = [ones(3,1); -ones(3,1)];
Q = (y * y') .* (ClassesA' * ClassesA);
x = quadprog(Q,y)

Answers (2)

Matt J
Matt J on 17 Oct 2016
Edited: Matt J on 17 Oct 2016
Your Q is singular. As one consequence, this makes the problem ill-posed. As another, it makes Q appear numerically to have negative eigenvalues, such that the problem appears non-convex and its minimum unbounded. You must regularize Q in some way, e.g.,
x = quadprog(Q+eye(6)*.000001,y)
Matt J
Matt J on 17 Oct 2016
Edited: Matt J on 17 Oct 2016
By regularize, I mean as discussed here. The example I showed you is a simple example of Tikhonov regularization.

Sign in to comment.

Matt J
Matt J on 17 Oct 2016
If it is natural to put norm constraints on alpha, you can solve with TRUSTREGPROB ( Download ), as opposed to QUADPROG.


Find more on Quadratic Programming and Cone Programming in Help Center and File Exchange



Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!