[ODE] Simplex Solver?

[Achim Moller]

Richard, thanks a lot for your answer.

> 
> > 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
> _______________________________________________
> ODE mailing list
> ODE at q12.org
> http://q12.org/mailman/listinfo/ode
>