find a point with constraint --URGENT--

OpenGL
1

Here is my problem:

I have to find the best position of a point respecting some constraint.

The point should be “above” N plane.
So it should respect theses inequation:
a1x + b1y +c1z + d1 > 0
a2x + b2y +c2z + d2 > 0
a3x + b3y +c3z + d3 > 0
.
.
.
.
anx + bny + cnz + dn > 0

Thats the first constraint.
The plane are always defining an existing volume, but this volume is not necessary closed.

The second constraint is that the solution point have to be the closest point to another out of the volume.
ie: the distance between my reference point and the solution point should be the smaller possible.

I have to solve this system numerically.

Please heeelp :wink:

PS: I know… I need to improve my english level :wink:

2

This is an optimization problem with a quadratic constraint.

Take a look at http://www.lindo.com

Here’s an extract of their lindo API:

LINDO API provides you with an arsenal of powerful solvers for linear, nonlinear (convex & nonconvex), quadratic, quadratically constrained, and integer optimization. All solvers incorporate numerous enhancements for maximum speed and robustness.

Greetz,

Nico

3

Unfortunatly i can’t use LINDO in my program :frowning:

Are u sure that’s not a linear problem ?

4

The contraints are linear, but your objective function(mininum distance from a given point) is not.
Why is it urgent anyway??

5

yes u are right that’s not linear

this is urgent coz i’ve to implement this within a week :frowning:

Apparently i can use the Karush-Kuhn-Tucker conditions to solve my problem(even if its seem hard to implement…)

6

You can easily redefine the problem as multiple linear problems.
Some logic reasoning will show that the optimal solution has to be on at least one of the planes you used as constraints.

So a linear version of the code you supplied can be redefined as:

Original:

a1x + b1y +c1z + d1 > 0
a2x + b2y +c2z + d2 > 0
a3x + b3y +c3z + d3 > 0
.
anx + bny + cnz + dn > 0

Linear:

for i=1:n

Optimize for

objective function:
aix + biy + ciz + di = 0

constraints:
a1x + b1y +c1z + d1 > 0
.
a(i-1)x + b(i-1)y +c(i-1)z + d(i-1) > 0
.
a(i+1)x + b(i+1)y +c(i+1)z + d(i+1) > 0
.
anx + bny + cnz + dn > 0

store local optimal point:
(xi,yi,zi)

endfor

check all local optimal points and choose closest as the global optimal point.

I’m sure there will be some other optimizations you can perform for faster convergence of the algorithm.

Greetz,

Nico

7

ok i’ll try that…sounds good

thanks