Constrained optimisation, Lagrange multipliers, and duality

A training loss, resource budget or scheduling objective becomes a different problem when constraints are added. A boundary optimum can have a nonzero ordinary gradient. A multiplier is useful only with the correct sign convention, feasibility conditions and theorem assumptions. This lesson develops explicit certificates, derives projections and dual bounds, and shows why a stationary report or finite penalty does not automatically solve a constrained problem.

Retrieval check: Module 19 supplies convex supporting inequalities, curvature bounds and gradient descent. Module 18 supplies gradients and Jacobian dimensions. Labs use NumPy and run entirely on the CPU. All multipliers below use inequalities written as g_i(x)≤0 and the Lagrangian sign convention +λ_i g_i(x).

Write a constrained problem as minimise f(x) subject to x∈D, g_i(x)≤0 and h_j(x)=0. The set C of points satisfying every restriction is the feasible set. D is the common domain on which objective and constraints are defined. An infeasible point has no standing as a proposed primal solution, however attractive its objective value. A feasible set may be empty, disconnected, unbounded or a lower-dimensional surface; these properties affect both existence and methods. A continuous objective on a nonempty compact C attains a minimum, while closedness alone does not suffice on an unbounded set.

An inequality is active at x when g_i(x)=0; it is inactive when g_i(x)<0. Equality constraints are always imposed, rather than being switched on by a solver. For the box 0≤x_i≤1, write the lower restriction as −x_i≤0 and the upper as x_i−1≤0. Their gradients are −e_i and +e_i. Reversing one restriction without reversing its multiplier convention changes the stationarity equation. Redundant descriptions can give the same C with different, even nonunique, multiplier representations.

Feasible directions express the local geometry. At a smooth boundary g_i(x)=0, a differentiable feasible curve with velocity d must satisfy ∇g_i(x)ᵀd≤0; equality curves require ∇h_j(x)ᵀd=0. These are necessary linearised tests, not automatically sufficient to construct a curve. Curvature or singular constraints can rule out a direction that passes them. The degenerate equation x²=0 at zero has zero linearisation, yet its feasible set contains only zero. Section 2 explains the missing regularity.

For a nonempty closed convex C⊂Rⁿ, the Euclidean projection P_C(v) is the unique point p∈C minimising (1/2)‖p−v‖². Existence follows by restricting to a sufficiently large closed ball around v containing one feasible point: farther points cannot improve that point’s distance, and the restricted set is compact. Strict convexity of squared distance gives uniqueness, since two distinct minimisers would have a closer midpoint. On nonconvex C nearest points can be nonunique, so the same notation needs an explicit selection rule and does not inherit the convex properties used here.

Projection has a variational characterisation: p=P_C(v) exactly when (v−p)ᵀ(z−p)≤0 for all z∈C. Necessity follows by differentiating squared distance along the feasible segment p+t(z−p) at t=0 from the right. For sufficiency expand ‖z−v‖²=‖p−v‖²+‖z−p‖²−2(v−p)ᵀ(z−p); the last two terms are nonnegative. This supplies a global nearest-point proof, not merely a sampled comparison. Adding the two projection inequalities for v,w yields ‖P_C(v)−P_C(w)‖²≤(v−w)ᵀ(P_C(v)−P_C(w)), hence nonexpansiveness by Cauchy–Schwarz.

For a box the objective separates by coordinate, so scalar clipping gives its exact projection. For the simplex, the common threshold couples coordinates. Sort v into u₁≥…≥u_n and define θ_j=(Σ_{i≤j}u_i−1)/j. Let ρ be the largest index with u_ρ>θ_ρ; then θ=θ_ρ and x_i=max(v_i−θ,0). The selected positive coordinates sum to one, the others lie below the threshold, and the KKT certificate in Section 3 proves nearest-point optimality. There is always an eligible index because u₁>u₁−1. Sorting costs O(n log n), so projection itself has a computational cost.

