Quadprog says the problem is non-convex

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
clc

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
axis([-2,2,-2,2])
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)

Answer 1

[Matt J]

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)

[monkey_matlab]

Hello Matt, can you extrapolate your meaning of "regularize Q". Thanks for all your time and help!

[Matt J]

By regularize, I mean as discussed here. The example I showed you is a simple example of Tikhonov regularization.

Answer 2

[Matt J]

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