Thread Subject: Please save my master thesis! Need help with optimisation! URGENT

Hi all!
I'm really desperate now! I've been working on my master
thesis in electrical engineering for 4 months now and I have
only 6 weeks left!!! And now I have to discover that my
whole system doesn't work.

The whole thing is about landmark navigation for satellites.
I have a nonlinear equation that has to be minimized to find
6 unknown variables: a vector for position and three angles.

You can download a sketch of the problem here:
www.wh10.tu-dresden.de/~vklink/uni/MatLabProblem.pdf

Therefore I wrote this function, using fminunc to solve this
problem:
www.wh10.tu-dresden.de/~vklink/uni/FindPos1.m

The m-File is very well commented to help you understand the
problem. But if you have any questions let me know.

I've played around with several parameters, also tried
fminsearch but I just can't figure out why this is not working!

I did a lot of research on how my function reacts to
different situations..iwth the result that I only get decent
results (still with an absolute error of ~ 0.1 - 1
millidegree )if I call my function with an ideal x0!

I tried to run it with a reduced number of unknown
variables, e.g. assuming that the position is known. But no
success.
I'm just running out of ideas!

Are there any specialists out there who have ideas what
could be wrong with my code or the general approach??? Do
you know a better way to minimize the function?

Please let me know!
Thanks in advance for your support!
Volker

Hi Volker,

I would guess, that your objective function isn't smooth at
all because of that rotary matrix. You could plot part of
it to get the right feeling for the problem.
So, the algorithm probably gets stuck in an local optimum.

You could try a global optimization approach e.g. genetic
algorithm or particle swarm search.

Maybe this
http://www.norg.uminho.pt/aivaz/pswarm/
or that
http://www4.ncsu.edu/~ctk/Finkel_Direct/
or
http://www.mathworks.com/matlabcentral/fileexchange/
loadFile.do?objectId=18342&objectType=file

You could also search for branch-and-bound type algorithms.
They are also cappable of finding a global optimum.

Regards,
Stefan

"Volker Klink" <klinkv.NOSPAM@yahoo.de> wrote in message
<ftj4r5$h5j$1@fred.mathworks.com>...
> Hi all!
> I'm really desperate now! I've been working on my master
> thesis in electrical engineering for 4 months now and I
have
> only 6 weeks left!!! And now I have to discover that my
> whole system doesn't work.
>
> The whole thing is about landmark navigation for
satellites.
> I have a nonlinear equation that has to be minimized to
find
> 6 unknown variables: a vector for position and three
angles.
>
> You can download a sketch of the problem here:
> www.wh10.tu-dresden.de/~vklink/uni/MatLabProblem.pdf
>
> Therefore I wrote this function, using fminunc to solve
this
> problem:
> www.wh10.tu-dresden.de/~vklink/uni/FindPos1.m
>
> The m-File is very well commented to help you understand
the
> problem. But if you have any questions let me know.
>
> I've played around with several parameters, also tried
> fminsearch but I just can't figure out why this is not
working!
>
> I did a lot of research on how my function reacts to
> different situations..iwth the result that I only get
decent
> results (still with an absolute error of ~ 0.1 - 1
> millidegree )if I call my function with an ideal x0!
>
> I tried to run it with a reduced number of unknown
> variables, e.g. assuming that the position is known. But
no
> success.
> I'm just running out of ideas!
>
> Are there any specialists out there who have ideas what
> could be wrong with my code or the general approach??? Do
> you know a better way to minimize the function?
>
> Please let me know!
> Thanks in advance for your support!
> Volker

Hi Volker,

I would guess, that your objective function isn't smooth at
all because of that rotary matrix. You could plot part of
it to get the right feeling for the problem.
So, the algorithm probably gets stuck in an local optimum.

You could try a global optimization approach e.g. genetic
algorithm or particle swarm search.

Maybe this
http://www.norg.uminho.pt/aivaz/pswarm/
or that
http://www4.ncsu.edu/~ctk/Finkel_Direct/
or
http://www.mathworks.com/matlabcentral/fileexchange/
loadFile.do?objectId=18342&objectType=file

You could also search for branch-and-bound type algorithms.
They are also cappable of finding a global optimum.

