2
$\begingroup$

I know some methods to solve nonlinear system of equaltites: Relaxation Method, Newton method, nonlinear Jacobi method, nonlinear Seidel method. Is it exist some analogous method to solve nonlinear systems of inequaltites?

$\endgroup$
1
$\begingroup$

Evidently, there is. In Mathematica, for example:

intervals = Reduce[Sin[8 x]/x^2 <= x, x]
NumberLinePlot[intervals, x]

(* Out: 
   Root[{-Sin[8 #1] + #1^3 &, -0.99738748628764884151}] <= x <= 
     Root[{-Sin[8 #1] + #1^3 &, -0.87854419062296271449}] || 
   Root[{-Sin[8 #1] + #1^3 &, -0.38553220443841061998}] <= x < 0 || 
   Root[{-Sin[8 #1] + #1^3 &, 0.38553220443841061998}] <= x <= 
     Root[{-Sin[8 #1] + #1^3 &, 0.87854419062296271449}] || 
   x >= Root[{-Sin[8 #1] + #1^3 &, 0.99738748628764884151}]
*)

enter image description here

The technique, I believe, is based on root isolation followed by a simple interval check.

Systems of inequalities can often be decomposed into sequences of inequalities involving increasing number of variables - the so called cylindrical algebraic decomposition. This is a fundamental technique in computer algebra and, while it is immediately applied to systems of polynomials, it can be extended in some cases to more general equations. For example:

Reduce[
  x^2 + y^2 < 1 && Sin[x + y] < 1/2,
  {x, y}
]

(* Out: (-1 < x < Pi/12 - Sqrt[72 - Pi^2]/12 && 
  -Sqrt[1 - x^2] <= y <= Sqrt[1 - x^2]) || 
  (Pi/12 - Sqrt[72 - Pi^2]/12 <= x < Pi/12 + Sqrt[72 - Pi^2]/12 &&
  -Sqrt[1 - x^2] <= y < 1/6 (Pi - 6 x))
*)

Now, for a given $x$ value, the problem reduces to a single variable problem.

$\endgroup$
  • $\begingroup$ It is rather straightforward method for one inequality, but as I think it's ok. Thanks. $\endgroup$ – bruziuz Mar 25 '15 at 11:22
  • $\begingroup$ As I mentioned in question I'm interesting in "solve nonlinear system" without optimisation objective. What methods are exist for it? $\endgroup$ – bruziuz Mar 25 '15 at 11:26
  • $\begingroup$ What kind of object would the "solution" of this non-linear system be? $\endgroup$ – LutzL Mar 25 '15 at 12:26
  • 1
    $\begingroup$ @LutzL A conjunction of inequalities such as the one produced by the second Reduce command in the answer seems ideal to me, though your question might be better posed to the OP. $\endgroup$ – Mark McClure Mar 25 '15 at 12:31
1
$\begingroup$

I'm answering from my question after couple years....

Yes, there are various ways to solve numerically objective plus inequalities.

But what is deeply wrong in question is that word non-linearity should not bring panic, in fact the problem is not in linear/non-linear but in convex/non-convex. In USSR it was realized in 1960, in USA approximately at same years.

And there areas outside math. optimization which are still think that problem is in "non-linearity".

For convex optimization problem there are a bunch of methods (e.g. interior point method, penalty method, projective subgradients).

For non-convex problems precise methods don't exist but there are two ways to handle it:

  1. Forget about non-convexity and convexify problem locally in some way 1.a DCCP(convex concave programming) - represent objective/constraint functions as convex-convex and then remove concave part or represent it via affine approximation at point. 1.b Just use convex methods and feed non-convex inequality or objective 1.c Fit convex approximation for objective and constraint via particle method 1.d Use penalty method and pull containts into objective 1.d Create you own

  2. Use global methods like branch-and-bound which are leveraged in convex optimization step, but they are usually computanionally very hard (even for small dimensions).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.