For equality constraints h:Rⁿ→Rᵐ, the Jacobian J_h(x) has m rows, one gradient transpose per constraint. At a regular feasible point with independent equality gradients, J_h has full row rank m. The tangent space is N(J_h). A constrained differentiable local minimum has zero first-order objective rate along every tangent direction, so ∇f lies in N(J_h)⊥=C(J_hᵀ). Consequently some ν∈Rᵐ satisfies ∇f(x)+J_h(x)ᵀν=0. Define the equality Lagrangian L(x,ν)=f(x)+νᵀh(x). Its x-gradient is precisely this stationarity equation.

The step from tangent vectors to actual nearby feasible curves uses the regular level-set theorem, a consequence of the implicit function theorem. We state that regularity result here; linear algebra alone cannot prove that arbitrary null vectors describe the actual surface at a singular point. This is why full row rank is part of the necessity theorem. Equality multipliers have unrestricted signs because an equality has neither a one-sided interior nor an inequality orientation. Multipliers are attached to the stated equations, so rescaling an equation rescales its multiplier inversely.

In general, for f(x)=(1/2)xᵀQx+cᵀx and Ax=b, with symmetric Q, stationarity and feasibility form the block system Qx+Aᵀν=−c, Ax=b. The matrix is [[Q,Aᵀ],[A,0]], often called the saddle-point system. If Q is positive definite and A has independent rows, it is invertible: a homogeneous solution obeys Qd+Aᵀw=0 and Ad=0; multiplication by dᵀ gives dᵀQd=0, hence d=0 and then Aᵀw=0 implies w=0. Solve this system rather than form an explicit inverse.

Positive definiteness on all of Rⁿ is sufficient but stronger than necessary. Only directions preserving Ax=b are relevant to primal uniqueness: if dᵀQd>0 for every nonzero d∈N(A), the objective is strictly convex along that affine feasible space. With independent rows this also makes the block system invertible by the same argument restricted to N(A). Curvature normal to the feasible space can be negative without harming this particular constrained minimum. General nonlinear constraints add curvature through the Hessian of the Lagrangian, so checking ∇²f alone along a curved surface may be inadequate.

Stationarity is a necessary candidate condition under regularity, not an unconditional minimum certificate. Minimise x²+y² on the unit circle x²+y²=1: every feasible point has the same value, and a suitable multiplier satisfies stationarity everywhere. For minimising x on that circle, stationarity produces both (−1,0) and (1,0); one is the minimum and one the maximum. Compare values, use suitable second-order conditions, or use a convex global certificate when its assumptions hold. The circle equality is nonlinear and its feasible set is not convex.

Multipliers can measure optimal-value sensitivity when a suitable differentiable solution branch and value function exist. With h(x)−b=0 written inside L, the derivative of V with respect to b is −ν*, not +ν*. In the line example V′(b)=b/2=−ν*. This follows by differentiating f(x*(b)), using stationarity and the derivative J_h x*′=1. At switches, degeneracies or nondifferentiable value functions, a unique ordinary sensitivity derivative may not exist. A multiplier cannot be interpreted as a universal finite-change price without checking these conditions and the perturbation convention.

For differentiable f,g_i,h_j use L(x,λ,ν)=f(x)+Σλ_i g_i(x)+Σν_j h_j(x). The Karush–Kuhn–Tucker conditions are primal feasibility g_i≤0,h_j=0; dual feasibility λ_i≥0; complementarity λ_i g_i=0 for each inequality; and stationarity ∇f+Σλ_i∇g_i+Σν_j∇h_j=0. Each line has a separate purpose. Complementarity permits positive multipliers only on active inequalities, but permits zero multipliers on active ones too. Inequality signs belong to the chosen g≤0 convention; equality ν remains unrestricted.

For smooth problems, a local optimum has KKT multipliers under a suitable constraint qualification. One sufficient qualification is linear independence of the equality gradients and gradients of all active inequalities at the point, abbreviated LICQ. It excludes redundant active gradients and singular descriptions. We state the qualified necessity theorem rather than derive it from an unproved direction argument. Other qualifications can be weaker, so failure of LICQ does not establish that no multipliers exist. Conversely an unqualified optimum need not possess them, as the singular equality example demonstrated.

