Editing Nonlinear programming (section)

== Methods for solving a general nonlinear program ==

=== Analytic methods ===
Under [[differentiability]] and [[constraint qualification]]s, the [[Karush–Kuhn–Tucker conditions|Karush–Kuhn–Tucker (KKT) conditions]] provide necessary conditions for a solution to be optimal. If some of the functions are non-differentiable, [[subderivative|subdifferential]] versions of [[Karush–Kuhn–Tucker conditions|Karush–Kuhn–Tucker (KKT) conditions]] are available.<ref>
{{cite book |last=Ruszczyński |first=Andrzej |title=Nonlinear Optimization |publisher=[[Princeton University Press]] |year=2006 |isbn=978-0691119151 |location=Princeton, NJ |pages=xii+454 |mr=2199043 |author-link=Andrzej Piotr Ruszczyński}}</ref>

Under convexity, the KKT conditions are sufficient for a [[global optimum]]. Without convexity, these conditions are sufficient only for a [[local optimum]]. In some cases, the number of local optima is small, and one can find all of them analytically and find the one for which the objective value is smallest.<ref name=":0">{{Cite web |last=Nemirovsky and Ben-Tal |date=2023 |title=Optimization III: Convex Optimization |url=http://www2.isye.gatech.edu/~nemirovs/OPTIIILN2023Spring.pdf}}</ref>

=== Numeric methods ===
In most realistic cases, it is very hard to solve the KKT conditions analytically, and so the problems are solved using [[Numerical analysis|numerical methods]]. These methods are iterative: they start with an initial point, and then proceed to points that are supposed to be closer to the optimal point, using some update rule. There are three kinds of update rules:<ref name=":0" />{{Rp|location=5.1.2}}

* Zero-order routines - use only the values of the objective function and constraint functions at the current point;
* First-order routines - use also the values of the ''[[gradient]]s'' of these functions;
* Second-order routines - use also the values of the [[Hessian matrix|''Hessians'']] of these functions.

Third-order routines (and higher) are theoretically possible, but not used in practice, due to the higher computational load and little theoretical benefit.

=== Branch and bound ===
Another method involves the use of [[branch and bound]] techniques, where the program is divided into subclasses to be solved with convex (minimization problem) or linear approximations that form a lower bound on the overall cost within the subdivision. With subsequent divisions, at some point an actual solution will be obtained whose cost is equal to the best lower bound obtained for any of the approximate solutions. This solution is optimal, although possibly not unique. The algorithm may also be stopped early, with the assurance that the best possible solution is within a tolerance from the best point found; such points are called ε-optimal. Terminating to ε-optimal points is typically necessary to ensure finite termination. This is especially useful for large, difficult problems and problems with uncertain costs or values where the uncertainty can be estimated with an appropriate reliability estimation.