Quadratic Cost Function x^T Q x
in [Matlab]
|
From: Matt J on 20 May 2010 15:25 "Jason" <jf203(a)ic.ac.uk> wrote in message <ht41ak$at$1(a)fred.mathworks.com>... > I think it was quite clear from the description, and please see the code. lsqnonlin does compute the sum of the squares. > > This is the reason why I wrote J = sum || x^T Qi x ||^2 > > I am referring indeed to the last case you outlined. > Do you have any suggestions for that? ============ As both Roger and I have suggested already, this function is globally minimized by x=0, so long as x is unconstrained. This is because, by direct evaluation, J=0 for x=0. Also, it is clear that there is no x for which J<0 because J is the sum of positive terms for all x. It appears as though some constraints are needed to make this problem non-trivial.
From: Roger Stafford on 20 May 2010 15:33 "Jason" <jf203(a)ic.ac.uk> wrote in message <ht41ak$at$1(a)fred.mathworks.com>... > I think it was quite clear from the description, ...... No, I disagree with you; your explanation is not at all clear, Jason! You have yet to address the problem of placing constraints on x. Three times that question has been posed to you. Why are you so reticent about that matter? I can make no more suggestions until receiving some statement on your part as to this question. Roger Stafford
From: Jason on 20 May 2010 17:22 "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <ht42pg$8he$1(a)fred.mathworks.com>... > "Jason" <jf203(a)ic.ac.uk> wrote in message <ht41ak$at$1(a)fred.mathworks.com>... > > I think it was quite clear from the description, ...... > > No, I disagree with you; your explanation is not at all clear, Jason! You have yet to address the problem of placing constraints on x. Three times that question has been posed to you. Why are you so reticent about that matter? I can make no more suggestions until receiving some statement on your part as to this question. > > Roger Stafford Dear Roger, Without placing constraints on x lsqnonlin runs, and *might* give you the correct result, i.e. the global minimum. One way to address the problem was to place a constraint on x such that x(1) and x(2) lie on a unit circle. There is no constraint on x(3). This would reduce the problem to two variables. if x(1) = cos(alpha) and x(2) = sin(alpha) then the vector x would be: x = [alpha x(3)]. This works fine using lsqnonlin, however it still does not guarantee that I won't get trapped in a local (suboptimal) minimum. Think of the vector x as a line in geometrical 2-D space. I want to estimate the parameters of this line, i.e. x(1)*x + x(2)*y + x(3). Pardon my ignorance, but even without placing any constraints on x you get a non-trivial solution (i.e. not x = 0). This is why I reformulated my statement, I am not reticent about the matter. By the way, I have tried fmincon using the nonlinear constraint x(1)^2 + x(2)^2 -1 = 0 but (barring any programming error from my side) did not provide correct results. My main question is if I can use something different than lsqnonlin which takes a very long time to run and is prone to fall into suboptimal minima. Best regards, Jason
From: Matt J on 20 May 2010 17:47 "Jason" <jf203(a)ic.ac.uk> wrote in message <ht495s$eq2$1(a)fred.mathworks.com>... > "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message > Think of the vector x as a line in geometrical 2-D space. I want to estimate the parameters of this line, i.e. x(1)*x + x(2)*y + x(3). > > Pardon my ignorance, but even without placing any constraints on x you get a non-trivial solution (i.e. not x = 0). =============== But the cost function for this estimation problem bears no resemblance to the one you posed. > > My main question is if I can use something different than lsqnonlin which takes a very long time to run and is prone to fall into suboptimal minima. ================= You might try running lsqnonlin with the Algorithm option to 'levenberg-marquardt'. My intuition about the default trust-region method is that, even if you initialize in the correct capture basin, the algorithm can crawl out of it into something less optimal. Conversely, Levenberg-Marquardt is, according to my intuition, may be more basin-preserving. Also, if you supply an analytical gradient then, according to doc lsqnonlin, it could be more computationally cheap per iteration. All of this assumes that you have at least a reasonable guess of the initial solution, but there's no escaping that when it comes to non-convex minimization.
From: Jason on 20 May 2010 18:07
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht4al2$jcc$1(a)fred.mathworks.com>... > "Jason" <jf203(a)ic.ac.uk> wrote in message <ht495s$eq2$1(a)fred.mathworks.com>... > > "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message > > > Think of the vector x as a line in geometrical 2-D space. I want to estimate the parameters of this line, i.e. x(1)*x + x(2)*y + x(3). > > > > Pardon my ignorance, but even without placing any constraints on x you get a non-trivial solution (i.e. not x = 0). > =============== > > But the cost function for this estimation problem bears no resemblance to the one you posed. > > > > > > My main question is if I can use something different than lsqnonlin which takes a very long time to run and is prone to fall into suboptimal minima. > ================= > > You might try running lsqnonlin with the Algorithm option to 'levenberg-marquardt'. My intuition about the default trust-region method is that, even if you initialize in the correct capture basin, the algorithm can crawl out of it into something less optimal. Conversely, Levenberg-Marquardt is, according to my intuition, may be more basin-preserving. Also, if you supply an analytical gradient then, according to doc lsqnonlin, it could be more computationally cheap per iteration. > > All of this assumes that you have at least a reasonable guess of the initial solution, but there's no escaping that when it comes to non-convex minimization. I will try the levenberg-marquardt option, thanks! As for your inquiry, what do you mean? 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. Regards, Jason |