Convex KKT conditions provide a global sufficient certificate: assume f and all g_i are differentiable convex on a common convex domain and h=Ax−b is affine. At a feasible KKT point x*, the Lagrangian for its λ*,ν* is convex because λ*≥0. Stationarity and the convex supporting inequality imply L(x,λ*,ν*)≥L(x*,λ*,ν*)=f(x*) for all domain points. For a feasible x, L(x,λ*,ν*)≤f(x). Combining gives f(x)≥f(x*). This proof needs no constraint qualification for sufficiency; the qualification enters when asserting that an optimum must have such a certificate.

For the simplex projection in Section 1 take g_i(x)=−x_i and h(x)=Σx_i−1. Stationarity is x_i−v_i+θ−λ_i=0. With x_i=max(v_i−θ,0), choose λ_i=max(θ−v_i,0). Both signs and complementarity hold. For v=(1.2,.4,−.2), x*=(.9,.1,0), θ=.3 and λ=(0,0,.5). Squared distance is strongly convex and the simplex is convex, so this certificate proves the unique global projection. It also explains why the shared threshold is not an arbitrary normalisation recipe.

Resource allocation often uses a budget inequality Σx_i≤B along with nonnegativity. Minimise (1/2)Σ(x_i−a_i)² with a=(3,1), B=2. The budget is active at x=(2,0), its multiplier is 1, and both lower-bound multipliers are zero. Stationarity is x−a+λ_B(1,1)−λ_lower=0; the second coordinate’s zero is active despite its zero lower price. Increasing B slightly below 2 has value derivative −λ_B=−1 at B=2 in this example, reflecting decreased loss from a relaxed upper budget. The active set can change as B crosses this value.

Outside convexity, KKT points can be maxima or saddles. For f(x)=−x² on −1≤x≤1, x=0 with both multipliers zero satisfies KKT, but the global minimum value −1 occurs at the endpoints. All active-gradient qualification concerns at zero are harmless because there are no active inequalities, yet sufficiency still fails: necessity regularity cannot supply missing objective convexity. A numerical residual table should therefore identify the theorem under which the residuals are being used, rather than label every small stationarity number “global optimum.”

Fix λ≥0 and any ν. The dual function q(λ,ν)=inf_{x∈D}L(x,λ,ν) minimises the Lagrangian over the whole domain D, without imposing the primal constraints again. Keeping those restrictions inside the infimum generally computes a different object. The dual value may be −∞; evaluating L at one convenient x gives an upper bound on this infimum, not a certified lower bound on the primal optimum. When computing q analytically, verify the minimisation or bound it in the required direction.

Weak duality follows directly. For every primal-feasible x, λ_i g_i(x)≤0 and νᵀh(x)=0, hence q(λ,ν)≤L(x,λ,ν)≤f(x). Therefore q(λ,ν)≤p*, the primal infimum. This holds for nonconvex objectives and constraints as well; its essential ingredients are the multiplier signs, feasibility and a genuine domain infimum. The dual problem maximises q over λ≥0,ν unrestricted, with optimal supremum d*≤p*. Equality of these two optimal values is strong duality, which requires more than this elementary bound.

The dual function is concave in the multipliers even when the primal problem is nonconvex. For two multiplier vectors and t∈[0,1], each Lagrangian at fixed x is affine in those vectors. Its mixed value is at least t times the first infimum plus (1−t) times the second infimum; taking an infimum over x preserves that lower bound. Thus q at the mixture is at least the mixture of q values, the concave inequality. Extended values of −∞ require care, but do not make an arbitrary nonconvex primal easy to solve or eliminate a duality gap.

For the simplex squared-distance problem, take equality θ and lower-bound vector λ≥0. Minimising L over Rⁿ gives x=a−θ1+λ and q(θ,λ)=θ(Σa_i−1)−λᵀa−(1/2)‖θ1−λ‖². At θ=.3 and λ=(0,0,.5) this is .11, matching f(.9,.1,0). The minimiser of L happens to be primal feasible at this optimal certificate, but primal feasibility was not imposed while deriving q. At other multipliers the Lagrangian minimiser can violate the simplex; that is allowed in the dual infimum.

