Nonlinear programming

Sometimes math helps us find the best way.

We want to find the highest or lowest point. This is called an optimization problem.

We must follow rules to find the answer. These rules are called constraints. Some problems have a good answer. Some problems have no answer at all. Other problems go on forever without an end. We can use math to solve these big puzzles. It helps us find the best spot.

Math can help us find the best way to do things. This is called an optimization problem. We try to find the highest or lowest point of a goal. We must follow certain rules. These rules are called constraints.

In some problems, the rules are simple and straight. But in nonlinear programming, the rules or the goal are not straight. They might be curved.

Some problems have a good answer. We call this a feasible problem. Other problems have no answer at all. This happens if the rules fight each other. These are called infeasible problems. Some problems are unbounded. This means the goal can keep getting better forever. There is no final best answer.

We use many ways to solve these puzzles. Some ways use math to find the exact spot. Most ways use number steps. These steps start at one point. Then they move closer to the best spot. We use these methods to solve big tasks. One task is moving oil. We must pick the best way to move it. We can use ships, trains, or pipes. Each way has different costs and rules.

This math helps us choose well.

Math helps us find the best way to do things. This is called an optimization problem. We try to find the highest or lowest point of a goal. We must follow certain rules. These rules are called constraints.

In many problems, the rules and goals are straight lines. But in nonlinear programming, things are different. The rules or the goal might be curved instead. This makes the math much more interesting. It is a special part of mathematical optimization. It deals with problems that do not follow straight paths.

There are different types of these math puzzles. A feasible problem is one that has a real answer. An infeasible problem has no answer at all. This happens if the rules fight each other. An unbounded problem is when a goal can get better forever. In that case, there is no final best answer. Most real-world tasks are feasible problems. If a model is infeasible, it might be a failure. We can sometimes fix this by looking at how much rules are broken.

People use many ways to solve these curved puzzles. Some use analytic methods to find an exact spot. The Karush–Kuhn–Tucker conditions, or KKT, help find these spots. These conditions work best when the math is smooth. Without certain shapes, they only find a local optimum. A local optimum is a good spot, but not the best one. Most real cases use numeric methods instead. These methods are iterative, which means they use many small steps. They start at one point and move closer to the best spot.

These steps use different rules to move. Zero-order routines only look at the current values. First-order routines also look at gradients. A gradient shows the direction of change. Second-order routines also look at Hessians. These are more complex math tools. We can also use a method called branch and bound. This method divides the big problem into smaller parts. It uses approximations to find a lower bound on the cost. We can stop when we find an ε-optimal solution. This means the answer is close enough to the best.

This math is very useful in our world. One example is moving petroleum products. We must choose between pipelines, rail tankers, or ships. Each choice has different costs and capacities. These costs can change in sudden ways. Scientists also use it to fit data to models. They might look at a spectrum of peaks. They try to find the best fit for unknown parts. Many computer programs can do this work. ALGLIB, NLopt, and SciPy are some examples. They help us solve these hard, curved problems.

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.