I am trying to solve a system of non-linear algebraic systems through optimization. \(f_i(x)=0\) for \(i=1 \dots n\) and \(x \in R^n\). I saw few optimization versions: Minimize \(\sum f_i^2(x)\), Minimize \(\max(|f_i(x)|)\), multi-objective formulation.

can you please suggest which method gives more accurate solution? Are there any other methods?


asked 28 May '15, 01:49

cbot's gravatar image

accept rate: 0%

edited 28 May '15, 16:19

Paul%20Rubin's gravatar image

Paul Rubin ♦♦

Your nonlinear least squares approach has been successfully used for many decades to solve systems of nonlinear equations. The residuals at the optimum should be quite small (else the equations haven't really been "solved"). So you can use a specicalized nonlinear least squares solver which assumes small residuals at the optimum, such as Levenbeg-Marquardt, or just use a general purpose (continuous variable) nonlinear optimizer to solve the nonlinear least squares problem. Or just solve it with a nonlinear optimizer by providing only the equations to be solved as nonlinear constraints, and either no objective function or any objective function or a "fake" objective function, such as 0, and let the nonlinear optimizer find a feasible solution for you.

If employing nonlinear least squares, and the equations might not be solvable "exactly", you can even put in weights on the individual equations to change the relative amount of infeasibility each equation should have in a balanced solution,.

That said, perhaps there are specialized methods for dealing with algebraic equations (I think there are), so you might be able to do better than the more generic approaches I outlined. I think finding good starting values is the key to success if you use a local optimizer. You could also try a global optimizer such as BARON, which should be comprehensive in searching for a solution in the event that a local optimizer with your choice(s) of starting points does not find one. There are also global solvers based on branch and bound using outward-rounded interval or radial arithmetic, which given a box in R^n, achieve absolute rigor (which BARON does not achieve) in finding one or all solutions inside the box; but they may not necessarily run to completion in a time frame you find satisfactory.

If you really want to solve to super-high accuracy, and indeed you think an exact solution exists, then solve by any method I mentioned to get an "approximate solution" to some number of significant digits. Then use that as starting solution for an optimization in extended precision (quad precision or even higher) and solve it with a trust region Newton's method (quadratic convergence, and given you are starting very close to the solution, you probably don't even need the trust regions), for instance to get higher accuracy. Actually, there's a very easy way to do this in MAPLE using arbitrary precision arithmetic (which runs in SW and is slow, however), and you don't need the preliminary phase at lower precision, but you could do that and provide the solution as starting point to MAPLE if you want. Use MAPLE's fsolve (to solve as a system of nonlinear equations, not as an optimization problem), and specify as many digits of precision as you want, for instance 1000, then let MAPLE solve it for you. If your problem is not too difficult, you may get a solution accurate to hundreds, thousands, or more digits, if you want, fairly quickly. This can work quite well, because you can achieve quadratic convergence, so the number of correct digits is approximately doubled every iteration.


answered 28 May '15, 13:15

Mark%20L%20Stone's gravatar image

Mark L Stone
accept rate: 15%

edited 28 May '15, 14:16

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 28 May '15, 01:49

Seen: 1,500 times

Last updated: 28 May '15, 16:19

OR-Exchange! Your site for questions, answers, and announcements about operations research.