A feasible candidate x and valid dual bound q give 0≤f(x)−p*≤f(x)−q. The computable primal-dual gap is therefore an objective-accuracy certificate even if the primal optimiser is not known, provided q truly is a lower bound and x is feasible. An infeasible candidate can have f(x)<q without violating weak duality, because the theorem never compared infeasible objective values. A negative inequality multiplier likewise invalidates the bound’s sign argument. Report feasibility residuals and dual-bound validity alongside a candidate difference.

If a computed q is approximate, an upper-biased approximation is unsafe as a lower certificate. Suppose a Lagrangian minimiser solve returns value L(x_trial,λ,ν); this is ≥q, so it cannot simply replace q in a certified gap. A proven lower error allowance can repair it: if L_trial−q≤ε, then L_trial−ε is a valid lower bound. In small quadratics complete the square and solve accurately with suitable error analysis. In larger systems a useful approximate numerical trace is still distinct from a rigorous bound unless its error direction is controlled.

For the standard finite-dimensional convex problem with convex finite-valued f,g_i on Rⁿ and affine equalities Ax=b, a useful sufficient Slater condition is existence of a point x̄ satisfying Ax̄=b and every g_i(x̄)<0. With a finite primal optimal value, this condition gives strong duality and an attained dual optimum. This is the qualified Slater theorem, stated here rather than proved from projection or gradient descent. Its full treatment uses a separating-hyperplane argument. The original reading provides that theorem; our lower-bound and KKT sufficiency proofs stand independently of it.

For functions with restricted convex domains, a corresponding condition uses a feasible point in the relative interior of the common domain, rather than demanding interior in the whole ambient space. Relative interior means interior within its affine hull. The domain and theorem version must be stated: a simplex has empty ambient interior yet nonempty relative interior within its sum-one hyperplane. Some affine inequalities admit weaker refined Slater versions, but the stricter finite-valued version above is sufficient for this lesson’s examples. Do not transform a sufficient condition into an unconditional equivalence.

Strong duality compares infimum and supremum values. It does not, by itself, say a primal minimiser is attained, nor that each multiplier is unique. For example minimise exp(x) on R with no constraints: the primal infimum and unconstrained dual value are zero, but no finite x attains that value. If the convex problem has an attained primal optimum and attained dual optimum with equal values, the chain q≤L≤f forces complementarity and global Lagrangian minimisation. In differentiable problems with the stated domain assumptions, stationarity then produces KKT. Primal attainment remains a separate fact to establish.

Failure of Slater is inconclusive, rather than a proof of a positive gap. Minimise x² subject to x=0 and x≤0. No strict inequality point can satisfy the equality, yet p*=0 and the zero multipliers yield q=0. Thus strong duality holds despite this version of Slater failing. The equation and inequality are partly redundant. This example also distinguishes the geometry of the feasible set from a particular algebraic description and explains why other constraint qualifications or refined theorems may work when a simple condition does not.

Consider instead minimise x subject to x²≤0. The only feasible point is zero with p*=0, and there is no strict feasible point. For λ>0, q(λ)=inf_x(x+λx²)=−1/(4λ); at λ=0 it is −∞. Its supremum is zero as λ→∞, so strong duality holds as equality of values, but no finite dual multiplier attains it. KKT would require 1+2λx=0 at x=0 and is impossible. This example separates zero gap, dual attainment and multiplier necessity; those three statements must not be collapsed into one label.

Conversely strict feasibility alone cannot replace convexity. For minimise −x² on −1≤x≤1, x=0 is strictly feasible for the two affine inequalities. Nevertheless every Lagrangian over R retains its negative quadratic leading term, so q=−∞ for every λ≥0 and d*=−∞ while p*=−1. The convex Slater theorem does not apply because the objective is concave. A feasible interior point and a KKT stationary point cannot make this problem globally convex. Lab 3 exposes exactly this invalid inference.

