Constrained Nonlinear Programming
Chapters 19 and 20 let the search roam over all of \(\mathbb{R}^n\); real engineering never does. Budgets, tolerances, capacities and physical laws fence the design in, and the best feasible point is usually pressed hard against that fence — where \(\nabla F \ne \mathbf{0}\) and every result so far falls silent. This chapter rebuilds the theory for that world: the Lagrangian, which converts a constrained problem into a stationarity condition; the KKT conditions, the central result of nonlinear programming; constraint qualifications and convexity, which say when those conditions can be trusted; duality and the shadow-price meaning of a multiplier; and the algorithms — penalty, barrier, and SQP — that turn the theory into computation.
- The general NLP, its feasible region, and why constrained optima need new theory.
- Lagrange multipliers for equality constraints — the tangency geometry and the shadow-price reading of \(\lambda\).
- The KKT conditions — stationarity, feasibility, dual feasibility, and complementary slackness.
- Constraint qualifications and why convexity upgrades KKT from necessary to sufficient.
- Lagrangian duality — the dual function, weak and strong duality, and the duality gap.
- Penalty, barrier and augmented Lagrangian methods, plus SQP and feasible-direction algorithms.
The Constrained Problem
The general nonlinear programming problem asks for the best point that also obeys the rules. Some rules are exact — a mass balance must close, a circuit law must hold — and appear as equality constraints. Others are limits — a stress must not exceed yield, a budget must not be overspent — and appear as inequality constraints.
The set of points satisfying every constraint is the feasible region \(\mathcal{S}\), and we now seek the lowest \(F\) over \(\mathcal{S}\) alone. Any constraint can be pushed into this standard form: \(g(\mathbf{x}) \ge 0\) becomes \(-g(\mathbf{x}) \le 0\), and \(\max F\) becomes \(\min -F\), exactly as in Chapter 19.
Now for the observation that forces the entire chapter. In Chapter 19, the first-order condition \(\nabla F(\mathbf{x}^\star) = \mathbf{0}\) was necessary at every local minimum. That claim rested on a hidden assumption: that we were free to step in any direction, so a nonzero gradient always offered an escape downhill. Inside a feasible region that reasoning still holds. But at a point on the boundary, the downhill direction \(-\nabla F\) may lead straight out of \(\mathcal{S}\) — and a direction you are not allowed to take is no escape at all.
The gradient need not vanish; it need only fail to point anywhere useful and allowed. The whole of Sections 21-2 and 21-3 is the work of making "useful and allowed" precise — and the answer will be that \(\nabla F\) must be exactly cancelled by the gradients of the constraints holding it in place.
Lagrange Multipliers
Start with equality constraints alone: minimise \(F(\mathbf{x})\) subject to \(h(\mathbf{x}) = 0\). The feasible set is now a curve or surface, and we may move only along it. Suppose we stand at a feasible point and \(\nabla F\) has any component tangent to that surface — then sliding along the surface in the opposite direction lowers \(F\) while staying feasible, so we are not optimal. At a minimum, therefore, \(\nabla F\) can have no tangential component at all: it must point entirely perpendicular to the surface.
But \(\nabla h\) is itself perpendicular to the surface \(h = 0\), by definition of a gradient. Two vectors perpendicular to the same surface must be parallel — and that single geometric fact is the method of Lagrange multipliers:
The scalar \(\lambda\) is the Lagrange multiplier — the factor by which the constraint gradient must be scaled to cancel the objective gradient. The condition, together with feasibility itself, is packaged neatly by defining the Lagrangian, a single unconstrained function whose stationarity reproduces both:
Setting \(\nabla_{\mathbf{x}}\mathcal{L} = \mathbf{0}\) gives the tangency condition, and \(\nabla_{\boldsymbol{\lambda}}\mathcal{L} = \mathbf{0}\) returns the constraints \(h_i(\mathbf{x}) = 0\). So a constrained problem in \(n\) variables becomes an unconstrained stationarity problem in \(n + m\) variables — solve the \(n+m\) equations for \(\mathbf{x}^\star\) and \(\boldsymbol{\lambda}^\star\) together.
The multiplier is far more than an algebraic device — it carries units and meaning. Write the constraint as \(h(\mathbf{x}) = b\) and ask how the optimal value \(F^\star\) responds to loosening the requirement \(b\). The answer is the sensitivity theorem, and it is why economists call \(\lambda\) a shadow price and engineers read it as a marginal cost:
A large \(|\lambda_i|\) marks a constraint that is expensive — relaxing it by one unit buys a large improvement, so that is where design effort belongs. A multiplier near zero marks a constraint that barely matters. This is exactly the shadow-price interpretation met in linear programming (Chapter 10), now generalised to nonlinear problems. A note on signs: with the convention \(\mathcal{L} = F + \sum\lambda_i h_i\) used here, the sensitivity carries a minus sign; texts defining \(\mathcal{L} = F - \sum\lambda_i h_i\) get \(+\lambda_i\). Only the sign of \(\lambda\) changes, never the point \(\mathbf{x}^\star\).
The KKT Conditions
Inequalities introduce a genuinely new feature: a constraint \(g_j(\mathbf{x}) \le 0\) may or may not be doing anything. If \(g_j(\mathbf{x}^\star) = 0\) the point sits exactly on that boundary and the constraint is active (or binding) — it is physically holding the solution back. If \(g_j(\mathbf{x}^\star) < 0\) there is slack, the constraint is inactive, and the solution would not move if we deleted the constraint entirely.
Two consequences follow. First, inactive constraints contribute nothing, so their multipliers must be zero. Second, an active constraint pushes back in only one direction — it resists motion outward but never pulls inward — so, unlike an equality multiplier, its multiplier carries a sign restriction. Both facts are captured by the Karush–Kuhn–Tucker conditions, first stated by Karush in 1939 and rediscovered by Kuhn and Tucker in 1951: the central theorem of nonlinear programming.
Together with primal feasibility \(h_i(\mathbf{x}^\star) = 0,\ g_j(\mathbf{x}^\star) \le 0\); dual feasibility \(\mu_j \ge 0\); and complementary slackness \(\mu_j\,g_j(\mathbf{x}^\star) = 0\). If \(\mathbf{x}^\star\) is a local minimum and a constraint qualification holds, multipliers exist satisfying all four.
| Condition | Statement | What it means |
|---|---|---|
| Stationarity | \(\nabla F + \sum\lambda_i\nabla h_i + \sum\mu_j\nabla g_j = \mathbf{0}\) | The objective's pull is exactly balanced by the constraints' push |
| Primal feasibility | \(h_i = 0,\ \ g_j \le 0\) | The point actually obeys the rules |
| Dual feasibility | \(\mu_j \ge 0\) | Inequalities push one way only — a wall, not a magnet |
| Complementary slackness | \(\mu_j\,g_j = 0\) | Each inequality is either active (\(g_j = 0\)) or ignorable (\(\mu_j = 0\)) |
Complementary slackness deserves a second look, because it is the condition students most often misread. It does not say that both factors are zero. It says that in every product \(\mu_j g_j\), at least one factor must vanish: either the constraint is tight (\(g_j = 0\), and then \(\mu_j\) is free to be positive), or it has slack (\(g_j < 0\), and then \(\mu_j\) is forced to zero). A constraint cannot simultaneously have room to spare and exert force. This is also what makes KKT computable: it converts inequalities into a finite set of equality problems, one per guess of the active set.
That gives the standard hand-solution recipe. Enumerate the possible active sets; for each, solve the resulting equalities; then discard any candidate violating \(\mu_j \ge 0\) (the constraint is pulling the wrong way) or violating feasibility. With \(p\) inequalities there are \(2^p\) subsets — fine for the two or three of a textbook problem, hopeless beyond that, which is exactly why Section 21-7 exists.
The sign convention repays a moment's care. With the problem in standard form \(g_j \le 0\) and \(\mathcal{L} = F + \sum\mu_j g_j\), we require \(\mu_j \ge 0\). Flip the constraint to \(g_j \ge 0\) without flipping the Lagrangian and the requirement becomes \(\mu_j \le 0\). Almost every sign error in this chapter traces back to a constraint that was never converted to standard form.
Qualifications & Convexity
The KKT theorem carries a clause easy to skim past — "if a constraint qualification holds". The conditions are a statement about gradients, and gradients describe a constraint surface faithfully only when that surface is well behaved at the point in question. Where constraints meet in a cusp or a degenerate tangency, the linearised picture misrepresents the true feasible set, and a genuine minimum can fail KKT outright.
The most common qualification is LICQ (linear independence constraint qualification): the gradients of the active constraints at \(\mathbf{x}^\star\) are linearly independent. Others include Slater's condition (a strictly feasible point exists, for convex problems) and the fact — worth remembering — that linear constraints need no qualification at all. Since the great majority of engineering constraints are linear or smoothly curved and independent, qualifications rarely bite in practice; but they explain why KKT is a necessary condition with a caveat rather than a universal law.
Even with a qualification in hand, KKT remains only necessary — it flags candidates, exactly as \(\nabla F = \mathbf{0}\) did in Chapter 19, and those candidates may be minima, maxima, or saddles. The remedy is the same as it was there, and it is again convexity. A convex program is one in which \(F\) is convex, each \(g_j\) is convex, and each \(h_i\) is affine (linear plus a constant) — conditions ensuring the feasible region is a convex set and the objective a bowl over it.
Convexity does for constrained problems precisely what it did for unconstrained ones in Chapter 19-4: it promotes a local, first-order certificate into a global guarantee. This is why so much effort in modelling goes into recognising — or engineering — convex structure. If the program is convex, finding one KKT point ends the problem.
| Situation | Status of the KKT conditions |
|---|---|
| Convex program, qualification holds | Necessary and sufficient — a KKT point is the global minimum |
| Non-convex, qualification holds | Necessary only — candidates need second-order tests or comparison |
| Qualification fails (e.g. cusp) | May fail even at a true minimum — gradients misdescribe the region |
| Linear constraints | No qualification needed; KKT is automatically necessary |
For non-convex problems the analogue of Chapter 19's Hessian test is the second-order sufficient condition: at a KKT point, if the Hessian of the Lagrangian \(\nabla_{\mathbf{x}\mathbf{x}}^2\mathcal{L}\) is positive definite on the subspace tangent to the active constraints, then \(\mathbf{x}^\star\) is a strict local minimum. Note the two changes from the unconstrained case: it is the Lagrangian's curvature, not the objective's, and it need only be positive on the directions we are actually allowed to move in — curvature in forbidden directions is irrelevant.
Lagrangian Duality
The multipliers deserve promotion from bookkeeping devices to variables in their own right. Fix \(\boldsymbol{\lambda}\) and \(\boldsymbol{\mu}\), then minimise the Lagrangian over \(\mathbf{x}\) with the constraints dropped entirely. The result is the dual function:
Two properties make this construction valuable. First, \(q\) is always concave — even when the original problem is horribly non-convex — because it is an infimum of functions affine in \((\boldsymbol{\lambda},\boldsymbol{\mu})\). The dual problem is therefore a convex problem, always. Second, at any feasible \(\mathbf{x}\) and any \(\boldsymbol{\mu} \ge \mathbf{0}\), the added terms \(\sum\lambda_i h_i + \sum\mu_j g_j\) are \(\le 0\), so the Lagrangian never exceeds \(F\). This gives weak duality.
Every dual value is a lower bound on the optimal primal value — no exceptions, no assumptions. The shortfall \(F(\mathbf{x}^\star) - q(\boldsymbol{\lambda}^\star, \boldsymbol{\mu}^\star) \ge 0\) is the duality gap. For a convex program satisfying Slater's condition the gap closes — strong duality — and solving the dual solves the primal.
Weak duality is the workhorse even when the gap does not close. Any \((\boldsymbol{\lambda}, \boldsymbol{\mu} \ge \mathbf{0})\) you can name yields a certified lower bound on the best achievable value, and a feasible \(\mathbf{x}\) yields an upper bound. The interval between the two is a rigorous, computable measure of how far from optimal you might be — which is precisely how branch-and-bound prunes its tree (Chapter 16), and how a practitioner knows when to stop. Note also that this generalises LP duality (Chapter 10): there the gap is always zero, the special case of a convex program with affine everything.
Penalty & Barrier Methods
Theory in hand, we need algorithms. The most direct idea is to abolish the constraints — fold them into the objective as a cost for misbehaviour, then apply the unconstrained machinery of Chapter 20 unchanged. Two opposite ways of doing this give the two classical families.
The exterior penalty method charges for violation. Add a term that is zero inside the feasible region and grows steeply outside it, then solve a sequence of unconstrained problems with the penalty parameter \(\rho\) increasing:
As \(\rho \to \infty\) the penalty for straying grows without bound and the minimisers \(\mathbf{x}_\rho\) approach \(\mathbf{x}^\star\) — but always from outside: every iterate is slightly infeasible, which is fatal if the model is undefined there (a negative thickness, a log of a negative number).
The interior barrier method takes the opposite tack, charging for approaching the boundary from within. Start strictly inside and add a term that blows up at the fence, then decrease the barrier parameter \(\mu\) toward zero:
Every iterate is strictly feasible — the method cannot escape, since the objective becomes infinite at the boundary — so it can be stopped at any time and still return a usable design. The path traced by \(\mathbf{x}_\mu\) as \(\mu\) decreases is the central path, and following it efficiently is the basis of the interior-point methods that revolutionised both linear and nonlinear programming from the 1980s onward.
Both families share one serious flaw. Driving \(\rho \to \infty\) or \(\mu \to 0\) makes the Hessian of the subproblem catastrophically ill-conditioned — and Chapter 20 taught us exactly what a huge condition number does to a gradient method. The very limit that delivers accuracy destroys the solvability of each subproblem.
The augmented Lagrangian (method of multipliers) escapes the trap by combining a penalty with an explicit multiplier estimate, so that convergence no longer requires \(\rho \to \infty\):
Minimise over \(\mathbf{x}\), update the multipliers by the simple rule shown, repeat. Because the \(\boldsymbol{\lambda}\) terms carry the load that the penalty alone would have to carry, a moderate fixed \(\rho\) suffices — accuracy without ill-conditioning.
Feasible Directions & SQP
Penalty and barrier methods dissolve the constraints. The alternative is to respect them at every step — adapting the descent framework of Chapter 20 so that each move stays legal. A direction \(\mathbf{d}_k\) is a feasible direction if a short step along it keeps us in \(\mathcal{S}\); combined with the old descent test, that gives the requirement for a usable direction:
The second condition says: do not move outward through any wall you are already touching. Several classical algorithms implement this idea — Zoutendijk's method finds such a direction by solving an LP at each step; Rosen's gradient projection projects \(-\nabla F\) onto the surface of the active constraints; and the generalised reduced gradient (GRG) eliminates variables using the equalities and runs an unconstrained method on those that remain — the engine inside many spreadsheet solvers.
The dominant modern method takes a different and more elegant route. Recall the logic of Newton's method in Chapter 20: build a quadratic model, minimise it, repeat. Sequential quadratic programming (SQP) applies exactly that logic to the KKT system — model the Lagrangian quadratically, model the constraints linearly, and solve the resulting quadratic program for the step:
Here \(\mathbf{W}_k \approx \nabla_{\mathbf{x}\mathbf{x}}^2\mathcal{L}\) is the Hessian of the Lagrangian, in practice maintained by a BFGS update (Chapter 20-5) rather than computed. Solve for \(\mathbf{d}_k\), line-search along it, update, repeat.
SQP is best understood as Newton's method applied to the KKT conditions, and it inherits the corresponding virtue: near a solution it converges superlinearly, needing only a handful of iterations even on hard problems. It is the default in most professional NLP software. Two details make it work in practice: the curvature used is the Lagrangian's, not the objective's — constraint curvature genuinely matters, as anyone who has optimised on a curved surface knows — and a merit function or filter balances the competing goals of reducing \(F\) and reducing infeasibility, since far from the solution the two conflict.
| Method | Idea | Iterates feasible? | Best suited to |
|---|---|---|---|
| Exterior penalty | Charge for violation, \(\rho \uparrow \infty\) | No | Simple problems; easy to code |
| Barrier / interior point | Charge for nearing the fence, \(\mu \downarrow 0\) | Yes | Large convex problems; LP and QP |
| Augmented Lagrangian | Penalty + multiplier updates | No | Equality-heavy problems; avoids ill-conditioning |
| GRG / gradient projection | Move only along feasible directions | Yes | Mostly linear constraints; spreadsheet solvers |
| SQP | Newton on the KKT system | No (asymptotically) | General smooth NLP — the modern default |
Worked Examples
Problem. Minimise \(F(x,y) = x^2 + y^2\) subject to \(x + y = 4\). Interpret \(\lambda\).
Solution. Form \(\mathcal{L} = x^2 + y^2 + \lambda(x + y - 4)\). Stationarity gives \(2x + \lambda = 0\) and \(2y + \lambda = 0\), so \(x = y = -\lambda/2\) — the symmetry of the objective forces the two variables to be equal. Feasibility then gives \(x + y = -\lambda = 4\), so \(\lambda = -4\) and \(\mathbf{x}^\star = (2, 2)\) with \(F^\star = 8\). Geometrically this is the closest point on the line to the origin, and the contour circle of radius \(\sqrt8\) is tangent to the line there.
Sensitivity check. Replace the right-hand side by \(b\): the same algebra gives \(x = y = b/2\) and \(F^\star(b) = b^2/2\). Then \(\mathrm{d}F^\star/\mathrm{d}b = b = 4\) at \(b = 4\), which matches \(-\lambda = 4\) exactly. So loosening the constraint by one unit costs four units of objective — \(\lambda\) is a genuine exchange rate, not a bookkeeping artefact.
Problem. Minimise \(F(x,y) = x^2 + y^2\) subject to \(xy = 1\).
Solution. With \(\mathcal{L} = x^2 + y^2 + \lambda(xy - 1)\), stationarity gives \(2x + \lambda y = 0\) and \(2y + \lambda x = 0\). Multiply the first by \(x\), the second by \(y\), and subtract: \(2x^2 - 2y^2 = 0\), so \(y = \pm x\). The constraint \(xy = 1\) rules out \(y = -x\) (it would give \(-x^2 = 1\)), leaving \(y = x\) and hence \(x^2 = 1\).
Two feasible candidates survive: \((1, 1)\) and \((-1, -1)\), both with \(F = 2\) and \(\lambda = -2\). The hyperbola has two branches, and by symmetry the nearest point on each is equidistant from the origin — so here the tie is real, and both are global minima. Note what the method did not do: it never told us these were minima rather than maxima. Lagrange conditions are necessary only; here \(F \to \infty\) along each branch, which is what confirms the candidates are minima.
Problem. Minimise \(F(x,y) = (x-3)^2 + (y-2)^2\) subject to \(x + y \le 4\).
Solution. Test the inactive case first: it would give the unconstrained minimum \((3,2)\), but \(3 + 2 = 5 > 4\) is infeasible — so the constraint must be active. Set \(g = x + y - 4 = 0\) and use \(\mathcal{L} = F + \mu g\):
Stationarity: \(2(x-3) + \mu = 0\) and \(2(y-2) + \mu = 0\), giving \(x = 3 - \mu/2\), \(y = 2 - \mu/2\). Substituting into \(x + y = 4\) gives \(5 - \mu = 4\), so \(\mu = 1\). Dual feasibility \(\mu = 1 \ge 0\) ✓ — the constraint pushes the right way, so the candidate is valid.
Hence \(\mathbf{x}^\star = (2.5,\ 1.5)\) with \(F^\star = 0.25 + 0.25 = 0.5\). This is the projection of \((3,2)\) onto the line — the constrained optimum is the closest feasible point to the unconstrained one, and \(\mu = 1\) measures how hard the wall is pushing back.
Problem. Minimise \(F(x,y) = (x-1)^2 + (y-1)^2\) subject to \(x + y \le 4\).
Solution. Same constraint, different objective — and now the answer is completely different. Try \(\mu = 0\) (inactive): stationarity reduces to \(\nabla F = \mathbf{0}\), giving \((1,1)\). Check feasibility: \(1 + 1 = 2 \le 4\) ✓, with slack \(g = -2 < 0\). Complementary slackness \(\mu g = (0)(-2) = 0\) ✓. All KKT conditions hold, so \(\mathbf{x}^\star = (1,1)\), \(F^\star = 0\).
Why the other case fails. Had we assumed the constraint active, we would have forced \(x + y = 4\) and found \(\mu = -2 < 0\), violating dual feasibility — the multiplier's sign is the alarm bell, and it is telling us the "constraint" would have to pull the solution outward to hold it there, which a wall cannot do. Comparing Examples 3 and 4: the same fence matters enormously or not at all, depending entirely on where the unconstrained optimum sits.
Problem. Minimise \(F(x) = x^2\) subject to \(x = 1\) by the quadratic penalty method. Track \(x_\rho\) as \(\rho\) grows.
Solution. The penalised objective is \(P(x,\rho) = x^2 + \rho(x-1)^2\). Setting \(P'(x) = 2x + 2\rho(x-1) = 0\) gives \(x_\rho = \dfrac{\rho}{1+\rho}\).
| \(\rho\) | \(x_\rho = \rho/(1+\rho)\) | Feasible? | \(2\rho(x_\rho - 1)\) |
|---|---|---|---|
| \(1\) | \(0.5000\) | No — violates \(x=1\) | \(-1.000\) |
| \(10\) | \(0.9091\) | No | \(-1.818\) |
| \(100\) | \(0.9901\) | No | \(-1.980\) |
| \(1000\) | \(0.9990\) | No | \(-1.998\) |
Two lessons. First, \(x_\rho \to 1\) but always from below — every iterate is infeasible, exactly as the exterior method promises. Second, the last column converges to \(-2\), which is precisely the exact multiplier: from \(\mathcal{L} = x^2 + \lambda(x-1)\), stationarity \(2x + \lambda = 0\) at \(x^\star = 1\) gives \(\lambda = -2\). The penalty term's derivative is a multiplier estimate in disguise — which is exactly the observation the augmented Lagrangian exploits.
Problem. Minimise \(F(x) = x\) subject to \(x \ge 1\) by the logarithmic barrier method.
Solution. In standard form the constraint is \(g(x) = 1 - x \le 0\), so \(-g = x - 1\) and the barrier objective is \(B(x,\mu) = x - \mu\ln(x - 1)\). Setting \(B'(x) = 1 - \dfrac{\mu}{x-1} = 0\) gives the central path in closed form: \(x_\mu = 1 + \mu\).
So \(\mu = 1 \Rightarrow x = 2\); \(\mu = 0.1 \Rightarrow x = 1.1\); \(\mu = 0.01 \Rightarrow x = 1.01\). The iterates approach \(x^\star = 1\) from inside, and every one of them is strictly feasible — stop whenever you like and the answer is still usable. Check the multiplier: \(\mu/(x_\mu - 1) = \mu/\mu = 1\) for every \(\mu\), matching the exact KKT multiplier from \(\nabla F + u\nabla g = 1 + u(-1) = 0 \Rightarrow u = 1 \ge 0\) ✓.
The catch. \(B''(x) = \mu/(x-1)^2 = 1/\mu\) at \(x_\mu\), which blows up as \(\mu \to 0\). The subproblem grows ever more ill-conditioned exactly as it grows more accurate — the central difficulty of barrier methods, and the reason practical interior-point codes follow the central path in carefully controlled steps rather than driving \(\mu\) to zero at once.
Chapter Summary
Minimise \(F\) over a feasible region; the optimum usually sits on the boundary, where \(\nabla F \ne \mathbf{0}\).
\(\mathcal{L} = F + \sum\lambda_i h_i\): at the optimum \(\nabla F\) is cancelled by constraint gradients, and \(\partial F^\star/\partial b_i = -\lambda_i\) is the shadow price.
Stationarity, feasibility, \(\mu_j \ge 0\), and \(\mu_j g_j = 0\) — each inequality is either active or ignorable.
With a qualification, KKT is necessary; add convexity and it becomes sufficient for a global minimum.
\(q(\boldsymbol{\lambda},\boldsymbol{\mu})\) is always concave and always a lower bound; the gap closes for convex programs.
Penalty from outside, barrier from inside, augmented Lagrangian to dodge ill-conditioning — and SQP, Newton on the KKT system, as the default.
Problems
Convert every constraint to standard form first, then apply the conditions. Difficulty rises down the list.
- Write the general NLP in standard form, and explain why \(\nabla F(\mathbf{x}^\star) = \mathbf{0}\) is no longer necessary at a constrained minimum.
- Explain geometrically why \(\nabla F\) and \(\nabla h\) must be parallel at the optimum of an equality-constrained problem.
- Minimise \(F(x,y) = x^2 + y^2\) subject to \(2x + y = 5\) using Lagrange multipliers, and verify \(\mathrm{d}F^\star/\mathrm{d}b = -\lambda\).
- Find the rectangle of maximum area \(xy\) with perimeter \(2x + 2y = 20\), and interpret \(\lambda\) as the value of an extra unit of perimeter.
- Minimise \(F(x,y,z) = x^2 + y^2 + z^2\) subject to \(x + 2y + 3z = 14\).
- State all four KKT conditions and explain, in one sentence each, what they mean physically.
- Explain complementary slackness and why it does not mean both \(\mu_j\) and \(g_j\) are zero.
- Minimise \(F(x,y) = (x-4)^2 + (y-1)^2\) subject to \(x + y \le 3\). Determine whether the constraint is active and find \(\mathbf{x}^\star\) and \(\mu\).
- Minimise \(F(x,y) = (x-0.5)^2 + (y-0.5)^2\) subject to \(x + y \le 3\), \(x \ge 0\), \(y \ge 0\). Enumerate the active sets and identify which one satisfies all KKT conditions.
- Minimise \(F(x) = x^2\) subject to \(x \ge 2\). Solve by KKT, and confirm the multiplier's sign is consistent with the constraint pushing the solution up.
- Show that if \(\mathbf{x}^\star\) satisfies KKT for a convex program then it is a global minimum, and state where convexity is used.
- State LICQ, and give an example of a feasible region where it fails at a point.
- For \(\min\ x^2 + y^2\) s.t. \(x + y \ge 2\), construct the dual function \(q(\mu)\) explicitly, maximise it over \(\mu \ge 0\), and verify strong duality.
- Prove weak duality: \(q(\boldsymbol{\lambda},\boldsymbol{\mu}) \le F(\mathbf{x})\) for every feasible \(\mathbf{x}\) and every \(\boldsymbol{\mu} \ge \mathbf{0}\).
- Explain why the dual function is concave regardless of the primal's convexity, and why this does not make every problem easy.
- Apply the quadratic penalty method to \(\min\ x^2 + y^2\) s.t. \(x + y = 2\). Find \(\mathbf{x}_\rho\) in closed form and show \(\mathbf{x}_\rho \to \mathbf{x}^\star\) from the infeasible side.
- Apply the log-barrier method to \(\min\ x^2\) s.t. \(x \ge 1\). Find the central path \(x_\mu\), and show \(x_\mu \to 1^{+}\) as \(\mu \to 0\).
- Explain why both penalty and barrier subproblems become ill-conditioned in the limit, connecting your answer to the condition number \(\kappa\) of Chapter 20, and explain how the augmented Lagrangian avoids this.
- State the SQP subproblem and explain why it uses the Hessian of the Lagrangian rather than that of the objective.
- A design has three inequality constraints with multipliers \(\mu = (0,\ 12,\ 0.3)\) at the optimum. Which constraint should the engineer negotiate to relax, and which could be deleted from the model entirely?