CODEWITHSUNDEEP
matlabquadratic
user34790
user34790

Reputation: 2036

Issues with quadratic programming

I am trying to do a quadratic programming. I have an affinity matrix A, and I have to maximize certain function x'*A*x. This is basically related to feature matching i.e., matching points to labels

This is basically related to establish a connection between dominant sets in a weighted graph and local maximizers of the quadratic function

maximize(f({x} = x^{T}A{x})

subject to 

x \epsilon\Delta, \Delta:\sum_{j}x_j=1

To solve this problem I found a method called replicator equation given by Pavan and Pelillo IEEE PAMI 2007

Once an initialization x(1) is given, the discrete replicator equation can be used to obtain a local solution x*

x_i(t+1) = x_i(t+1) \frac{(Ax(t))_i}{x(t)^TAx(t)}

I get the right results when I use the replicator equation. However, when I try to solve it using matlab's quadprog function like this 

X = quadprog(-A,[],[],[],Aeq,Beq,s);

I don't get the right values. Suppose I want to match 7 points with 7 labels, I define my affinity matrix and then use the above. However, using replicator equation I get the right results. But using just quadprog doesn't give me the right results. Any suggestions?

Am I doing something wrong?

Upvotes: 2

Views: 3317

Answers (2)

Min Lin
Min Lin

Reputation: 3197

If A is positive-semidefinite, then the maximization problem is a concave problem rather than a convex one. If A is negative semidefinite, then -A is positive semidefinite. You can just optimize x^T(-A)x in matlab.

Namely:

min x^TAx

is convex,

and

max x^TAx  =  min x^T(-A)x

is concave.

if 

A>0 (Positive semidefinite)

And quadprog needs convex

Since matlab quadprog fails, I guess your A is positive semidefinite. You can do eig(A) to check if all eigen values are positive, thus you need some concave optimization solution.

Upvotes: 1

Bitwise
Bitwise

Reputation: 7805

quadprog() documentation shows:

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)

A and b can be [] if there are no inequality constraints, but it does not say that about f, so I am assuming you should set f to be a zeros vector. Also, if what you marked as s is your initialization, then it isn't located in the correct position.

The line your wrote as:

X = quadprog(-A,[],[],[],Aeq,Beq,s);

should be:

X = quadprog(-A,f,[],[],Aeq,Beq,[],[],s);

where f is a zeros vector.

BTW if this is convex you shouldn't need the initialization point, and if it is not convex, I am not sure you can be guaranteed to find the same local solution as the replicator method.

Upvotes: 1

Related Questions