Dual multipliers have a qualified perturbation interpretation. Write inequalities g_i(x)≤u_i and equalities h(x)=v. An optimal original dual pair gives V(u,v)≥V(0,0)−λᵀu−νᵀv when the original primal-dual values match: evaluate that pair’s shifted dual lower bound. This is a supporting bound on the value function. If V is differentiable, its derivatives equal the corresponding negative multipliers; otherwise several dual optima can supply different supporting slopes. A positive upper-budget multiplier describes the local value of relaxing that budget in the stated units, not a fixed price valid for every finite perturbation.

For a nonempty closed convex C and differentiable f, projected gradient uses x⁺=P_C(x−α∇f(x)), starting from a feasible x and choosing α>0. Exact projection makes every iterate feasible. The projection variational inequality with z=x gives ∇f(x)ᵀd≤−‖d‖²/α, where d=x⁺−x. Combine with the L-Lipschitz-gradient descent lemma to obtain f(x⁺)≤f(x)−(1/α−L/2)‖d‖². Thus 0<α<2/L gives strict decrease whenever the projected update moves, assuming the smoothness bound covers feasible segments. This is a statement about the feasible update, not the unprojected proposal.

Define the projected-gradient mapping G_α(x)=(x−P_C(x−α∇f(x)))/α. Its zero condition is equivalent to ∇f(x)ᵀ(z−x)≥0 for all z∈C by the projection characterisation. If f is convex, its supporting inequality makes this a global minimiser certificate. Ordinary ∇f can remain nonzero at a boundary. The mapping depends on α and the projection metric, and a small computed mapping needs an appropriate error bound before it becomes a distance promise. A zero result caused by rounding or inaccurate projection is not the exact mathematical fixed-point statement.

For convex f and α≤1/L, compare the projection inequality with a minimiser x*. Convex support at x and smooth upper control at x⁺ give f(x⁺)−f(x*)≤∇f(x)ᵀ(x⁺−x*)+(L/2)‖d‖². The projection inequality bounds the first term by (x−x⁺)ᵀ(x⁺−x*)/α. Expanding this dot product gives the telescoping bound f(x⁺)−f(x*)≤(‖x−x*‖²−‖x⁺−x*‖²)/(2α), after dropping the nonpositive term −(1/α−L)‖d‖²/2. Summation and objective monotonicity yield f(x_k)−f(x*)≤‖x₀−x*‖²/(2αk). State existence of x*, convexity, exact projection and fixed α together with the rate.

Penalty methods instead change the objective. For an equality h=0, squared penalty f+(ρ/2)‖h‖² discourages violations but generally leaves nonzero violations at finite ρ. Minimise (x−2)²/2 subject to x=0: the true answer is zero, whereas the penalised minimiser is 2/(1+ρ)>0 for every finite positive ρ. Its constraint gradient contribution approaches the required equality multiplier as ρ grows, but the iterate is still infeasible. Large ρ can also introduce severe curvature conditioning. Exact projection and a finite smooth penalty therefore solve different intermediate problems.

Some nonsmooth penalties can be exact under appropriate assumptions and a sufficiently large weight related to multipliers. In that same scalar example, (x−2)²/2+ρ|x| has minimiser zero for ρ≥2, as the left derivative −2−ρ≤0 and right derivative −2+ρ≥0 bracket zero there and the objective is convex. This illustrative exactness does not make every finite squared penalty exact or remove the need for nonsmooth optimality treatment. Domain violations that make f undefined must still be prevented; a penalty cannot evaluate a logarithm at an invalid point.

The full QP workflow is to specify Q,c,C, check convexity and feasibility, derive an analytic candidate where possible, run a method with its step and projection contract, then check the resulting primal and dual quantities. Lab 3 deliberately supplies an infeasible point that passes stationarity and a negative multiplier that invalidates a dual bound. Tolerances should be stated in the units of each equation; rescaling constraints alters raw residuals and multipliers. Solver termination, mathematical feasibility and certified objective accuracy remain separate conclusions.

The explorer uses the two-coordinate simplex x+y=1, x,y≥0 and half-squared distance to a=(a₁,a₂). Its exact projection has x=clip((a₁−a₂+1)/2,0,1), y=1−x. Move a through an active-set switch, then choose an infeasible candidate or negative-multiplier fault. The displayed stationarity and dual expressions are recomputed for that candidate; a small stationarity residual or candidate difference cannot bypass the feasibility and sign checks.

