Nonlinear programming

Nonlinear programming, or NLP, is a specialized branch of mathematical optimization. Optimization is the process of finding the extrema of a function. Extrema are the maximum, minimum, or stationary points of a mathematical goal. In NLP, we seek these points while following specific rules called constraints. In many simple math problems, these rules and goals are linear. Linear functions follow straight paths and predictable patterns. However, nonlinear programming deals with problems where the objective function or the constraints are nonlinear. This means they may involve curves, complex shapes, or sudden changes rather than straight lines.

To understand how this works, we must look at the different types of problems that can arise. A feasible problem is one where at least one set of values satisfies every constraint. This means a valid solution actually exists within the allowed rules. An infeasible problem occurs when the constraints are mutually contradictory. In this case, no set of values can satisfy all the rules at once, and the feasible set is empty. An unbounded problem is a type of feasible problem where the objective function can be improved indefinitely. Because you can always find a better value, there is no single optimal solution. Most real-world applications aim for feasible problems, as infeasible or unbounded results often suggest a failure in the underlying model.

Mathematical structures also determine which solving techniques are most effective. If a maximization problem has a concave objective function and a convex constraint set, it is called a convex problem. Similarly, a minimization problem with a convex objective function and convex constraints is also convex. Convex optimization is highly efficient because general methods work well in most cases. There are also specialized sub-types of NLP. Quadratic programming is used when the objective function is quadratic but the constraints remain linear. Fractional programming is used when the objective function is a ratio of a concave and a convex function. These specific structures allow mathematicians to use more targeted and faster solution methods.

Solving these problems generally requires either analytic or numeric methods. Analytic methods involve using mathematical formulas to find exact solutions. The Karush–Kuhn–Tucker (KKT) conditions provide the necessary conditions for a solution to be optimal. If the functions are non-differentiable, mathematicians use subdifferential versions of the KKT conditions. Under the condition of convexity, these KKT conditions are sufficient to find a global optimum. Without convexity, they might only identify a local optimum. A local optimum is a point that is the best within its immediate area, but not necessarily the best across the entire problem.

Because analytic solutions are often too difficult for complex real-world math, numeric methods are more common. Numeric methods are iterative, meaning they repeat a process to get closer to the answer. They start at an initial point and use an update rule to move toward the optimal point. There are three primary types of update rules used in these routines. Zero-order routines only use the values of the objective and constraint functions at the current point. First-order routines also use the values of the gradients, which show the direction of change. Second-order routines use the values of the Hessians, which are more complex mathematical tools. While third-order routines are theoretically possible, they are rarely used due to the high computational load.

Another powerful technique is the branch and bound method. This approach divides a large program into smaller subclasses. These subclasses are solved using linear or convex approximations that create a lower bound on the total cost. As the algorithm continues to divide the problem, it eventually finds a solution that matches the best lower bound. This solution is considered optimal, though it may not be unique. In many large or difficult problems, the algorithm stops once it reaches an ε-optimal point. An ε-optimal point is a solution that is within a specific tolerance of the true best value. This ensures the process finishes in a reasonable amount of time.

Nonlinear programming is essential for managing complex systems like transportation and science. For example, moving petroleum products requires choosing between pipelines, rail tankers, road tankers, river barges, or coastal tankships. These choices involve economies of scale and capacity constraints, often creating cost functions with discontinuities. In experimental science, researchers use NLP for data analysis, such as fitting a spectrum with a sum of peaks. They use theoretical models with variable parameters to find the best numerical fit for their data. To handle these tasks, engineers use various software implementations. Open-source solvers include ALGLIB, NLopt, and SciPy, which contains the scipy.optimize solver. Another major solver is IPOPT, which is an interior point method solver used for complex nonlinear problems.