Inmathematics,nonlinear programming (NLP) is the process of solving anoptimization problem where some of the constraints are notlinear equalities or the objective function is not alinear function. Anoptimization problem is one of calculation of the extrema (maxima, minima or stationary points) of anobjective function over a set of unknownreal variables and conditional to the satisfaction of asystem ofequalities andinequalities, collectively termedconstraints. It is the sub-field ofmathematical optimization that deals with problems that are not linear.
Letn,m, andp be positive integers. LetX be a subset ofRn (usually a box-constrained one), letf,gi, andhj bereal-valued functions onX for eachi in {1, ...,m} and eachj in {1, ...,p}, with at least one off,gi, andhj being nonlinear.
A nonlinear programming problem is anoptimization problem of the form
Depending on the constraint set, there are several possibilities:
Most realistic applications feature feasible problems, with infeasible or unbounded problems seen as a failure of an underlying model. In some cases, infeasible problems are handled by minimizing a sum of feasibility violations.
Some special cases of nonlinear programming have specialized solution methods:
A typical non-convex problem is that of optimizing transportation costs by selection from a set of transportation methods, one or more of which exhibiteconomies of scale, with various connectivities and capacity constraints. An example would be petroleum product transport given a selection or combination of pipeline, rail tanker, road tanker, river barge, or coastal tankship. Owing to economic batch size the cost functions may have discontinuities in addition to smooth changes.
In experimental science, some simple data analysis (such as fitting a spectrum with a sum of peaks of known location and shape but unknown magnitude) can be done with linear methods, but in general these problems are also nonlinear. Typically, one has a theoretical model of the system under study with variable parameters in it and a model the experiment or experiments, which may also have unknown parameters. One tries to find a best fit numerically. In this case one often wants a measure of the precision of the result, as well as the best fit itself.
Underdifferentiability andconstraint qualifications, theKarush–Kuhn–Tucker (KKT) conditions provide necessary conditions for a solution to be optimal. If some of the functions are non-differentiable,subdifferential versions ofKarush–Kuhn–Tucker (KKT) conditions are available.[1]
Under convexity, the KKT conditions are sufficient for aglobal optimum. Without convexity, these conditions are sufficient only for alocal 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.[2]
In most realistic cases, it is very hard to solve the KKT conditions analytically, and so the problems are solved usingnumerical 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:[2]: 5.1.2
Third-order routines (and higher) are theoretically possible, but not used in practice, due to the higher computational load and little theoretical benefit.
Another method involves the use ofbranch 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.
There exist numerous nonlinear programming solvers, including open source:
A simple problem (shown in the diagram) can be defined by the constraintswith an objective function to be maximizedwherex = (x1,x2).
Another simple problem (see diagram) can be defined by the constraintswith an objective function to be maximizedwherex = (x1,x2,x3).
|  | |||||||||||||||||
| ||||||||||||||||||
| ||||||||||||||||||
| ||||||||||||||||||
