Jump to content
  • Advertisement
Sign in to follow this  
Dirk Gregorius

Linear Programming

This topic is 4882 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Dear group, is it possible to handle the following problem: A*x > b and x > 0 as a linear optimisation problem? Hence that there is no objective function. Actually I am actually only intersseted in *one* arbitrary feassible solution not the optimal solution. Any resources/papers/tips are appreciated... Regards, -Dirk PS: The background is physical based modeling, more precisly contact handling. I am aware that this can be solved as an LCP, but I am interessted in the above problem and its solution.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
A*x > b and x > 0

What are all those letters? Variables? Constants? Which is which?

If you want to satisfy a set of semilinear constrains, just provide the linear programming library with any linear function to optimize.

Share this post


Link to post
Share on other sites
Sorry!

'A' is a square matrix (in my case symmetric positive semi-definit). 'b' is a column vector of constants and 'x' is a column vector of variables...

Regards,

-Dirk

Share this post


Link to post
Share on other sites
Sorry, I don't understand what you mean. English is not my native language as well. Maybe you can be a bit more precise. If I understand linear programming correctly every vertex of the constraint domain is a feasible point. So can I simply try to find one feasible point?

The problem I am in is how I come from the classical velocity constrained formulation of Stewart/Trinkle and Anitescu where I solve the mixed LCP using Lemkes' algorithm to the degenerated form where the outgoing relative normal velocity at the contact point is no more treated as an unknown.

Regards,

-Dirk

Share this post


Link to post
Share on other sites
Yes it is possible.

Assume you are using a LP solver.
Your problem can be understand as:
- objective: find one feasible solution
- subject to: A*x>=b+epsilon, x>=epsilon
where epsilon is some vector near vector 0 and greater than 0. To make it simple, replace a member of an all-zeros vector by 1e-8 or whatever. Then you place it in the solver and get the thing you want. If the solver doesn't accept "find one feasible solution" objective then replace the objective as minimize x(i) with whatver index i you want.

Assume you want to do it "by hand", then it's also easy. In the "pertubation form", add in some arbitrary variable then solve the new LP with objective max(sum(newLP_var)). The solution of this LP is a feasible solution of the original LP problem. If you knew LP before then you should already know this method.

Share this post


Link to post
Share on other sites
Thanks for the reply. This gets me forward. Two questions

a) What is the "pertubation form" (I will google for it as well)
b) "max(sum(newLP_var))": Is this method what the projective solvers like Projective Gauss-Seidel, Projected SOR, etc, do?

Any papers/links/etc would be appreciated...

-Dirk

Share this post


Link to post
Share on other sites
a) Sorry that I confused you. The so-called "pertubated form" is actually the formula I posted. In LP you can not deal with the ">" sign. You have to add a "epsilon" vector to make it return to standard LP, or purely contain only ">=" or "<=" signs.

b) "max(sum(newLP_var))". That is just my notation? It's just the "new objective" in the "new LP" that you have to solve to get the initial solution of your LP, or one feasible solution you want.

These simplex stuffs are basically basic :) and you can find it in any simplex textbook. For a quick reference look here http://ocw.mit.edu/NR/rdonlyres/Sloan-School-of-Management/15-093Fall-2004/728EAF01-18E5-4C81-952C-1DCDD54B4B50/0/lecture04.pdf

Share this post


Link to post
Share on other sites
I assume those greater-thans mean greater-than-in-norm? Which norm?

It just isn't clear to me exactly what you are looking for. Restate please?

You want to find a vector x such that norm(adjoint(A)x) > norm(b), where norm(x)>0? Obviously that last part is practically always true...

Share this post


Link to post
Share on other sites
Given a subjective function f and a set of constraints A*x + b = 0. Linear Programming is about two subjects. First find a set of feasibel points. Second find one or more optimal solutions from this set of feasible points. So what I am looking for is only finding a set of feasible points for a system of constraint equations _without_ a subjective function:

A*x + b >= 0
x >= 0

Here A is a symmetric semi positive-definite matrix (in my case) and b is a column vector.

Regards,

-Dirk

PS: I think I am trying to find the bridge from linear programming to LCP. It seems as if solving LCP is some kind of advanced Simplex Method...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!