Nonlinear programming

In mathematics, nonlinear programming (NLP), also known as nonlinear optimization , is the process of solving an optimization problem where some of the constraints are not linear equalities or the objective function is not a linear function. An optimization problem is one of calculation of the extrema (maxima, minima or stationary points) of an objective function over a set of unknown real variables and conditional to the satisfaction of a system of equalities and inequalities, collectively termed constraints. It is the sub-field of mathematical optimization that deals with problems that are not linear.

In mathematics, nonlinear programming (NLP), also known as nonlinear optimization , is the process of solving an optimization problem where some of the constraints are not linear equalities or the objective function is not a linear function. An optimization problem is one of calculation of the extrema (maxima, minima or stationary points) of an objective function over a set of unknown real variables and conditional to the satisfaction of a system of equalities and inequalities, collectively termed constraints. It is the sub-field of mathematical optimization that deals with problems that are not linear. & h_j(x) = 0 \text{ for each } j \in \{1, \dotsc, p\} \\ & x \in X. \end{align} Depending on the constraint set, there are several possibilities: feasible problem is one for which there exists at least one set of values for the choice variables satisfying all the constraints. an infeasible problem is one for which no set of values for the choice variables satisfies all the constraints. That is, the constraints are mutually contradictory, and no solution exists; the feasible set is the empty set. unbounded problem is a feasible problem for which the objective function can be made to be better than any given finite value. Thus there is no optimal solution, because there is always a feasible solution that gives a better objective function value than does any given proposed solution. 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: If the objective function is concave (maximization problem), or convex (minimization problem) and the constraint set is convex, then the program is called convex and general methods from convex optimization can be used in most cases. If the objective function is quadratic and the constraints are linear, quadratic programming techniques are used. If the objective function is a ratio of a concave and a convex function (in the maximization case) and the constraints are convex, then the problem can be transformed to a convex optimization problem using fractional programming techniques. ==Applicability== A typical non-convex problem is that of optimizing transportation costs by selection from a set of transportation methods, one or more of which exhibit economies 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. ==Implementations== There exist numerous nonlinear programming solvers, including open source: ALGLIB (C++, C#, Java, Python API) implements several first-order and derivative-free nonlinear programming solvers NLopt (C/C++ implementation, with numerous interfaces including Julia, Python, R, MATLAB/Octave), includes various nonlinear programming solvers SciPy (de facto standard for scientific Python) has scipy.optimize solver, which includes several nonlinear programming algorithms (zero-order, first order and second order ones). IPOPT (C++ implementation, with numerous interfaces including C, Fortran, Java, AMPL, R, Python, etc.) is an interior point method solver (zero-order, and optionally first order and second order derivatives). Proprietary solvers include SNOPT (written in Fortran, with interfaces to C, C++, Python and MATLAB). ==Numerical Examples== ===2-dimensional example=== . The tangency of the line with the feasible region represents the solution. The line is the best achievable contour line (locus with a given value of the objective function).]] A simple problem (shown in the diagram) can be defined by the constraints \begin{align} x_1 &\geq 0 \\ x_2 &\geq 0 \\ x_1^2 + x_2^2 &\geq 1 \\ x_1^2 + x_2^2 &\leq 2 \end{align} with an objective function to be maximized f(\mathbf x) = x_1 + x_2 where . ===3-dimensional example=== Another simple problem (see diagram) can be defined by the constraints \begin{align} x_1^2 - x_2^2 + x_3^2 &\leq 2 \\ x_1^2 + x_2^2 + x_3^2 &\leq 10 \end{align} with an objective function to be maximized f(\mathbf x) = x_1 x_2 + x_2 x_3 where . ==See also== Curve fitting Least squares minimization Linear programming nl (format) Nonlinear least squares List of optimization software Quadratically constrained quadratic programming Werner Fenchel, who created the foundation for nonlinear programming ==References== ==Further reading== Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. . Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. . Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. . Jan Brinkhuis and Vladimir Tikhomirov, Optimization: Insights and Applications, 2005, Princeton University Press ==External links== Mathematical Programming Glossary

Text derived from https://en.wikipedia.org/w/index.php?oldid=1348815621 under CC BY-SA 4.0; modifications have been made.