Prev: convert to polar coordinate
Next: Region boundary extraction post-edge detection
From: Jason on 20 May 2010 11:52
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.
From: Matt J on 20 May 2010 12:39
"Jason" <jf203(a)ic.ac.uk> wrote in message <ht3lnt$92i$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.
===============

The sum is over i? If so, it is trivial to see that there is a global minimum at x=0.
From: Roger Stafford on 20 May 2010 12:45
"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
From: Jason on 20 May 2010 14:05
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht3oj8$gpr$1(a)fred.mathworks.com>...
> "Jason" <jf203(a)ic.ac.uk> wrote in message <ht3lnt$92i$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.
> ===============
>
> The sum is over i? If so, it is trivial to see that there is a global minimum at x=0.

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: Jason on 20 May 2010 14:07
"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

See my reply above.
 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: convert to polar coordinate
Next: Region boundary extraction post-edge detection