Quadprog says the problem is non-convex

25 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
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.

Tags

Products

Community Treasure Hunt

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

Start Hunting!