Linear Programming

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.

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

Now you just have to define an order in vectors...

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

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.

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

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

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...

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...