Newton's method with inequality constraint

[Denise00]

Dear all,

Consider the system given by : http://www.freeimagehosting.net/image.php?53f7eed9ce.jpg

where we are trying to solve for s and gamma using Newton's method. It turns out to be a simple implementation. Now, what if we need to impose an inequality constraint on the solution s : one of the form norm(s) <= 1 .

Is there a simple way to proceed by modifying a little bit the initial system? Or do we have to reformulate the problem using Lagrange multipliers or other similar methods? Many thanks for your input

Sincerely

 

[AlephZero]

It would help if you told us what equations you want to solve. The link seems to be showing how you tried to solve them with Newton's method.

It's often easier to answer a question if you know what the question is, not just an attempt at solving it.

 

[Denise00]

HI there,

Here are more information : I am trying to project a point onto an ellipsoid type of shape. The equation is given by f(x,y,z) = y^2 + z^2 - (1- x^2)^2 .

I would like to project any random point (x,y,z) onto this surface, but my only constraint is that I must have the absolute value of each component to be smaller than one : abs(x) <=1 , abs(y) <= 1 and abs(z) <= 1

Here is an illustration of my problem : http://www.freeimagehosting.net/image.php?632fa92cea.png

I do find a point satisfying f(x,y,z) = 0 (on the surface), but not in the appropriate range. How could I modify my Newton's algorithm to converge to the appropriate solution?

Thanks

 

[AlephZero]

I guess the problem is that in some sense there are multiple roots of your "projection" equations, and Newton-Raphson is converging to the wrong one, outside the range you want.

Some things you could try:

1 Find a better starting guess. For example draw a line from your point to the origin and find the intersection of that line with the surface.

2 Find a different way to represent just the part of the surface that you want. For eaxmple change variables so x = sin t or something similar.

3 Limit the maximum step that you can take in one iteration (say to 0.1, looking at your picture) so you can't "jump" onto the wrong part of the surface.

When it fails, print out all the iterations and see if you can figure out geometrically why it failed (analogous to showing how Newton's method works for a single variable by drawing tangents to the curve representing the function). That might suggest a way to fix it.

 

[Denise00]

None of these "fixes" will do the trick. As I mentioned, it's a plasticity problem, the initial step is an "elastic trial" that can be (often is) outside of the ellipsoid right off the bat.
The complexity of the problem is associated both with the fact that we are trying to satisfy equilibrium and land on the surface. They have to be solved simultaneously ... and it can't be simplified to a basic projection.

Anyways, thanks for taking the time to answer

 

[AlephZero]

The complexity of the problem is associated both with the fact that we are trying to satisfy equilibrium and land on the surface. They have to be solved simultaneously ... and it can't be simplified to a basic projection.

You can get a starting point for your iterative solution in any way you like. You don't have to be constrained by the physics of the situation. If starting from a point way off the ellipsoid doesn't work, try starting from close to it - for example pick any point on it, in the correct octant. The only thing that matters in nonlinear equation solution is the final converged solution. It doesn't matter what path you take to get there, so long as you DO get there.

Your equation f(x,y,z) = y^2 + z^2 - (1- x^2)^2 has cylindrical symmetry. Does it help to transform into cyliindrical polar coordiates x, r, theta? If you do that, can you eliminate theta by projection and just iterate to solve for x and r?