Nonlinear programming

Nonlinear programming (NLP) is a field of mathematical programming and operations research that deals with optimization problems where the objective function and/or at least one of the constraints are nonlinear functions of the decision variables.

NLP is a generalization of linear programming and allows for modeling a broader class of real-world systems and processes where the relationships between variables are not strictly proportional (i.e., they are described by curves rather than straight lines).

Subject and Purpose

Nonlinear programming is used to find optimal solutions in situations where:

• The relationship of the objective metric (profit, cost, efficiency, etc.) to the control parameters is nonlinear (e.g., diminishing returns to scale, quadratic costs).
• Constraints on resources or technological processes are described by nonlinear relationships (e.g., chemical reactions, physical laws, economic dependencies).

NLP problems arise in many areas:

• Engineering design (optimization of structures, processes).
• Economics and finance (portfolio optimization considering risk, market modeling).
• Chemical engineering (optimization of reactor operating modes).
• Machine learning (training neural networks, support vector machines).
• Management of production processes. Logistics (taking into account nonlinear costs).

Mathematical Formulation of an NLP Problem

A general nonlinear programming problem is formulated as follows:

The goal is to find a set of values for the decision variables that maximizes or minimizes a nonlinear objective function. At the same time, the values of these variables must satisfy a system of constraints, which can be expressed as either inequalities (e.g., "quantity A must be less than or equal to B") or equalities (e.g., "quantity C must be exactly equal to D"). Crucially, at least one of the functions describing the objective or the constraints must be nonlinear. Often, non-negativity conditions are added for the variables, i.e., the requirement that their values be greater than or equal to zero.

The set of all combinations of variable values that satisfy the constraints forms the feasible region.

Differences from Linear Programming

Nonlinear programming (NLP) differs significantly from linear programming (LP):

• Nonlinearity: The objective function or the constraints (or both) contain nonlinear relationships.
• Properties of the Feasible Region: The feasible region in NLP can be non-convex (unlike in LP, where the feasible region is always a convex polytope).
• Properties of the Optimum: The optimal solution in NLP is not necessarily located at a vertex of the feasible region; it can lie on the boundary or within the interior of the region. In NLP, there can be local optima that are not global optima.
• Solution Complexity: NLP problems are generally much more difficult to solve than LP problems. There is no single universal algorithm, analogous to the simplex method, for all NLP problems.

Main Difficulties and Challenges of NLP

Solving nonlinear programming problems involves several difficulties:

• Presence of Local Extrema: Most NLP methods only guarantee finding a local optimum (a solution that is the best in some neighborhood). Finding a global optimum (the best solution in the entire feasible region) is a challenging task, especially for non-convex problems.
• Non-convexity: If the problem is non-convex (the objective function or the feasible region is non-convex), there may be multiple local optima, and standard gradient-based methods can get "stuck" in one of them.
• Computational Complexity: NLP solution algorithms often require significantly more computational resources compared to LP.

Important Classes of NLP Problems

Despite the general complexity, there are important subclasses of NLP problems for which effective solution methods have been developed:

• Convex Programming: The problem of minimizing a convex function over a convex feasible set (or maximizing a concave function). A key property: any local minimum is also a global minimum. This significantly simplifies the search for an optimal solution.
• Quadratic Programming: The objective function is quadratic, and all constraints are linear.
• Separable Programming: The objective function and constraints can be expressed as sums of functions, where each function depends on only one variable.

Methods for Solving NLP Problems

Methods for Solving Nonlinear Programming (NLP) Problems

I. Unconstrained Optimization Methods:

• Gradient methods (method of steepest descent, conjugate gradient method);
• Newton's method and quasi-Newton methods (e.g., BFGS);
• Methods using Hessian approximation.

II. Constrained Optimization Methods:

• Transformation methods:
  • Penalty methods;
  • Barrier methods.
• Direct search direction methods:
  • Method of feasible directions.
• Methods based on optimality conditions:
  • Karush-Kuhn-Tucker (KKT) conditions;
  • Lagrange multiplier method.
• Iterative methods:
  • Sequential quadratic programming (SQP);
  • Interior-point methods.

III. Global Optimization Methods:

• Heuristic and metaheuristic methods:
  • Genetic algorithms;
  • Simulated annealing;
  • Tabu search.
• Deterministic methods:
  • Branch and bound;
  • Global optimization algorithms for problems with special structure.

References

• Bazaraa, M., Shetty, C. Nonlinear Programming. Theory and Algorithms. — Moscow: Mir, 1982.
• Fiacco, A., McCormick, G. Nonlinear Programming. Sequential Unconstrained Minimization Techniques. — Moscow: Mir, 1972.
• Himmelblau, D. Applied Nonlinear Programming. — Moscow: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

See also

• Operations research
• Optimization
• Linear programming
• Convex programming
• Objective function
• Constraints
• Feasible region