Nonlinear Optimization
Nonlinear Optimization · Optimizing when relationships are not straight lines
How do we find maximums and minimums when the relationship between variables is not a straight line? The linear programming of Chapters 02–05 dealt with problems whose objective function and constraints are expressed as straight lines, but not every relationship in the real world is linear. Doubling the advertising budget does not double sales: advertising has a big effect at first, but past a certain level each additional ad does less.
What is nonlinear optimization?
An optimization problem in which the objective function or at least one constraint is nonlinear is called nonlinear optimization. It covers many forms, including squares, products of variables, exponential functions, and logarithms.
Linear versus nonlinear optimization
| Aspect | Linear optimization | Nonlinear optimization |
|---|---|---|
| Example objective | Z = 3x + 5y | Z = 10x − x² |
| Variable–result relationship | Changes at a constant rate | The rate of change can vary |
| Shape of the graph | Straight line | Curves and many other shapes |
| Location of the optimum | A corner of the feasible region | An interior stationary point or anywhere on the boundary |
| Finding the optimum | The structure and algorithms of linear programming | Various methods depending on curvature and structure |
| Typical cases | Production problems with constant profit per unit | Advertising effects, portfolio risk, nonlinear costs |
The key difference is whether the objective value changes at a constant rate as you change a variable. That is why, unlike in linear problems, the optimum can lie inside the region rather than at a corner.
Example: advertising spend and advertising effect
x: advertising spend · R(x): a hypothetical score for the advertising effect (not actual sales or measured results)
As Figure 1 shows, the effect grows at first as ad spend rises, but the gains get smaller and smaller, and past a certain point spending more actually reduces the effect. In problems like this, instead of comparing the slopes of straight lines, we have to analyze how the function changes to find the optimum.
Finding the optimum with derivatives
The derivative tells you how much the effect changes when you increase ad spend by a little.
Spending more on ads increases the effect (x = 2 in Figure 1).
Spending more on ads decreases the effect (x = 8).
A stationary point where the rate of change is 0 (x = 5).
Setting 10 − 2x = 0 gives the stationary point x = 5. To check whether this point is a maximum, look at the second derivative.
If the second derivative is negative, the slope keeps decreasing and the curve bulges upward, so the stationary point is a maximum; if it is positive, the curve bulges downward and the point is a minimum. In this hypothetical model, the effect peaks at 25 when ad spend is 5. In real decisions you also need to consider the allowed range of ad spend, budget constraints, and how reliable the data used to estimate the advertising effect are.
Nonlinear optimization with constraints
Without the constraint, x = 5 was optimal, but if ad spend is allowed only up to 4, then R′(x) = 10 − 2x stays positive throughout that range. Since the effect keeps growing, the optimum is the boundary of the constraint, x = 4, with R(4) = 24. The unconstrained optimum and the optimum you can actually implement may differ, and in nonlinear problems the optimum can be either an interior stationary point or a boundary point, so you need to check both (Chapter 07).
Main types of nonlinear optimization
Problems whose objective function and feasible region are convex. They have the important property that, in a minimization problem, any local optimum is also the global optimum.
Examples: portfolio optimization that accounts for variance, resource allocation
There can be several peaks or valleys, so there is no guarantee that an optimum found from one starting point is the overall optimum.
Examples: complex process optimization, neural network training
Optimizes a nonlinear objective function subject to equality or inequality constraints.
Example: process design that considers output, cost, and quality requirements together
Convex versus nonconvex is a distinction based on the problem's structure, while constrained nonlinear optimization is a distinction based on whether there are constraints, so the categories are not mutually exclusive.
Figure 3 shows gradient descent run from three starting points on a nonconvex function with several valleys. Starting on the left it stops at a local minimum of 1.91, starting on the right at a local minimum of -0.27, and only the start in the middle reaches the global minimum of -1.36. This is why nonconvex problems call for trying several starting points or using global search methods as well.
Which algorithm should you use?
| Method | Basic idea | Use |
|---|---|---|
| Gradient descent | Uses the gradient to move a little at a time in the direction that decreases the objective | Training machine learning models (13 · Chapter 01) |
| Newton's method | Searches for the optimum using first- and second-derivative information | Differentiable optimization problems |
| Sequential quadratic programming (SQP) | Repeatedly approximates the nonlinear problem with a quadratic programming problem | Constrained nonlinear optimization |
| Interior-point methods | Search for the optimum from inside the feasible region | Large-scale optimization problems |
| Evolutionary algorithms | Generate candidate solutions and improve them by selection and variation | Complex nonlinear · nonconvex problems |
In Figure 4, gradient descent moves a fixed proportion along the gradient and approaches x = 5 only after many iterations, whereas Newton's method also uses the curvature (second derivative) and, on a quadratic function, reaches the optimum in a single step. In exchange, Newton's method has to compute second derivatives, which becomes expensive when there are many variables. There are also methods, such as evolutionary algorithms, that use no derivative information, and no method is always best for every problem. Choose by weighing differentiability, constraints, starting values, and computational cost together.
Where it is used in practice
Budget allocation that accounts for the nonlinear relationship between ad spend and response rate
Portfolio construction that accounts for the relationship between return and risk
Optimizing costs and efficiency that change with output
Operating plans that account for power output, fuel consumption, and operating constraints
Searching for the parameters that minimize a loss function
Optimizing structural designs, control systems, and process conditions
Assuming an advertising effect of R(x) = 10x − x², the effect peaked (25) at x = 5, where R′(x) = 0, and R″(x) = −2 < 0 confirmed that this is a maximum. With an ad spend cap of 4, R′(x) > 0 across the whole allowed range, so the optimum was the boundary x = 4 (R = 24).
Check both the points where the slope is 0 and the boundaries, and use curvature to tell maximums from minimums.
- Nonlinear optimization: deals with problems where the objective function or at least one constraint is nonlinear.
- Derivatives: the first derivative gives the rate of change and stationary points; the second derivative tells maximums from minimums.
- Boundary solutions: with constraints, a point on the boundary rather than an interior stationary point can be optimal.
- Convexity: in convex problems a local optimum is the global optimum, but in nonconvex problems you can stop at different solutions depending on the starting point.
- Algorithms: choose among gradient descent, Newton's method, SQP, interior-point methods, and evolutionary algorithms to fit the problem's structure.
Next is 07 Constrained optimization. Using Lagrange multipliers and the KKT conditions, we look at how constraints affect the optimal solution.