Prev: 'popupmneu' uicontrol behavior in Linux
Next: GUIDE and prgrammaticaly create GUI
From: Jason on 19 Jul 2010 14:35
I seem to have hit a brick-wall, when I initially thought the problem was solved.

Just to re-iterate, we are facing a system of the type (x^T Q x)^2 for which x = [x1,x2,x3] and Q is a 3x3 matrix representing a conic (or more specifically an ellipse). Note that we are dealing with homogenous coordinates.

The idea was to find the common tangent to a set of ellipses Q1, Q2, Q3, Q4 ... which is done by computing the adjoint of sum{Q1,...,Q4} and then solving for the parameters x1,x2,x3.

We did this (as proposed by Matt) by decomposing the problem into 3 cases:

Case 1: Set x = [x1,x2,1]

Case 2: Set x = [x1,1,0]

Case 3: Set x = [1,x2,0]

Obtaining the solutions for Cases 2 and 3 is trivial as we are dealing with a 1-D polynomial for which we can compute the roots and hence obtain our solution.

Case 1 is a bit more complex since we are dealing with a fourth order polynomial in both x1 and x2.

For this case we have our initial function f = ( [x1,x2,1]^T * Q * [x1,x2,1] )^2.
Note that Q = [a,b,d;b,c,e;d,e,f].

Hence f = (a*x1^2 + 2b*x1*x2 + 2d*x1 + c*x2^2 + 2e*x2 + f)^2

What I do next is compute the partial derivative of f with respect to x1 and the partial derivative of f with respect to x2. I then set the first partial derivative to 0 to compute the roots:

df/dx1 = 0.

I am left with some roots (potentially complex) which I substitute for x1 into the partial derivative of f with respect to x2, i.e. into df/dx2.

I set this to zero as well to get my solutions for x2, i.e. I do

df/dx2 (x1,1,...,x1,N) = 0.

I am left with an expression for x2 which is only dependent on Q, i.e. on known parameters a,b,c,d,e,f !

These solutions are potentially complex as well.

I then take these results for x2 and resubstitute into the original roots i found for df/dx1 = 0 to compute values x1.

This is pretty standard practice for computing the global minima of a function depending on two variables right?


The problem is, my results are wrong. And I don't know why.

Is there something wrong with my thinking? Did I omit something. Is something not true when dealing with potentially complex roots?

I can be more specific if you like!

Many thanks
From: Matt J on 19 Jul 2010 16:17
"Jason" <jf203(a)ic.ac.uk> wrote in message <i225sp$gej$1(a)fred.mathworks.com>...

> The idea was to find the common tangent to a set of ellipses Q1, Q2, Q3, Q4 ... which is done by computing the adjoint of sum{Q1,...,Q4} and then solving for the parameters x1,x2,x3.
==========

No, you cannot approach the problem by combining all the Q{i} into one matrix. The problem as we've posed it is to minimize,

