Nonlinear Programming

Nonlinear Programming: Concept Architecture

Orientation and learning roadmap

Nonlinear programming provides a mathematical framework for choosing the best feasible values when relationships are not all linear. This page develops objectives, decision variables, constraints, feasibility, convexity, optimality conditions, algorithms, scaling, initialization, and verification. It then connects these ideas to health-economic calibration, allocation, treatment design, uncertainty, Excel use, and reproducible reporting.

Every problem needs decisions, an objective, and constraints

Decision variables represent the quantities the optimizer may change, while the objective expresses what should be minimized or maximized. Constraints define the combinations that are permitted by resources, science, policy, or mathematical structure.

A standard minimization form is:

[ \begin{aligned} \underset{\mathbf x}{\operatorname{minimize}}\quad & f(\mathbf x)\ \text{subject to}\quad & g_i(\mathbf x)\leq0,\quad i=1,\ldots,m,\ & h_j(\mathbf x)=0,\quad j=1,\ldots,p,\ & \boldsymbol\ell\leq\mathbf x\leq\mathbf u. \end{aligned} ]

The functions, units, domains, and direction of optimization must be explicit. Maximizing benefit is equivalent to minimizing its negative, but software outputs and multiplier signs must be interpreted using the implemented convention.

Nonlinearity can occur in the objective or constraints

A problem belongs to nonlinear programming when at least one objective or constraint relationship is nonlinear in the decision variables. Products, powers, ratios, exponentials, logarithms, probabilities, and simulation outputs commonly introduce nonlinearity.

A quadratic objective with linear constraints is a structured nonlinear case, while a linear objective with a nonlinear budget or risk constraint is also nonlinear programming. Recognizing special structure can lead to stronger algorithms and guarantees than treating every problem as a generic black box.

Feasibility comes before optimality

A feasible point satisfies every equality, inequality, and bound within declared numerical tolerances. If the feasible set is empty, no optimizer can produce a valid solution, even if it returns a point with a favorable objective value.

Constraint violations should be reported in their original units and on suitable scaled measures. Small numerical residuals may be acceptable, but a solver tolerance is not permission to violate a clinical, legal, or physical requirement materially.

Active constraints shape the final choice

An inequality constraint is active at a solution when it holds at equality and inactive when it has slack. Active constraints restrict local movement and often explain why the optimum differs from the unconstrained best point.

For (g_i(\mathbf x)\leq0), slack may be written as (-g_i(\mathbf x)\geq0). A constraint can be numerically near-active without carrying a meaningful shadow value, so activity and multiplier interpretation should be checked together.

Local and global optima are different claims

A local optimum is best within a neighborhood, while a global optimum is best over the entire feasible set. Nonconvex problems may contain several local minima, saddle points, disconnected feasible regions, or flat areas.

A local solver generally certifies only local first- or second-order conditions under its assumptions. Describing its result as “the optimum” without addressing nonconvexity, initialization, or global evidence can overstate what was established.

Convexity turns local solutions into global solutions

For minimization, a convex objective over a convex feasible set gives powerful guarantees: every local minimum is global. Strict convexity can also give a unique minimizer, although different decision vectors may still tie when strictness or identification is absent.

Convex inequality constraints usually take the form (g_i(\mathbf x)\leq0), and equality constraints must be affine to preserve a conventional convex feasible set. A smooth-looking function or positive Hessian at one point does not prove global convexity.

Gradients describe first-order change

The gradient collects partial derivatives of the objective with respect to the decision variables. At an unconstrained differentiable interior optimum, the gradient is zero under ordinary regularity conditions.

[ \nabla f(\mathbf x^*)=\mathbf0. ]

A zero gradient is necessary but not sufficient because the point may be a maximum or saddle point. Boundaries, nonsmooth functions, and constraints require adapted optimality conditions.

The Hessian describes local curvature

The Hessian matrix contains second derivatives and describes how the gradient changes locally. A positive-definite Hessian at a stationary point supports a strict local minimum for an unconstrained twice-differentiable problem.

[ H_f(\mathbf x)=\left[\frac{\partial^2 f} {\partial x_r\partial x_s}\right]_{r,s}. ]

In constrained problems, curvature is assessed on feasible directions using the Hessian of the Lagrangian. Numerical Hessians can be noisy, indefinite, or poorly scaled, so their use requires care.

The Lagrangian combines the objective and constraints

Lagrange multipliers attach local values to constraints and allow first-order conditions to be written compactly. The formulation must preserve a consistent inequality convention. For (g_i\leq0), the Lagrangian is:

[ \mathcal L(\mathbf x,\boldsymbol\lambda,\boldsymbol\nu) =f(\mathbf x)+\sum_{i=1}^{m}\lambda_i g_i(\mathbf x) +\sum_{j=1}^{p}\nu_j h_j(\mathbf x). ]

