[ODE] Simplex Solver?

[Richard Tonge]

> Hi,
> 
> sometimes, in papers about rigid body systems, the
authors mention the
> usage
> of "Simplex Methods" for solving linear programs
(?).
> 
> Can this also be applied to ODE? Why or why not?
> 
> Also, some authors mention usage of the 'Conjugate
Gradient' methods
> (which
> currently is commented out in 'quickstep.cpp').
> 
> Why does this also not work with ODE?
> 
> Thanks a lot for some explanation from the math
wizards around here!

Hi,

There are a few different topics mentioned in your
email, some of them are applicable to ODE, and some
are not. I've not worked on this stuff for a while
now, but this is what I recall. 

Linear programming is all about minimizing a linear
function subject to equality and or inequality
constraints.

eg. minimize cx subject to Ax+b=0 and x>=0

The simplex method is a way of solving linear
programs.

A linear system has the form
find x such that Ax=b. The conjugate gradient method
is a method of solving linear systems.

Now, what ODE solves can either be thought of as a
quadratic programming problem, or as an LCP.

The quadratic program solved by ODE can be written in
the form minimize f(x) = x'Ax+bx+b'b such that
lo<=x<=hi

You say that you've seen the simplex method applied to
rigid body methods. As far as I know, as ODE is
currently formulated as a QP, the simplex method for
LP cannot be directly applied. The reason it is a QP
is that ODE minimizes work done (in the constraint
space) and this is a quadratic function of
displacement (in constraint space). I am interested to
know how rigid body can be formulated as a linear
program though.

The standard conjugate gradient method is a method for
solving linear systems, Ax=b where A is s.p.d. It is
true that some QP and LCP solvers reduce to a sequence
of problems of this form, but it cannot be used to
solve the whole problem.
However, solving a linear system is equivalent to
minimizing a quadratic function (see Shewchuck's
introduction to conjugate gradient for details). You
could use this observation to modify the basic
conjugate gradient algorithm to respect the limits as
it descends down the function. I've never tried this
though, the details are probably difficult.

Richard Tonge



	
	
		
___________________________________________________________ALL-NEW Yahoo! Messenger - all new features - even more fun!  http://uk.messenger.yahoo.com