J(x)=sum_i (x' * adjoint(Q{i}) *x)^2

This is NOT equivalent to the function (x' * sum_i (adjoint(Q{i}) *x)^2

If that had been true, it would mean that the problem of finding a line uniquely tangent to multiple ellipses is equivalent to finding a line intersecting the single ellipse sum_i (Q{i}). But since a single ellipse never has a unique tangent line, you know it can't be equivalent to a multi-ellipse case in which the solution is unique.


> What I do next is compute the partial derivative of f with respect to x1 and the partial derivative of f with respect to x2. I then set the first partial derivative to 0 to compute the roots:
>
> df/dx1 = 0.
>
> I am left with some roots (potentially complex)
=================

You wouldn't get numerical values for these roots. At best, you would get VERY complicated expressions for the roots in terms of the unknown x2.




>which I substitute for x1 into the partial derivative of f with respect to x2, i.e. into df/dx2.
>
> I set this to zero as well to get my solutions for x2, i.e. I do
>
> df/dx2 (x1,1,...,x1,N) = 0.
>
> I am left with an expression for x2 which is only dependent on Q, i.e. on known parameters a,b,c,d,e,f !
===================

But because the expressions substituted in for x1 are very complicated functions of x2, this equation should be a VERY hard root finding problem. How did you solve it?


> These solutions are potentially complex as well.
>
> I then take these results for x2 and resubstitute into the original roots i found for df/dx1 = 0 to compute values x1.
>
> This is pretty standard practice for computing the global minima of a function depending on two variables right?
===============

If you can simultaneously solve the equations df/dxi=0, then yes, but often those equations are too complicated to solve analytically (as they are here) and need to be solved by more indirect means. That's why the approaches I recommended to you in earlier posts were more elaborate.
From: Matt J on 19 Jul 2010 16:29
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <i22bs1$bsh$1(a)fred.mathworks.com>...
>The problem as we've posed it is to minimize,
>
> J(x)=sum_i (x' * adjoint(Q{i}) *x)^2
>
> This is NOT equivalent to the function (x' * sum_i (adjoint(Q{i}) *x)^2
=======

Should have been ( x' * adjoint(sum_i Q{i}) * x )^2
From: Jason on 19 Jul 2010 17:04
No, you cannot approach the problem by combining all the Q{i} into one matrix. The problem as we've posed it is to minimize,

J(x)=sum_i (x' * adjoint(Q{i}) *x)^2

This is NOT equivalent to the function (x' * sum_i (adjoint(Q{i}) *x)^2

==============================================

Point taken!

You wouldn't get numerical values for these roots. At best, you would get VERY complicated expressions for the roots in terms of the unknown x2.

===============================================

Yes, exactly. It will be a complicated expression in terms of the unknown x2. However you can solve it using symlinks and the matlab 'solve' command.

For example (NOTE THAT x1 and x2 are replaced by l1 and l2 in my code!):

J1 = (a*l1^2 + 2*b*l1*l2 + 2*d*l1 + c*l2^2 + 2*e*l2 + f)^2

The first derivative in terms of l1:
dJl1 = 4*(d + a*l1 + b*l2)*(a*l1^2 + 2*b*l1*l2 + 2*d*l1 + c*l2^2 + 2*e*l2 + f)

The roots of this:

root1 = -(d + b*l2)/a
root2 = -(d + b*l2 - (b^2*l2^2 + 2*b*d*l2 + d^2 - a*c*l2^2 - 2*a*e*l2 - a*f)^(1/2))/a
root3 = -(d + b*l2 + (b^2*l2^2 + 2*b*d*l2 + d^2 - a*c*l2^2 - 2*a*e*l2 - a*f)^(1/2))/a

Solutions for l2 based on the first root:

l2_1 = (b*d - a*e + a*((f*b^2 - 2*b*d*e + c*d^2 + a*e^2 - a*c*f)/a)^(1/2))/(a*c - b^2)
l2_2 = -(a*e - b*d)/(a*c - b^2)
l2_3 = -(a*e - b*d + a*((f*b^2 - 2*b*d*e + c*d^2 + a*e^2 - a*c*f)/a)^(1/2))/(a*c - b^2)

Solutions for l1 by substituting back into root1:

l1_1 = -(d + (b*(b*d - a*e + a*((f*b^2 - 2*b*d*e + c*d^2 + a*e^2 - a*c*f)/a)^(1/2)))/(a*c - b^2))/a
l1_2 = -(d - (b*(a*e - b*d))/(a*c - b^2))/a
l1_3 = -(d - (b*(a*e - b*d + a*((f*b^2 - 2*b*d*e + c*d^2 + a*e^2 - a*c*f)/a)^(1/2)))/(a*c - b^2))/a

etc...

Is there anything wrong with that?

How else could I approach the problem then?

And wouldn't it be possible to just correct the first inconsistency you presented by summing over i in all the cases but following the same methodology ?

Regards,
Jason
From: Matt J on 20 Jul 2010 11:04
"Jason" <jf203(a)ic.ac.uk> wrote in message <i22ek6$90o$1(a)fred.mathworks.com>...

> Yes, exactly. It will be a complicated expression in terms of the unknown x2. However you can solve it using symlinks and the matlab 'solve' command.
>
> For example (NOTE THAT x1 and x2 are replaced by l1 and l2 in my code!):
>
> J1 = (a*l1^2 + 2*b*l1*l2 + 2*d*l1 + c*l2^2 + 2*e*l2 + f)^2
>
> The first derivative in terms of l1:
> dJl1 = 4*(d + a*l1 + b*l2)*(a*l1^2 + 2*b*l1*l2 + 2*d*l1 + c*l2^2 + 2*e*l2 + f)
>
> The roots of this:
>
> root1 = -(d + b*l2)/a
> root2 = -(d + b*l2 - (b^2*l2^2 + 2*b*d*l2 + d^2 - a*c*l2^2 - 2*a*e*l2 - a*f)^(1/2))/a
> root3 = -(d + b*l2 + (b^2*l2^2 + 2*b*d*l2 + d^2 - a*c*l2^2 - 2*a*e*l2 - a*f)^(1/2))/a
>
> Solutions for l2 based on the first root:
>
> l2_1 = (b*d - a*e + a*((f*b^2 - 2*b*d*e + c*d^2 + a*e^2 - a*c*f)/a)^(1/2))/(a*c - b^2)
> l2_2 = -(a*e - b*d)/(a*c - b^2)
> l2_3 = -(a*e - b*d + a*((f*b^2 - 2*b*d*e + c*d^2 + a*e^2 - a*c*f)/a)^(1/2))/(a*c - b^2)
>
> Solutions for l1 by substituting back into root1:
>
> l1_1 = -(d + (b*(b*d - a*e + a*((f*b^2 - 2*b*d*e + c*d^2 + a*e^2 - a*c*f)/a)^(1/2)))/(a*c - b^2))/a
> l1_2 = -(d - (b*(a*e - b*d))/(a*c - b^2))/a
> l1_3 = -(d - (b*(a*e - b*d + a*((f*b^2 - 2*b*d*e + c*d^2 + a*e^2 - a*c*f)/a)^(1/2)))/(a*c - b^2))/a
>
> etc...
>
> Is there anything wrong with that?
===========

It is strange to me that for each fixed root1,2,3 the symbolic solver would obtain only a single corresponding l1_1,2,3.

Prior to substituting root1,2,3 into dJl2, you have a cubic polynomial in l2 with potentially multiple real roots for each fixed l1. Are you saying the substitution of root1,2,3 reduced the number of potential roots to one?


> How else could I approach the problem then?
=========


We already discussed an alternative in Message #15 and #28


> And wouldn't it be possible to just correct the first inconsistency you presented by summing over i in all the cases but following the same methodology ?
========

Yes, even after the correction, you would obtain 4th order polynomials for J(l1,l2) and 3rd order polynomials for its derivatives. Any method applicable to that scenario should still be applicable after the correction.
 |  Next  |  Last
Pages: 1 2
Prev: 'popupmneu' uicontrol behavior in Linux
Next: GUIDE and prgrammaticaly create GUI