# Newton's method with inequality constraint

• Denise00
In summary, the conversation is discussing a problem involving projecting a point onto an ellipsoid shape, with a constraint that the absolute value of each component must be smaller than one. Different methods are suggested, such as finding a better starting guess, changing variables, or limiting the maximum step in each iteration. However, the problem is complex and cannot be simplified to a basic projection. It is suggested to focus on finding the final converged solution rather than the path taken to get there. Additionally, transforming the equation into cylindrical polar coordinates may be helpful in solving the problem.

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

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.

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

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.

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

Denise00 said:
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?

## 1. What is "Newton's method with inequality constraint"?

"Newton's method with inequality constraint" is a numerical optimization algorithm used to find the minimum or maximum value of a function, subject to one or more inequality constraints. It is an extension of the classic Newton's method, which is used to find the root of a function.

## 2. How does "Newton's method with inequality constraint" work?

The algorithm works by iteratively updating an initial guess for the minimum (or maximum) value of the function, while also satisfying the given inequality constraints. At each iteration, the algorithm uses the second derivative of the function to determine the direction of steepest descent (or ascent) and adjusts the guess accordingly. This process continues until the algorithm converges on a solution that satisfies the constraints.

## 3. What are the advantages of using "Newton's method with inequality constraint"?

One major advantage is that it is a fast and efficient algorithm, particularly for functions with a large number of variables. It also guarantees convergence to a local minimum or maximum, unlike other optimization methods that may only find a stationary point. Additionally, it allows for the incorporation of inequality constraints, which may be necessary in many real-world optimization problems.

## 4. What are the limitations of "Newton's method with inequality constraint"?

One limitation is that the algorithm may not converge if the initial guess is too far from the true solution, or if the function is not well-behaved (i.e. has discontinuities or sharp edges). Additionally, it may only find a local minimum or maximum, rather than the global optimum, depending on the starting point and the function itself.

## 5. In what fields is "Newton's method with inequality constraint" commonly used?

This algorithm is commonly used in fields such as engineering, economics, and machine learning, where optimization problems with inequality constraints are prevalent. It is also used in various applications of mathematics and computer science, such as image processing and data analysis.