Quadprog says the problem is non-convex

3 views (last 30 days)
monkey_matlab
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
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)

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)
  2 Comments
monkey_matlab
monkey_matlab on 17 Oct 2016
Edited: monkey_matlab on 17 Oct 2016
Hello Matt, can you extrapolate your meaning of "regularize Q". Thanks for all your time and help!
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.

Categories

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

Tags

Products

Community Treasure Hunt

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

Start Hunting!