Quadratic Cost Function x^T Q x
in [Matlab]
|
From: Jason on 20 May 2010 14:25 "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <ht3ov1$b3k$1(a)fred.mathworks.com>... > "Jason" <jf203(a)ic.ac.uk> wrote in message <ht3lr4$fft$1(a)fred.mathworks.com>... > > Hello, > > > > I have a (quadratic) non-linear problem of the type x^T Q x. > > > > Specifically the non-convex objective function is given by > > > > J = SUM ||x^T Qi x||^2 > > > > for i <= 3. > > > > My goal is to find arg min x, i.e. the values for the vector x. > > > > Q is a symmetric 3 x 3 matrix and x is a vector of length 3. This is why i <= 3 since we have 3 parameters (unknowns) in x. > > > > I am currently using lsqnonlin to find a solution. However I am getting trapped in local minima if I don't use a good starting guess for vector x. > > > > My question is, can I use something more 'robust' than lsqnonlin? > > Furthermore is there actually a global minimum in my problem? > > > > What would be the best way to find it? > > > > Many thanks. > > Well, unless you place some constraint on x, the obvious solution is x = 0. However, if you require that the norm of x be unity, then do this. > > [V,D] = eig(Q); > > Then the column of V that is paired with the smallest eigenvalue in absolute value in D will presumably be a solution. > > You have confused me, however, in writing J = SUM ||x^T Qi x||^2. My understanding is that x here must be a column vector and therefore x'*Qi*x would then be a scalar. What is the point of doing a 'sum' when there is only one number? All you want to do is minimize abs(x'*Qi*x), or equivalently minimize (x'*Qi*x)^2. > > Roger Stafford Why is there a global minimum at x=0 ?? Maybe I haven't expressed myself right. Qi is a matrix of 3x3, x = column vector of length 3. The result should be 0 if the correct values for x are chosen. What I mean with the sum is... x^T (Q_1 + Q_2 + ... Q_i) x Let me show you the code to avoid confusion: (Note that I need to feed in Q from another function since it changes, Q in this case is a cell of matrices Q.) function F = opt_routine(x,sns,Q); for i = 1:sns F(i) = (x.')*Q{i}*x; end end We want to find the values for x so: variable1 = @(x)opt_routine(x,sns,Q); [x,res] = lsqnonlin(variable1,[] ....) Ok ?
From: Matt J on 20 May 2010 14:43 "Jason" <jf203(a)ic.ac.uk> wrote in message <ht3tl0$mbi$1(a)fred.mathworks.com>... > Why is there a global minimum at x=0 ?? > > Maybe I haven't expressed myself right. Qi is a matrix of 3x3, x = column vector of length 3. The result should be 0 if the correct values for x are chosen. > > What I mean with the sum is... x^T (Q_1 + Q_2 + ... Q_i) x ===================== What you wrote here is not consistent with the code you show below. If the function you are trying to minimize is f(x) = x^T (Q_1 + Q_2 + ... Q_i) x Then with A=(Q_1 + Q_2 + ... Q_i), this is a very basic quadratic minimization f(x)= x'*A*x If A is positive definite and x is unconstrained, then this function is minimized trivially at x=0. If A is not positive definite and x is unconstrained, this function is not bounded from below, i.e., no global minimum exists. All of this so far is standard theory. The code below, on the other hand, is as I originally understood your post. According to the code, you want to minimize the function f(x) = ( x'*Q_1*x )^2 + ( x'*Q_2*x )^2 + ( x'*Q_3*x )^2 This function satisfies f(0)=0. It is also clear that this is a global minimum because f(x)>=0 for all x (because f(x) is the sum of positive terms). ================== > Let me show you the code to avoid confusion: > > (Note that I need to feed in Q from another function since it changes, Q in this case is a cell of matrices Q.) > > > function F = opt_routine(x,sns,Q); > for i = 1:sns > F(i) = (x.')*Q{i}*x; > end > end > > We want to find the values for x so: > variable1 = @(x)opt_routine(x,sns,Q); > > [x,res] = lsqnonlin(variable1,[] ....) > > Ok ?
From: Roger Stafford on 20 May 2010 14:44 "Jason" <jf203(a)ic.ac.uk> wrote in message <ht3tl0$mbi$1(a)fred.mathworks.com>... > > Why is there a global minimum at x=0 ?? > > Maybe I haven't expressed myself right. Qi is a matrix of 3x3, x = column vector of length 3. The result should be 0 if the correct values for x are chosen. > > What I mean with the sum is... x^T (Q_1 + Q_2 + ... Q_i) x > > Let me show you the code to avoid confusion: > > (Note that I need to feed in Q from another function since it changes, Q in this case is a cell of matrices Q.) > > > function F = opt_routine(x,sns,Q); > for i = 1:sns > F(i) = (x.')*Q{i}*x; > end > end > > We want to find the values for x so: > variable1 = @(x)opt_routine(x,sns,Q); > > [x,res] = lsqnonlin(variable1,[] ....) > > Ok ? You will have to explain yourself better than you have, Jason. As things stand, setting all the three elements of x equal to zero guarantees that x'*Qi*x will be the scalar zero, and therefore each component of the sum in J would be zero. Hence J would be zero and it can't be less than zero, so zero would be the minimum. This will remain true until you place some constraint on acceptable x vectors that rules out having all its elements equal to zero. If you really mean what you say in x^T (Q_1 + Q_2 + ... Q_i) x, then the eigenvector technique I gave you would still work as applied to the sum of the Q's. However, if you actually mean J is the sum of the squares of the x'*Qi*x scalars, that is an entirely different matter. Which is it you mean? Roger Stafford
From: Matt J on 20 May 2010 14:46 "Jason" <jf203(a)ic.ac.uk> wrote in message <ht3tl0$mbi$1(a)fred.mathworks.com>... > Why is there a global minimum at x=0 ?? > > Maybe I haven't expressed myself right. Qi is a matrix of 3x3, x = column vector of length 3. The result should be 0 if the correct values for x are chosen. > > What I mean with the sum is... x^T (Q_1 + Q_2 + ... Q_i) x ===================== What you wrote here is not consistent with the code you show below. If the function you are trying to minimize is f(x) = x^T (Q_1 + Q_2 + ... Q_i) x Then with A=(Q_1 + Q_2 + ... Q_i), this is a very basic quadratic minimization f(x)= x'*A*x If A is positive definite and x is unconstrained, then this function is minimized trivially at x=0. If A is not positive definite and x is unconstrained, this function is not bounded from below, i.e., no global minimum exists. All of this so far is standard theory. The code below, on the other hand, is as I originally understood your post. According to the code, you want to minimize the function f(x) = ( x'*Q_1*x )^2 + ( x'*Q_2*x )^2 + ( x'*Q_3*x )^2 This function satisfies f(0)=0. It is also clear that this is a global minimum because f(x)>=0 for all x (because f(x) is the sum of positive terms). ================== > Let me show you the code to avoid confusion: > > (Note that I need to feed in Q from another function since it changes, Q in this case is a cell of matrices Q.) > > > function F = opt_routine(x,sns,Q); > for i = 1:sns > F(i) = (x.')*Q{i}*x; > end > end > > We want to find the values for x so: > variable1 = @(x)opt_routine(x,sns,Q); > > [x,res] = lsqnonlin(variable1,[] ....) > > Ok ?
From: Jason on 20 May 2010 15:08
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <ht3vtl$o1d$1(a)fred.mathworks.com>... > "Jason" <jf203(a)ic.ac.uk> wrote in message <ht3tl0$mbi$1(a)fred.mathworks.com>... > > > > Why is there a global minimum at x=0 ?? > > > > Maybe I haven't expressed myself right. Qi is a matrix of 3x3, x = column vector of length 3. The result should be 0 if the correct values for x are chosen. > > > > What I mean with the sum is... x^T (Q_1 + Q_2 + ... Q_i) x > > > > Let me show you the code to avoid confusion: > > > > (Note that I need to feed in Q from another function since it changes, Q in this case is a cell of matrices Q.) > > > > > > function F = opt_routine(x,sns,Q); > > for i = 1:sns > > F(i) = (x.')*Q{i}*x; > > end > > end > > > > We want to find the values for x so: > > variable1 = @(x)opt_routine(x,sns,Q); > > > > [x,res] = lsqnonlin(variable1,[] ....) > > > > Ok ? > > You will have to explain yourself better than you have, Jason. > > As things stand, setting all the three elements of x equal to zero guarantees that x'*Qi*x will be the scalar zero, and therefore each component of the sum in J would be zero. Hence J would be zero and it can't be less than zero, so zero would be the minimum. This will remain true until you place some constraint on acceptable x vectors that rules out having all its elements equal to zero. > > If you really mean what you say in x^T (Q_1 + Q_2 + ... Q_i) x, then the eigenvector technique I gave you would still work as applied to the sum of the Q's. However, if you actually mean J is the sum of the squares of the x'*Qi*x scalars, that is an entirely different matter. Which is it you mean? > > Roger Stafford Dear Roger, Thanks for your reply. 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? Many thanks |