Regards,
Stefan

"Volker Klink" <klinkv.NOSPAM@yahoo.de> wrote in message
<ftj4r5$h5j$1@fred.mathworks.com>...
> Hi all!
> I'm really desperate now! I've been working on my master
> thesis in electrical engineering for 4 months now and I
have
> only 6 weeks left!!! And now I have to discover that my
> whole system doesn't work.
>
> The whole thing is about landmark navigation for
satellites.
> I have a nonlinear equation that has to be minimized to
find
> 6 unknown variables: a vector for position and three
angles.
>
> You can download a sketch of the problem here:
> www.wh10.tu-dresden.de/~vklink/uni/MatLabProblem.pdf
>
> Therefore I wrote this function, using fminunc to solve
this
> problem:
> www.wh10.tu-dresden.de/~vklink/uni/FindPos1.m
>
> The m-File is very well commented to help you understand
the
> problem. But if you have any questions let me know.
>
> I've played around with several parameters, also tried
> fminsearch but I just can't figure out why this is not
working!
>
> I did a lot of research on how my function reacts to
> different situations..iwth the result that I only get
decent
> results (still with an absolute error of ~ 0.1 - 1
> millidegree )if I call my function with an ideal x0!
>
> I tried to run it with a reduced number of unknown
> variables, e.g. assuming that the position is known. But
no
> success.
> I'm just running out of ideas!
>
> Are there any specialists out there who have ideas what
> could be wrong with my code or the general approach??? Do
> you know a better way to minimize the function?
>
> Please let me know!
> Thanks in advance for your support!
> Volker

Thanks Stefan!

Thanks for your help.
I'll check it out...my first impression was that these
algorithms are quite different to the ones I use.
First I have to figure out how to apply them!
Volker

Hi Volker,

Please send me a test case that can be run and I will take a look.

There are many options to look at, glcCluster, LGO, OQNLP, multiMin
and so on: http://tomopt.com/tomlab/products/

Best wishes, Marcus
Tomlab Optimization Inc.
http://tomopt.com/

> Please send me a test case that can be run and I will take
a look.
>
> There are many options to look at, glcCluster, LGO, OQNLP,
multiMin
> and so on: http://tomopt.com/tomlab/products/
>
Thanks for the thoughts! I'll prepare some data for you!

On Apr 9, 12:19 pm, "Volker Klink" <klinkv.NOS...@yahoo.de> wrote:
> Hi all!
> I'm really desperate now! I've been working on my master
> thesis in electrical engineering for 4 months now and I have
> only 6 weeks left!!! And now I have to discover that my
> whole system doesn't work.
>
> The whole thing is about landmark navigation for satellites.
> I have a nonlinear equation that has to be minimized to find
> 6 unknown variables: a vector for position and three angles.
>
> You can download a sketch of the problem here:www.wh10.tu-dresden.de/~vklink/uni/MatLabProblem.pdf
>
> Therefore I wrote this function, using fminunc to solve this
> problem:www.wh10.tu-dresden.de/~vklink/uni/FindPos1.m
>
> The m-File is very well commented to help you understand the
> problem. But if you have any questions let me know.
>
> I've played around with several parameters, also tried
> fminsearch but I just can't figure out why this is not working!
>
> I did a lot of research on how my function reacts to
> different situations..iwth the result that I only get decent
> results (still with an absolute error of ~ 0.1 - 1
> millidegree )if I call my function with an ideal x0!
>
> I tried to run it with a reduced number of unknown
> variables, e.g. assuming that the position is known. But no
> success.
> I'm just running out of ideas!
>
> Are there any specialists out there who have ideas what
> could be wrong with my code or the general approach??? Do
> you know a better way to minimize the function?
>
> Please let me know!
> Thanks in advance for your support!
> Volker

Hi, Volker.

