Nonlinear programming

• 1. Introduction

  ›

  Nonlinear programming is the mathematical discipline concerned with finding the best possible answer when the rules of the problem refuse to stay straight. Imagine you need to move petroleum products across a continent. You have pipelines, rail tankers, road tankers, river barges, and coastal tankships to choose from. The costs do not scale smoothly. They jump at certain batch sizes, drop off, then climb again. No simple line on a graph captures that behavior. That is the world nonlinear programming was built to navigate.

  At its core, an optimization problem asks a deceptively clean question: over all possible values of a set of unknown real variables, where does an objective function reach its highest or lowest point? The answer must also satisfy a collection of constraints, both equalities and inequalities. When at least one of those functions is nonlinear, the problem belongs to nonlinear programming. The questions that follow are not merely mathematical. They are practical: how do you find the optimum when the landscape is full of peaks and valleys? And how do you know when you have actually reached the best one?

• 2. Feasible, Infeasible, Unbounded

  ›

  Every nonlinear program falls into one of three categories, and the distinction matters enormously. A feasible problem is one where at least one combination of variable values satisfies all the constraints simultaneously. Most real-world applications live here. An infeasible problem is one where the constraints contradict each other so thoroughly that no solution exists at all; the feasible set is simply empty. Practitioners treat infeasibility as a signal that the underlying model has failed, not that the world has failed.

  The third category, the unbounded problem, is perhaps the strangest. It is feasible in the sense that solutions exist, but the objective function can be pushed to any value, no matter how large or how favorable. There is always a better answer just out of reach, so there is no true optimum. In practice, infeasible and unbounded problems are understood as modeling errors. When a problem turns out to be infeasible, one common engineering workaround is to reframe it as minimizing the total sum of constraint violations, which at least produces a useful diagnostic.

• 3. Special Structures

  ›

  Not every nonlinear program requires the same tools. Several special structures unlock faster or more reliable solution paths. When the objective function is concave in a maximization setting, or convex in a minimization setting, and the constraint set is also convex, the entire problem is classified as a convex program. Convex optimization carries a powerful guarantee: any local optimum is also a global one, which removes the danger of being trapped in a merely adequate solution.

  Two other structures are worth noting separately. If the objective function is quadratic while all the constraints remain linear, quadratic programming techniques apply directly. If the objective is a ratio of a concave function to a convex function in a maximization context, and the constraints are convex, fractional programming techniques can transform the problem into a convex one. These transformations are not cosmetic. They allow solvers designed for well-behaved problems to handle a wider class of real-world situations.

• 4. The KKT Conditions

  ›

  The Karush-Kuhn-Tucker conditions, commonly called the KKT conditions, are the analytical backbone of nonlinear programming. Under two assumptions, differentiability of the relevant functions and the satisfaction of constraint qualifications, the KKT conditions provide necessary conditions for any solution to be optimal. Put plainly, a point cannot be optimal unless it satisfies these conditions.

  Under convexity, the KKT conditions become sufficient as well as necessary. A point satisfying them is guaranteed to be a global optimum. Without convexity, they only guarantee a local optimum, a point that is best in its immediate neighborhood but not necessarily across the entire feasible region. When the number of local optima is small, it is sometimes possible to find all of them analytically and compare objective values. For problems where some functions are not differentiable, subdifferential versions of the KKT conditions extend the framework to cover those rougher cases.

• 5. Numeric Methods in Practice

  ›

  Solving the KKT conditions analytically is rarely possible in realistic problems. Numerical methods take over, and they share a common structure: start at some initial point, then move step by step toward points expected to be closer to the optimum, guided by an update rule. The differences between solvers often come down to which information about the problem each update rule uses.

  Zero-order routines use only the values of the objective and constraint functions at the current point, nothing about their slopes or curvature. First-order routines add gradient information, the rates of change of those functions. Second-order routines go further, incorporating the Hessian, the matrix of second derivatives, which captures curvature. Third-order and higher routines are theoretically possible but not used in practice; the computational cost outweighs the theoretical benefit. Among the named solvers available today, ALGLIB supports C++, C#, Java, and Python. NLopt offers interfaces including Julia, Python, R, and MATLAB. SciPy's scipy.optimize module provides zero-order, first-order, and second-order algorithms. IPOPT is an interior point method solver with interfaces ranging from C and Fortran to AMPL and Python. On the proprietary side, SNOPT is written in Fortran and supports C, C++, Python, and MATLAB interfaces.

• 6. Branch and Bound

  ›

  Branch and bound takes a different approach to hard nonlinear programs. Instead of attacking the full problem at once, it divides the problem into subclasses and solves each using convex or linear approximations that form a lower bound on the true cost within that subdivision. As subdivisions multiply and refine, the algorithm eventually encounters an actual feasible solution whose cost equals the best lower bound found anywhere in the search. That point is optimal, though not necessarily unique.

  The method also supports early termination. If the solver is stopped before finding a solution that exactly matches a lower bound, it can guarantee that the best possible answer lies within some tolerance of the best point found so far. Points meeting that criterion are called epsilon-optimal, and reaching epsilon-optimality is typically the practical goal for very large or difficult problems. The branch and bound approach is particularly suited to situations where costs or values carry uncertainty, provided that uncertainty can be estimated with appropriate reliability measures.

• 7. Scientific and Transport Applications

  ›

  Experimental science offers a clear illustration of why nonlinear methods matter. When a scientist fits a theoretical model to observed data, the model contains variable parameters and the experiment itself may introduce additional unknowns. Simple linear fitting methods work for narrow cases, such as fitting a spectrum with peaks of known location and shape but unknown magnitude. For the general case, the problem is nonlinear, and numerical optimization is the only path to a best fit. Crucially, researchers in this setting need more than the best-fit parameter values; they also need a measure of how precise those values are.

  The transportation example, which the field uses as a canonical illustration, puts the same challenges in economic terms. Selecting among pipeline, rail tanker, road tanker, river barge, and coastal tankship for petroleum product transport involves cost functions with both smooth changes and discontinuities introduced by economies of scale. Connectivity constraints and capacity limits layer further complexity on top. The combination of non-smooth cost functions and structural constraints is precisely what makes general-purpose nonlinear solvers indispensable for logistics planning of that kind.