The same foundations support allocation, constrained learning and support-vector formulations later. Applications can add nonsmooth losses, very large sparse systems or noisy gradients, which require their own method contracts. This lesson’s outcome is a complete small convex certificate and a justified feasible algorithm, together with precise reasons why a nonconvex KKT point, failed qualification or finite penalty cannot inherit those conclusions automatically.

Lab 1 · Box and simplex projections

Download lab1_box_and_simplex.py

"""Euclidean projections with feasibility and variational checks; NumPy only."""
import numpy as np


def simplex_projection(v):
    v = np.asarray(v, dtype=float)
    if v.ndim != 1 or len(v) == 0 or not np.all(np.isfinite(v)):
        raise ValueError("a nonempty finite vector is required")
    ordered = np.sort(v)[::-1]
    thresholds = (np.cumsum(ordered) - 1.0) / np.arange(1, len(v) + 1)
    eligible = np.flatnonzero(ordered - thresholds > 0)
    theta = thresholds[eligible[-1]]
    return np.maximum(v - theta, 0.0), theta


if __name__ == "__main__":
    np.set_printoptions(precision=8, suppress=True)
    v = np.array([1.2, 0.4, -0.2])
    lower, upper = np.zeros(3), np.ones(3)
    box = np.clip(v, lower, upper)
    simplex, theta = simplex_projection(v)
    clip_then_normalise = box / box.sum()
    print("input:", v)
    print("box projection:", box)
    print("simplex projection:", simplex, "threshold:", f"{theta:.8f}")
    print("clip then normalise:", clip_then_normalise)
    print("squared distances: projection=%.8f shortcut=%.8f" % (
        np.sum((simplex-v)**2), np.sum((clip_then_normalise-v)**2)))
    assert np.all(simplex >= 0) and abs(simplex.sum()-1) < 1e-12
    assert np.sum((simplex-v)**2) < np.sum((clip_then_normalise-v)**2)
    vertices = np.eye(3)
    variational = (vertices-simplex) @ (v-simplex)
    print("(v-projection) dot (vertex-projection):", variational)
    assert np.max(variational) < 1e-12
    for vector in [np.array([-3., -2., -1.]), np.zeros(3), np.array([2., 2., 2.])]:
        p, t = simplex_projection(vector)
        print("input", vector, "->", p, "threshold", f"{t:.8f}")
        assert np.all(p >= 0) and abs(p.sum()-1) < 1e-12
    print("PASS: feasible nearest points; normalisation shortcut is not projection")

input: [ 1.2  0.4 -0.2]
box projection: [1.  0.4 0. ]
simplex projection: [0.9 0.1 0. ] threshold: 0.30000000
clip then normalise: [0.71428571 0.28571429 0.        ]
squared distances: projection=0.22000000 shortcut=0.28897959
(v-projection) dot (vertex-projection): [ 0.   0.  -0.5]
input [-3. -2. -1.] -> [0. 0. 1.] threshold -2.00000000
input [0. 0. 0.] -> [0.33333333 0.33333333 0.33333333] threshold -0.33333333
input [2. 2. 2.] -> [0.33333333 0.33333333 0.33333333] threshold 1.66666667
PASS: feasible nearest points; normalisation shortcut is not projection

Derive both nearest points and predict the threshold before running. Compare squared distances with the normalisation shortcut. Testing every simplex vertex proves the variational inequality for all its convex combinations in this particular finite simplex.

Lab 2 · Feasible projected-gradient descent

Download lab2_projected_gradient.py

"""A convex simplex QP: feasible iterates and a projected-gradient residual."""
import numpy as np
from lab1_box_and_simplex import simplex_projection