The sign and economic interpretation of a multiplier depend on how the objective and constraint are written. Multipliers are local sensitivity measures, not universal prices independent of formulation and units.

KKT conditions characterize constrained stationary points

The Karush–Kuhn–Tucker conditions generalize Lagrange multiplier conditions to inequality-constrained problems. Under an appropriate constraint qualification, they are necessary at a local optimum and become sufficient for global optimality in a convex problem.

[ \nabla_{\mathbf x}\mathcal L(\mathbf x^,\boldsymbol\lambda^,\boldsymbol\nu^*)=\mathbf0, ]

[ g_i(\mathbf x^)\leq0,\quad h_j(\mathbf x^)=0, \quad \lambda_i^*\geq0, \quad \lambda_i^g_i(\mathbf x^)=0. ]

These are stationarity, primal feasibility, dual feasibility, and complementary slackness. A small KKT residual supports numerical optimality for the formulated problem but does not validate the model itself.

A constrained quadratic example is exactly auditable

Consider minimizing squared distance from ((2,1)) subject to nonnegative decisions and a capacity limit (x+y\leq2). The unconstrained minimizer violates capacity, so the constrained solution lies on the active boundary.

[ \underset{x,y}{\operatorname{minimize}}\quad (x-2)^2+(y-1)^2 \quad\text{subject to}\quad x+y\leq2,\quad x,y\geq0. ]

The solution is ((x^,y^)=(1.5,0.5)), with objective (0.5). For multiplier (\lambda=1) on (x+y-2\leq0), the stationarity equations (2(x-2)+\lambda=0) and (2(y-1)+\lambda=0), feasibility, dual feasibility, and complementary slackness all hold.

Constraint qualifications prevent degenerate conclusions

Constraint qualifications describe regularity of active constraint gradients near a candidate solution. Without them, an optimum may exist even though ordinary KKT multipliers do not, or multipliers may be unstable and non-unique.

Linear independence, Mangasarian–Fromovitz, and Slater-type conditions apply in different settings. Software rarely turns these theoretical distinctions into a complete validity certificate, so degeneracy warnings and multiplier behavior deserve review.

Dual values show local sensitivity to constraint limits

Under suitable regularity and sign conventions, a multiplier approximates the change in optimized objective from a small relaxation of a constraint bound. This supports interpretation of scarce capacity, budget, or risk limits at the margin.

The sensitivity is local and can change when the active set changes or the problem is nonconvex. A multiplier should not be extrapolated to large policy changes without re-solving and checking the solution path.

Scaling affects both accuracy and convergence

Optimization becomes difficult when variables, objective terms, or constraint residuals differ by many orders of magnitude. Poor scaling distorts stopping tests, finite differences, linear algebra, and merit functions.

Variables can be nondimensionalized or rescaled to comparable numerical ranges, while objective and constraint scaling should preserve meaning. Results must be transformed back into original units before interpretation and reporting.

Analytic and automatic derivatives improve reliability

Accurate gradients and Hessian information can substantially improve speed and convergence. Analytic derivatives, automatic differentiation, complex-step derivatives where applicable, and carefully chosen finite differences provide different accuracy and implementation tradeoffs.

Every derivative implementation should be checked against an independent approximation at representative and boundary points. A solver can converge to the wrong answer when supplied derivatives are internally consistent but incorrect.

Finite differences require a scale-aware step

A finite-difference derivative balances truncation error against floating-point cancellation. Steps that are too large poorly approximate local change, while steps that are too small subtract nearly equal computed values.

[ \frac{\partial f}{\partial x_k} \approx\frac{f(\mathbf x+h\mathbf e_k)-f(\mathbf x)}{h}. ]

Relative steps should account for the scale of each variable and any noise in the objective. Simulation noise can make ordinary finite differences unusable unless common random numbers, smoothing, replication, or derivative-free methods are introduced.

Line-search methods control movement along a direction

A line-search method chooses a search direction and then selects a step length that sufficiently improves an objective or merit function. Gradient descent, Newton, quasi-Newton, and sequential quadratic programming methods can use line searches.

Sufficient-decrease and curvature conditions balance progress with stability. A failed line search may signal poor derivatives, scaling, infeasibility, non-smoothness, or a direction that does not improve the constrained merit function.

Trust-region methods limit how far a local model is trusted

Trust-region methods approximate the objective and constraints near the current point and restrict candidate steps to a neighborhood. The radius expands when the approximation predicts actual improvement well and contracts when it performs poorly.