If I understand your problem correctly, you are trying to determine
the location and orientation of a satellite that minimizes the "look-
angle-error" between the satellite and a number of ground stations. I
think you may have too much freedom for the satellite in your
formulation. For example, suppose you rotate the satellite so as to
point the satellite z-axis towards a particular location on the
earth. Then any rotation of the satellite about this (new) z-axis
does not change the pointing of the satellite, hence does not change
the cost function. So you really only have two axes (or directions)
that you should be optimizing over. Similarly, are you really free to
change the satellite altitude? Typically the altitude is fixed and
only the orbital location at that particular altitude can be changed.
Thus, your three parameters Input(1:3) representing the Cartesian
coordinates of the satellite could be replaced by a pair of angles
(lat and long). This restriction seems to be necessary since
otherwise you could drive your cost function to zero simply by
increasing the altitude of the satllite, thus driving all the vectors
to being nearly parallel.
It also seems to me that you could estimate the optimum solution very
easily: pick the satellite location to be along the vector that is
the mean of the ground station location vectors, and point the
satellite towards the nadir location (the center of the earth). That
should give you a good starting point for your optimization, which
could be critical in achieving convergence.

Also, instead of forming the cost function from the difference of the
unit vectors, I would use a more direct angular error measure: from
the arccosine of the dot products of the unit vectors obtain the
actual angular errors and minimize their squared sum.

Hope this helps,
Peter Simon

> If I understand your problem correctly, you are trying to
determine the location and orientation of a satellite

--> correct, but I cannot change the satellites pos/attitude.

> that minimizes the "look-angle-error" between the
satellite and a number of ground stations.

-->I don't understand this. The satellite is observing
earth. My software finds known landmarks in the satellite
picture. Therefore I know the landmarks earth locations
(Lon/Lat or vectors) AND the look vectors from the satellite
to these landmarks. The look vectors do NOT equal the
attitude of the satellite's z-axis. The image is obtained
with a line scanner so the Line of Sights are the
orientation of the scanner when pointing at a landmark.

>I think you may have too much freedom for the satellite in
your formulation. For example, suppose you rotate the
satellite so as to point the satellite z-axis towards a
particular location on the earth. Then any rotation of the
satellite about this (new) z-axis does not change the
pointing of the satellite, hence does not change the cost
function.

--> Yes it does change. If I change the attitude/position of
the satellite in any way the position of the landmarks in
the satellite image will change, therefor the Lineof
sight-vectors also change.

>Typically the altitude is fixed and only the orbital
location at that particular altitude can be changed.

-->Ideally, position and attitude of a geostationary sat are
fix but it's the goal of this system to determine the
deviation of the satellite from the ideal pos/attitude.
Therefor the system should provide a high precision for all
six degrees of freedom.

 
> Also, instead of forming the cost function from the
difference of the
> unit vectors, I would use a more direct angular error
measure: from
> the arccosine of the dot products of the unit vectors
obtain the
> actual angular errors and minimize their squared sum.

--> Good idea! I'll check that out!

Thanks a lot for your help so far.

Volker

"Volker Klink" <klinkv.NOSPAM@yahoo.de> wrote in message
<ftj4r5$h5j$1@fred.mathworks.com>...
> Hi all!
> I'm really desperate now! I've been working on my master
> thesis in electrical engineering for 4 months now and I
have
> only 6 weeks left!!! And now I have to discover that my
> whole system doesn't work.
>
> The whole thing is about landmark navigation for
satellites.
> I have a nonlinear equation that has to be minimized to
find
> 6 unknown variables: a vector for position and three
angles.
>
> You can download a sketch of the problem here:
> www.wh10.tu-dresden.de/~vklink/uni/MatLabProblem.pdf
>
> Therefore I wrote this function, using fminunc to solve
this
> problem:
> www.wh10.tu-dresden.de/~vklink/uni/FindPos1.m
>
> The m-File is very well commented to help you understand
the
> problem. But if you have any questions let me know.
>
> I've played around with several parameters, also tried
> fminsearch but I just can't figure out why this is not
working!
>
> I did a lot of research on how my function reacts to
> different situations..iwth the result that I only get
decent
> results (still with an absolute error of ~ 0.1 - 1
> millidegree )if I call my function with an ideal x0!
>
> I tried to run it with a reduced number of unknown
> variables, e.g. assuming that the position is known. But
no
> success.
> I'm just running out of ideas!
>
> Are there any specialists out there who have ideas what
> could be wrong with my code or the general approach??? Do
> you know a better way to minimize the function?
>
> Please let me know!
> Thanks in advance for your support!
> Volker