if __name__ == "__main__":
    np.set_printoptions(precision=8, suppress=True)
    a = np.array([1.2, .4, -.2])
    target, _ = simplex_projection(a)
    x = np.ones(3) / 3
    eta = .5  # L=1; eta<=1/L supports the stated convex gap bound.
    objective = lambda z: .5 * np.sum((z-a)**2)
    previous = objective(x)
    print("analytic optimum:", target, "objective:", f"{objective(target):.8f}")
    for k in range(1, 31):
        proposed = x-eta*(x-a)
        updated, _ = simplex_projection(proposed)
        projected_residual = np.linalg.norm(x-updated) / eta
        assert np.min(updated) >= 0 and abs(updated.sum()-1) < 1e-12
        current = objective(updated)
        assert current <= previous+1e-14
        x, previous = updated, current
        if k in (1, 2, 5, 10, 30):
            print("k=%2d x=%s objective=%.10f step-mapping-norm=%.3e" % (
                k, x, current, projected_residual))
    at_optimum, _ = simplex_projection(target-eta*(target-a))
    print("ordinary gradient at optimum:", target-a)
    print("projected-gradient mapping at optimum:", (target-at_optimum)/eta)
    print("unconstrained update from optimum:", target-eta*(target-a))
    assert np.linalg.norm(x-target) < 1e-8
    assert np.linalg.norm(target-at_optimum) < 1e-12
    print("PASS: feasible descent; boundary optimum need not have zero ordinary gradient")

analytic optimum: [0.9 0.1 0. ] objective: 0.11000000
k= 1 x=[0.7 0.3 0. ] objective=0.1500000000 step-mapping-norm=9.933e-01
k= 2 x=[0.8 0.2 0. ] objective=0.1200000000 step-mapping-norm=2.828e-01
k= 5 x=[0.8875 0.1125 0.    ] objective=0.1101562500 step-mapping-norm=3.536e-02
k=10 x=[0.89960938 0.10039063 0.        ] objective=0.1100001526 step-mapping-norm=1.105e-03
k=30 x=[0.9 0.1 0. ] objective=0.1100000000 step-mapping-norm=1.054e-09
ordinary gradient at optimum: [-0.3 -0.3  0.2]
projected-gradient mapping at optimum: [ 0. -0.  0.]
unconstrained update from optimum: [ 1.05  0.25 -0.1 ]
PASS: feasible descent; boundary optimum need not have zero ordinary gradient

Check every iterate’s sum, nonnegativity and objective decrease. Explain the distinction between the raw gradient and the projected mapping at x*. A residual measured before an update belongs to that starting iterate, rather than the newly accepted point.

Lab 3 · KKT duality and penalty faults

Download lab3_kkt_and_dual_faults.py

"""Check all KKT residuals, a dual bound, and qualifications; NumPy only."""
import numpy as np

a = np.array([1.2, .4, -.2])


def report(label, x, lam, nu):
    gradient = x-a
    stationarity = gradient + lam - nu
    equality = abs(x.sum()-1)
    inequality = max(0.0, -float(x.min()))
    dual_feasibility = max(0.0, -float(nu.min()))
    complementarity = np.max(np.abs(nu*x))
    f = .5*np.sum((x-a)**2)
    q = lam*(a.sum()-1)-nu@a-.5*np.sum((lam-nu)**2)
    print(label)
    print("  residuals: equality=%.3e inequality=%.3e dual=%.3e stationarity=%.3e complementarity=%.3e" % (
        equality, inequality, dual_feasibility, np.linalg.norm(stationarity), complementarity))
    print("  objective=%.8f dual=%.8f candidate difference=%.8f" % (f, q, f-q))
    valid_dual = dual_feasibility == 0
    feasible = equality < 1e-12 and inequality == 0
    print("  dual bound valid:", valid_dual, "candidate feasible:", feasible)
    return feasible and valid_dual and max(np.linalg.norm(stationarity), complementarity) < 1e-12