This framework can be more robust than an unrestricted local step for curved or poorly approximated problems. Trust-region convergence remains local unless additional global-search logic or convexity supplies a stronger guarantee.

Sequential quadratic programming solves local subproblems

Sequential quadratic programming approximates the objective's Lagrangian curvature and linearizes constraints to form a quadratic subproblem at each iteration. It is a leading approach for smooth constrained nonlinear problems.

The subproblem suggests a step and multiplier update, while merit or filter methods manage progress toward both feasibility and optimality. Performance depends on derivative quality, scaling, active-set identification, and a suitable starting region.

Interior-point methods approach constraints through a barrier

Interior-point algorithms add barrier terms or primal-dual conditions that keep iterates inside inequality boundaries while the barrier parameter decreases. They can handle large sparse problems effectively.

Near boundaries, barrier systems may become ill-conditioned and require careful linear algebra. A solver's barrier termination values and constraint residuals should be reviewed rather than reduced to a success flag.

Derivative-free methods serve expensive or irregular models

Derivative-free optimization constructs steps without user-supplied gradients and can be useful when objectives are noisy, discontinuous, or generated by a simulator. Direct search, pattern search, interpolation-based trust regions, and evolutionary methods make different assumptions.

These methods can require many evaluations and provide weaker optimality evidence. Stochastic objectives should report replication, random-stream control, noise handling, and uncertainty in the selected solution.

Nonsmooth problems need suitable algorithms

Absolute values, maxima, thresholds, indicator functions, piecewise rules, and discrete event logic can make derivatives nonexistent or discontinuous. Feeding such a problem to a smooth solver can produce unstable gradients or false convergence.

Reformulation with auxiliary variables, smoothing with bias assessment, subgradient methods, complementarity approaches, or mixed-integer formulations may be appropriate. The reformulated problem must preserve the intended decision logic.

Discrete choices create a different optimization class

If a decision variable must be integer or binary, the model becomes a mixed-integer nonlinear program rather than a continuous nonlinear program. Continuous relaxation can provide bounds or starting points but may yield decisions that cannot be implemented.

Branch-and-bound, cutting planes, convex relaxations, and global solvers address discrete structure. Rounding a continuous solution after optimization can violate constraints and lose optimality.

Multiple starts provide evidence about nonconvexity

Running a local solver from dispersed feasible or repaired starting points can reveal alternative local solutions. Agreement in objective and decision variables strengthens confidence but does not mathematically prove global optimality.

Starts should span substantively plausible regions and include boundary cases. Reporting only the best run hides the frequency of failures, inferior basins, and dependence on initialization.

Global methods trade computation for stronger search

Deterministic global optimization uses bounds, relaxations, interval methods, or spatial branching to establish a global bound. Stochastic global methods such as multistart heuristics, evolutionary algorithms, and simulated annealing explore broadly but usually do not certify globality.

A claimed optimality gap should identify the bound and solver conditions that produced it. “Global” in a software method name is not itself a guarantee for every problem and tolerance.

Tolerances define practical numerical completion

Solvers stop using measures such as gradient norm, KKT residual, step size, objective change, feasibility, complementarity, iteration limit, or evaluation limit. Different tolerances can produce different solutions near flat regions or active constraints.

Termination due to a small step or exhausted iterations is not equivalent to verified optimality. The final constraint violations and first-order residuals should be compared with problem-specific acceptable scales.

Health-economic calibration is often nonlinear

Calibration may minimize a weighted discrepancy between model outputs and empirical targets. Nonlinear disease models, survival functions, interacting parameters, and simulation outputs can create several local minima or weakly identified parameter combinations.

[ Q(\boldsymbol\theta)= (\mathbf m(\boldsymbol\theta)-\mathbf d)^{\mathsf T} W(\mathbf m(\boldsymbol\theta)-\mathbf d). ]

Weights should represent target uncertainty or another declared criterion, and constraints should encode scientifically valid parameter domains. Calibration fit, parameter plausibility, identifiability, and predictive validation are separate checks.

Resource allocation can contain nonlinear returns

Allocation problems may maximize health outcomes or net benefit under budgets, capacity, equity, coverage, or risk constraints. Diminishing returns, congestion, interactions, and nonlinear dose-response relationships make linear programming inadequate.

The objective must define whose outcomes count, over what period, and under what distributional or equity rule. A mathematically optimal allocation can still be ethically or operationally unacceptable if relevant constraints were omitted.

Treatment design can balance benefit and toxicity

Dose, timing, screening interval, and treatment sequencing may be optimized using nonlinear clinical response and harm relationships. These applications are high stakes because the fitted functions and constraints can be uncertain outside observed data.

Optimization should remain inside clinically supported domains and undergo expert review, external validation, and robust sensitivity analysis. The solver must not be allowed to exploit unrealistic extrapolation or model artifacts.