What is your actual problem? The code looks fine. I can run
the code to find the optimal solution. For example, I used

result=FindPos1(zeros(3,1),randn(3,1),rand(1,6),optimset
('display','iter'))

I got:

result =

   -0.8089 3.0450 -3.0500 1.1420 0.1518 0.9207

Yi Cao

On Apr 12, 5:08 am, "Volker Klink" <klinkv.NOS...@yahoo.de> wrote:
> > If I understand your problem correctly, you are trying to
>
> determine the location and orientation of a satellite
>
> --> correct, but I cannot change the satellites pos/attitude.
>
> > that minimizes the "look-angle-error" between the
>
> satellite and a number of ground stations.
>
> -->I don't understand this. The satellite is observing
> earth. My software finds known landmarks in the satellite
> picture. Therefore I know the landmarks earth locations
> (Lon/Lat or vectors) AND the look vectors from the satellite
> to these landmarks. The look vectors do NOT equal the
> attitude of the satellite's z-axis. The image is obtained
> with a line scanner so the Line of Sights are the
> orientation of the scanner when pointing at a landmark.
>
> >I think you may have too much freedom for the satellite in
>
> your formulation. For example, suppose you rotate the
> satellite so as to point the satellite z-axis towards a
> particular location on the earth. Then any rotation of the
> satellite about this (new) z-axis does not change the
> pointing of the satellite, hence does not change the cost
> function.
>
> --> Yes it does change. If I change the attitude/position of
> the satellite in any way the position of the landmarks in
> the satellite image will change, therefor the Lineof
> sight-vectors also change.
>
> >Typically the altitude is fixed and only the orbital
>
> location at that particular altitude can be changed.
>
> -->Ideally, position and attitude of a geostationary sat are
> fix but it's the goal of this system to determine the
> deviation of the satellite from the ideal pos/attitude.
> Therefor the system should provide a high precision for all
> six degrees of freedom.
>
>
>
> > Also, instead of forming the cost function from the
> difference of the
> > unit vectors, I would use a more direct angular error
> measure: from
> > the arccosine of the dot products of the unit vectors
> obtain the
> > actual angular errors and minimize their squared sum.
>
> --> Good idea! I'll check that out!
>
> Thanks a lot for your help so far.
>
> Volker

OK, I misunderstood what you were trying to do.

One other item that comes to mind is scaling of the variables. Within
Input, three of the entries are lengths having some unknown (to me)
units and the other three are angles. Often, it is necessary to scale
the optimization degrees of freedom (i.e. independent variables) so
that they are all roughly of the same order of magnitude to prevent
problems in the optimizer. For example, you could scale the variables
so that they all take values between -1 and 1 (or whatever). Right
now, if the location vector has units of, say, kilometers, and the
angles are in radians or degrees, you will have many orders of
magnitude difference in their values, and hence in the step sizes
needed for finite-difference approximations to derivatives that are
implemented by the optimizer. Some optimizers let you specify the
step size for each variable individually, most don't let you do this.

--Peter

Often, it is necessary to scale the optimization degrees of
freedom so that they are all roughly of the same order of
magnitude For example, you could scale the variables
> so that they all take values between -1 and 1 (or
whatever). ...if the location vector has units of
kilometers and the
> angles are in radians or degrees, you will have many
orders of magnitude difference in their values, and hence in
the step sizes needed for finite-difference approximations
to derivatives that are implemented by the optimizer.

--> Sounds very interesting!
Have to check that out as well...still have to think about,
how to scale the values.
By the way: I've already found ONE tiny bug with big effect
in my code: at some point I used a lot of single values to
save RAM (I had to load several [382 2811] matrices).
Apparently that wasn't a good idea!!!
That explained why the stuff worked with virtual
coordinates/LoS (used double) and did not work with real
coordinates/Los(-->single!!!).

Also, using the dotproduct seems to be better than using the
difference!

Right now I'm checking out, how sensitive the system is
towards noise and bad starting guesses x0. So far I can say
that a more sofisticated algorithm that can find global
minima probably would perform better. I didn't have the time
yet to get the Swarm Particle/Direct stuff to work. The
syntax is quite different to the standard MatLab optimizers.

Thanks so far!