Quadratic Cost Function x^T Q x
in [Matlab]
|
From: Bruno Luong on 21 May 2010 01:55 "Jason" <jf203(a)ic.ac.uk> wrote in message <ht4bq9$4t9$1(a)fred.mathworks.com>... > > > The cost function is still the same. > > As I said J = min x ( x' Q x). > > I am following a principle from computer vision where Q is the matrix representation of a conic (an ellipse). If you set Q = adj(Q) (where adj means adjoint) then x' Q x = 0 means that if this equation is satisfied, then the line parametrized by x is tangent to the ellipse. The additional constraint i have gaven, namely that x(1) and x(2) lie on a unit circle only helps but is not necessary. Can you parametrize the "lines" with the constraints x(1)^2+x^2+x(3)^3 = 1 Rather than just the first two? Seem like it make more symmetry to me. In any case, such Quadratic programming with norm constraint can be solved by the similar approach I used in my FEX submission: http://www.mathworks.com/matlabcentral/fileexchange/27596-least-square-with-2-norm-constraint I believe it is possible to extend the method of norm constraint to semi-norm constraint. Bruno
From: Matt J on 21 May 2010 06:33 "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <ht578a$n72$1(a)fred.mathworks.com>... > Can you parametrize the "lines" with the constraints x(1)^2+x^2+x(3)^3 = 1 Rather than just the first two? Seem like it make more symmetry to me. > > In any case, such Quadratic programming with norm constraint can be solved by the similar approach I used in my FEX submission: > > http://www.mathworks.com/matlabcentral/fileexchange/27596-least-square-with-2-norm-constraint > > I believe it is possible to extend the method of norm constraint to semi-norm constraint. ========= But it is not a quadratic program, Bruno. The objective function is quartic.
From: Bruno Luong on 21 May 2010 07:09 "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht5ngv$mot$1(a)fred.mathworks.com>... > "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message > > But it is not a quadratic program, Bruno. The objective function is quartic. No, in fact they are the same problem: in both cases a quadratic functional is minimized. The formulation in QEP is derived from the Euler Lagrange condition. AFAICS, the calculation *should* be transposed more or less straight forward. I let OP work on it first, if he get stuck I can give a hand. Bruno
From: Bruno Luong on 21 May 2010 07:23 Well, actually I'm confused. The reason I think it's quadratic because I quote (from OP): 'As I said J = min x ( x' Q x).' OR in another thread [ If I have a quadratic optimization problem of the type min(x) x' Q x Where Q is symmetric but indefinite (3x3) matrix, and x is column vector of length 3. Fmincon and quadprog could solve this. ] So what exactly he wants to minimize? It seems Jason confused many people, and even Roger has left the thread. Bruno
From: Jason on 21 May 2010 07:59
"Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <ht5qeo$26u$1(a)fred.mathworks.com>... > Well, actually I'm confused. The reason I think it's quadratic because I quote (from OP): > > 'As I said J = min x ( x' Q x).' > > OR in another thread > > [ If I have a quadratic optimization problem of the type > > min(x) x' Q x > > Where Q is symmetric but indefinite (3x3) matrix, and x is column vector of length 3. > > Fmincon and quadprog could solve this. ] > > So what exactly he wants to minimize? It seems Jason confused many people, and even Roger has left the thread. > > Bruno Bruno, it is quite clearly quadratic. And it's quite clear that you minimize x, i.e. find the values of x that minimize x' Q x. If something is not clear in your mind then don't blame me. Using Matt's approach you can find a solution quickly and efficiently. He proposed constraining x_3, but you might just consider the subspace x_1 = 1 (which excludes the solution x_1 = 0) so you can combine it with the minimization on a different hyperplane that includes x_1 = 0. In any case it is possible to obtain a closed form solution and in order to find the global minimum you can find the stationary points of the two cost functions created for each subspace. Thanks for your help, but I don't think it's in my scope to try it out, I want something from scratch and not hacking a ready code, which I am not even sure is applicable for my purposes. Best regards, Jason |