Simulation optimization requires noise-aware methods

When each objective evaluation is a stochastic microsimulation, identical decisions can produce different observed objective values. An optimizer may chase random variation rather than genuine improvement.

Common random numbers, fixed streams during comparison, replication, response-surface methods, stochastic approximation, or sample-average approximation can reduce this risk. Final candidates should be reevaluated with independent random streams and adequate precision.

Robust and stochastic formulations represent uncertainty differently

Stochastic programming optimizes expectations or risk measures over specified probability distributions. Robust optimization protects against values in an uncertainty set, often producing a more conservative solution.

These approaches are not substitutes for ordinary sensitivity analysis and require explicit assumptions about uncertainty. A robust solution is only robust to the modeled set, while an expected-value solution can conceal poor tail performance.

Sensitivity analysis should re-solve the problem

Changing a parameter can alter the active constraints and the identity of the optimum. Evaluating the old decision under new inputs measures performance robustness but does not show what the optimal decision would become.

Both analyses can be useful: re-solving shows decision adaptation, while holding the solution fixed shows consequences of commitment. Local derivative-based sensitivity should be supplemented when changes are large or active sets switch.

Excel Solver supports learning and small problems

Excel Solver can express nonlinear objectives, variable cells, bounds, and constraints and is useful for transparent teaching or modest audit models. Formula errors, volatile functions, hidden scaling, and solver-option changes can make results fragile.

The workbook should display the objective, decision variables, constraints, slack, starting values, solver method, tolerances, and final residuals. High-stakes, large, sparse, stochastic, or nonconvex problems require more controlled software and reproducible code.

A disciplined nonlinear-programming workflow

Reliable optimization begins by translating the decision into an auditable mathematical program and ends with independent evidence that the selected solution is feasible, stable, and decision-relevant. Solver success is only one part of that evidence. A practical sequence is:

1. Define the decision. Specify variables, units, allowable domains, objective, perspective, horizon, and decision owner.
2. Write every constraint. State equations, inequalities, bounds, policy rules, and clinical or physical limits.
3. Classify the structure. Identify smoothness, convexity, sparsity, discreteness, stochastic noise, and separability.
4. Scale the formulation. Rescale variables, objective terms, and constraints without changing their meaning.
5. Choose the algorithm. Match derivatives, bounds, nonlinearity, convexity, noise, and problem size to the solver.
6. Validate derivatives. Compare analytic or automatic derivatives with independent numerical checks.
7. Explore starts. Use feasible or repaired initial points across plausible regions for nonconvex problems.
8. Check the solution. Recalculate the objective, feasibility, KKT residuals, active constraints, and multipliers independently.
9. Test robustness. Re-solve under input, tolerance, scaling, structural, and uncertainty scenarios.
10. Report reproducibly. Preserve formulation, code, data, software, options, starts, logs, failures, and validation evidence.

Common errors and safeguards

Optimization can return a precise-looking answer even when the formulation, derivatives, or numerical conditions are wrong. Strong safeguards separate mathematical optimality from scientific and policy validity.

• Omitting a real-world constraint and interpreting the resulting infeasible policy as optimal.
• Treating a locally optimal nonconvex solution as globally optimal without evidence.
• Accepting a solver success flag without checking constraint and KKT residuals.
• Supplying incorrect gradients or Hessians and trusting faster convergence.
• Mixing variables and constraints with extreme scales without rescaling.
• Starting every run from one point in a multimodal problem.
• Rounding continuous decisions into discrete choices after optimization.
• Interpreting multipliers as constant prices over large changes.
• Allowing an optimizer to exploit extrapolation beyond credible clinical data.
• Calibrating to targets without examining identifiability or predictive validity.
• Optimizing a noisy simulation without controlling random variation.
• Performing sensitivity analysis on the objective without re-solving when the optimum may change.
• Reporting excessive digits unsupported by tolerances and input uncertainty.
• Confusing numerical optimality with ethical, equitable, affordable, or implementable policy.

Reproducible reporting makes the optimum auditable

A complete record identifies the variables, units, domains, objective, constraints, bounds, data and parameter sources, transformations, scaling, convexity assessment, derivatives, software and version, solver algorithm, starting points, tolerances, iteration limits, and random-stream controls. It should retain logs for successful and failed runs and state whether global optimality is proven, bounded, explored heuristically, or not assessed.

Results should include the decision vector, objective value, constraint values and slack, active set, multipliers where interpretable, KKT or stationarity residuals, sensitivity results, and independent recalculation. Health-economic applications should also explain how the optimized choice changes costs, outcomes, equity, uncertainty, and implementability rather than presenting the numerical solution alone.