if __name__ == "__main__":
    np.set_printoptions(precision=8, suppress=True)
    assert report("correct certificate", np.array([.9, .1, 0]), .3, np.array([0., 0., .5]))
    assert not report("infeasible despite matching stationarity", np.array([1., .2, 0]), .2, np.array([0., 0., .4]))
    assert not report("negative lower-bound multiplier", np.array([.9, .1, 0]), .3, np.array([0., 0., -.5]))
    print("qualification failure: minimise x subject to x^2=0")
    print("  only feasible x=0; constraint gradient=0; stationarity 1+lambda*0 cannot vanish")
    print("  q(lambda)=-1/(4*lambda) for lambda>0; supremum 0, never attained")
    for lam in (1., 10., 100.):
        print("  lambda=%.0f dual bound=%.8f" % (lam, -1/(4*lam)))
    print("nonconvex KKT false certificate: minimise -x^2 subject to -1<=x<=1")
    print("  x=0, multipliers=0 pass KKT; f=0, but x=1 gives f=-1")
    print("  on R, every Lagrangian remains a downward quadratic: dual value=-infinity")
    for rho in (1., 10., 100.):
        # f=.5*(x-2)^2, equality x=0; squared penalty rho*x^2/2.
        x = 2/(1+rho)
        print("squared penalty rho=%.0f minimiser=%.8f equality violation=%.8f" % (rho, x, abs(x)))
        assert x > 0
    print("PASS: stationarity alone fails; qualification, convexity and feasibility matter")

correct certificate
  residuals: equality=0.000e+00 inequality=0.000e+00 dual=0.000e+00 stationarity=7.850e-17 complementarity=0.000e+00
  objective=0.11000000 dual=0.11000000 candidate difference=-0.00000000
  dual bound valid: True candidate feasible: True
infeasible despite matching stationarity
  residuals: equality=2.000e-01 inequality=0.000e+00 dual=0.000e+00 stationarity=5.551e-17 complementarity=0.000e+00
  objective=0.06000000 dual=0.10000000 candidate difference=-0.04000000
  dual bound valid: True candidate feasible: False
negative lower-bound multiplier
  residuals: equality=0.000e+00 inequality=0.000e+00 dual=5.000e-01 stationarity=1.000e+00 complementarity=0.000e+00
  objective=0.11000000 dual=-0.39000000 candidate difference=0.50000000
  dual bound valid: False candidate feasible: True
qualification failure: minimise x subject to x^2=0
  only feasible x=0; constraint gradient=0; stationarity 1+lambda*0 cannot vanish
  q(lambda)=-1/(4*lambda) for lambda>0; supremum 0, never attained
  lambda=1 dual bound=-0.25000000
  lambda=10 dual bound=-0.02500000
  lambda=100 dual bound=-0.00250000
nonconvex KKT false certificate: minimise -x^2 subject to -1<=x<=1
  x=0, multipliers=0 pass KKT; f=0, but x=1 gives f=-1
  on R, every Lagrangian remains a downward quadratic: dual value=-infinity
squared penalty rho=1 minimiser=1.00000000 equality violation=1.00000000
squared penalty rho=10 minimiser=0.18181818 equality violation=0.18181818
squared penalty rho=100 minimiser=0.01980198 equality violation=0.01980198
PASS: stationarity alone fails; qualification, convexity and feasibility matter

Report all five displayed residual quantities, including separate equality and inequality feasibility. Explain the infeasible candidate’s negative difference from a valid dual bound, the invalid negative multiplier, and the qualified theorem failures. Keep the two imported projection scripts together when downloading Lab 2.

Exercises 1–12 are required. Optional Exercises 13–14 add 35 minutes beyond the twelve-hour core schedule.

Use the duality and constrained-minimisation chapters in the authors’ Convex Optimization companion. Read the qualified Slater theorem as a theorem with hypotheses, then compare it with the direct weak-duality and convex KKT proofs above.

Specify a feasible set, derive projections, solve one line-constrained quadratic, and write all KKT conditions with the g≤0 sign convention. Prove weak duality and convex KKT sufficiency, and recognise exactly when Slater supplies a further theorem.

Exit task: complete the simplex QP certificate, derive one projected step and its decrease coefficient, and diagnose the singular qualification and nonconvex stationary examples without conflating gap, attainment and feasibility.

Ready to move on: you can connect constrained algorithms to feasible geometry and certificates. Probability next develops explicit models, conditioning and uncertainty, rather than treating numerical frequencies as unspecified mathematical facts. See the course overview.