Construct lower bounds before solving the primal

Try

Minimize x² subject to x≥2. Write g(x)=2−x≤0 and L(x,λ)=x²+λ(2−x), with λ≥0. Completing the square gives L=(x−λ/2)²+2λ−λ²/4. Its infimum over all real x is q(λ)=2λ−λ²/4. This is a lower bound on every feasible primal objective. Maximizing it gives λ=4 and q=4, matching the primal feasible point x=2. The dual solves a bound-selection problem.

Predict

Predict why the infimum in q is taken over the objective’s domain, not only the primal feasible set. The multipliers penalize or reward constraint violations, and minimizing the Lagrangian over all domain points produces a tractable lower bound. Restricting the infimum to the original feasible set would obscure that mechanism. Predict also whether q can equal negative infinity. It can, when the chosen multipliers leave an unbounded decreasing Lagrangian direction; such a dual point is simply an unusable finite bound.

Experiment

Evaluate q for several nonnegative multipliers in the worked problem. Record both the Lagrangian minimizer and its bound; that minimizer need not be primal feasible.

λ	Minimizer of L over R	q(λ)
0	0	0
2	1	3
4	2	4
6	3	3

Only the middle matching certificate at λ=4 has both zero gap and the correct primal optimum. A larger multiplier does not necessarily produce a stronger bound. Dual optimization balances the terms rather than treating multipliers as penalties that should be increased without analysis.

The next experiment changes the problem to min x subject to x²≤δ. Keep this family separate from the worked min x² example above.

A missing multiplier is not automatically a positive gap

Minimize x subject to x²≤δ. Predict the primal status and whether a finite dual multiplier attains the best bound before changing δ.

Constraint δ-0.2500.2514 Nonnegative multiplier λ00.1250.250.512416Reset dual comparison

Solid navy: q(λ), sampled for1/16≤λ≤4. Dashed red: primal optimum when feasible. Shared vertical range[−5,5]; off-range curve values are clipped. At λ=0 the bound is −∞, not a plotted finite point.

Status: strict-feasible. Primal optimum: -1.00000. Selected q(λ): -1.00000. Lagrangian minimizer: -1.00000; it is primal feasible.

Strict feasibility holds at x=0. The attained optimal multiplier is 0.500000.

Repair the conclusion

Slater is sufficient, not necessary. At δ=0 there is no strict point, yet the values agree; dual attainment fails. At δ<0 the finite-primal-value assumption also fails. Increasing λ is not always improvement: at δ=1 the bound peaks at λ=1/2 and then decreases.

Forty bounded analytic settings, no numerical optimizer or saved state. Derive q by completing the square, then retain your prediction and changed-case proof in the written practice.

Understand

For minimization with g≤0 and h=0, define q(λ,ν)=inf_x[f(x)+λᵀg(x)+νᵀh(x)] with λ≥0. For any feasible x, q≤L(x,λ,ν)≤f(x), proving weak duality even for a nonconvex primal. The dual maximizes q. It is concave because an infimum of affine functions of the multipliers is concave: taking an infimum after a convex combination gives at least the same convex combination of the separate infima.

Strong duality is not automatic in general nonlinear optimization. We prove a precise full-domain version: f and every g_i are real-valued differentiable convex functions on all of R^d; equalities are Ax=b; there is a point x̄ with Ax̄=b and every g_i(x̄)<0; the primal infimum pis a finite real number. Then nonnegative inequality multipliers and free equality multipliers attain dual value p. Primal attainment is not assumed. General extended-valued/common-domain relative-interior versions and refined conditions for affine inequalities are broader theorems; they are not silently included in this proof.

First prove the separation fact we need

Let C be a nonempty open convex subset of finite-dimensional Euclidean space with0 outside C. We claim there is a unit vector v such that v·c≥0 for every c in C. Write D for its closed convex closure. The projection theorem already proves existence and the nearest-point inequality for D.

If0 is outside D, project0 to p. The projection inequality gives p·c≥||p||² for c in D, so v=p/||p|| works. If0 is in D, choose y in C and an open ball of radius r about y contained in C. The points z_k=−y/k lie outside D: otherwise approximate z_k by points of C, and combine each with that ball using weights1/(k+1) and k/(k+1). Convexity puts balls of radius r/(k+1), with centers tending to0, inside C. Eventually such a ball contains0, a contradiction.

Project each z_k onto D at p_k. Since0 lies in D, the distance is at most ||z_k|| and hence ||p_k||≤2||z_k||→0. Normalize v_k=(p_k−z_k)/||p_k−z_k||. The projection inequality gives v_k·(c−p_k)≥0 for every c in D. Compactness of the unit sphere gives a convergent subsequence v_k→v with ||v||=1. Passing to the limit yields v·c≥0. Thus separation follows from the previously proved projection mechanism, including the boundary case where strict separation may fail.

Encode objective, inequalities and equalities together

Delete dependent equality rows after checking their consistency; strict feasibility already ensures consistency. The retained A has full row rank, so there is a linear right inverse B with AB=I. With no equalities, omit these coordinates. Consider the set of triples (u,v,t) for which some x satisfies g_i(x)<u_i, Ax−b=v and f(x)−p*<t.

This set C is nonempty and convex: convexly combine witnesses, use convexity of f and g_i, and use affinity of Ax−b. It is open. To see the equality-coordinate issue explicitly, for a nearby v′ replace a witness x by x+B(v′−v). Differentiability implies continuity of the finitely many functions, so sufficiently small changes preserve their strict margins; sufficiently small changes in u and t do too. Full row rank is what permits arbitrary small equality-residual changes here.

The origin is not in C: a witness there would be strictly feasible with f(x)<p*, contradicting the definition of the primal infimum. Apply the proved separation fact to obtain a nonzero vector (λ,ν,μ) such that

$$\lambda^T u+\nu^T v+\mu t\geq0\qquad\text{for every }(u,v,t)\in C.$$

Increasing any u_i or t preserves membership in C, so λ_i≥0 and μ≥0; a negative coefficient would contradict the inequality along that increasing ray. The equality coefficient ν is unrestricted in sign.

Strict feasibility forces a genuine objective coefficient

Suppose μ=0. At the strict point x̄ choose each u_i strictly between g_i(x̄) and0, set v=0 and take t sufficiently large. Then λ·u≥0 with u strictly negative and λ nonnegative forces λ=0. Because A has full row rank and the functions are finite everywhere, every v is realized by some x and can be accompanied by sufficiently large u,t. Thus ν·v≥0 for every v, forcing ν=0. This contradicts the nonzero separator. Therefore μ>0.

Divide the separator by μ. For any x, let u decrease to g(x), set v=Ax−b and let t decrease to f(x)−p*. Continuity of the separating linear expression gives

$$f(x)+\widehat\lambda^Tg(x)+\widehat\nu^T(Ax-b)\geq p^*,\qquad\widehat\lambda=\lambda/\mu\geq0,\quad\widehat\nu=\nu/\mu.$$

Taking the infimum over every x gives q(λ̂,ν̂)≥p*. Weak duality gives the opposite inequality, hence equality. This one finite multiplier pair attains the dual optimum. The construction never selected a primal minimizer, so it does not establish primal attainment.

Recover KKT only when a primal minimizer exists

If a feasible xattains p, then q≤L(x,λ̂,ν̂)≤f(x)=p=q. All inequalities are equalities. The sum of the nonpositive terms λ̂_i g_i(x) is zero, so each vanishes. Also xglobally minimizes the differentiable Lagrangian, giving ∇f(x)+Σλ̂_i∇g_i(x)+Aᵀν̂=0. This proves KKT necessity under the stated Slater hypotheses and primal attainment. Conversely, for a convex differentiable problem, primal/dual feasibility, stationarity and complementary slackness make x a global Lagrangian minimizer and certify a zero gap; that sufficiency does not require Slater.

For a strict-feasible problem without a primal minimizer, take min exp(−x) subject to −x≤0. Its infimum is0, approached as x→∞ but never reached. The dual at λ=0 equals0 and is attained there; every λ>0 gives infimum−∞. This separates primal attainment from the dual-attainment conclusion.

The Stanford Convex Optimization I Lecture8 transcript provides the primary duality/strict-feasibility and geometric-support reference. The proof above makes the full-domain, equality-rank and boundary-separation steps explicit; the broader relative-domain and complexity refinements remain separately scoped.

When the common domain is an affine space

An equality constraint can force every feasible point into a line. Empty interior in the surrounding plane then says nothing useful about strict feasibility within that line. Relative interior means interior inside the affine hull. For the entire line D consisting of (s,0) for real s, its ordinary interior in R² is empty but its relative interior is D.

Here is a precise extension of the proof above. Suppose the common domain is all of a nonempty affine space D=x₀+range B, where the columns of the n-by-k matrix B are an orthonormal basis for its direction space. The objective f and inequality functions gᵢ are finite convex functions on D whose coordinate pullbacks are differentiable. Keep affine equalities Ax=b, a finite primal infimum, and a point in D satisfying those equalities and all gᵢ strictly negative.

Every x in D has a unique coordinate z in Rᵏ, through x=x₀+Bz. Define F(z)=f(x₀+Bz), Gᵢ(z)=gᵢ(x₀+Bz), and rewrite the equalities as ABz=b−Ax₀. These are now finite differentiable convex functions on the whole coordinate space. Check consistency and delete redundant equality rows as in the full-domain proof. That theorem gives multipliers λ≥0 and ν attaining the primal value. No optimization problem has been relaxed: the coordinate map is a bijection onto the stated domain.

The key equality is

$$\inf_{x\in D}\bigl[f(x)+\lambda^Tg(x)+\nu^T(Ax-b)\bigr]=\inf_{z\in\mathbb R^k}\bigl[F(z)+\lambda^TG(z)+\nu^T(ABz+Ax_0-b)\bigr].$$

Thus the domain-restricted dual attains the same finite optimum. For k=0 the domain is one point: feasibility makes its objective the optimum, and zero multipliers already attain that value. This handles the singleton separately without pretending it has nonempty ambient interior.

If a minimizer exists, coordinate stationarity is ∇F+Σλᵢ∇Gᵢ+(AB)ᵀν=0. For differentiable ambient extensions, this is Bᵀ(∇f+Σλᵢ∇gᵢ+Aᵀν)=0: the residual is normal to the affine domain. Demanding that this ambient residual itself vanish would discard legitimate constrained optima. Its normal component is absorbed by the domain restriction, or by equality multipliers when those defining equalities are written explicitly.

For example, minimize s²+3t on the line D defined by t=0, subject to 2−s≤0. The restricted function is s², the optimum is (2,0), and λ=4. The ambient residual (2s,3)+λ(−1,0)=(0,3) is nonzero but orthogonal to the line. Writing t=0 as an explicit equality instead gives its multiplier ν=−3 and a zero full stationarity residual. Both descriptions certify value 4.

Repair the domain before testing strict feasibility

Minimize s² on points (s,0), with b−s≤0. Predict whether empty ordinary interior prevents strong duality. Then select a multiplier and try to close the gap.

Common domain Whole line: s is realRay: s≥0 (scope challenge) Lower bound b 123 Multiplier λ 012468

Strict feasible point

(3,0), with b−s=−1

Infimizing coordinate in this example

s=λ/2=0.0000

Dual lower bound q(λ)=bλ−λ²/4

0.0000

Primal optimum b²; remaining gap

4.0000; 4.0000

The domain is its entire affine hull. Coordinate reduction to one real variable proves the affine-domain corollary applies.

Compare your reasoning with feedback

Both sets have empty interior in R². Their relative interiors differ: the whole line versus the positive ray. A strict point exists in each, but replacing a ray by a whole line changes the problem in general. For this selected family the infimizer happens to stay in the ray. Explain that fact before reusing its dual formula. The optimal multiplier is 4; feasibility and the algebraic gap supply the certificate.

Reset domain experiment

Temporary, bounded exact-formula practice; no score or progress is recorded.

Scope check. A ray, an open disk, or the domain of a logarithm is not its entire affine hull. Choosing affine coordinates does not turn such a domain into all of Rᵏ. The general relative-interior Slater theorem covers more convex domains, but this corollary proves only the full-affine-domain case. It also does not remove strict inequalities for affine constraints or prove any solver complexity bound. Boyd and Vandenberghe, sections 2.1.3 and 5.2.3 give the relative-interior definition and broader theorem; the coordinate proof here makes its narrower scope explicit.

Changed-case proof practice

Minimize s²+t on the line D defined by t=2s+1, subject to s≥1. Before opening the feedback, give a strict feasible point, reduce to one variable, compute the restricted dual, and explain the ambient stationarity equation. Retain an initial argument, identify any unjustified domain extension, then write a corrected proof.

Feedback and proof criteria

Use x₀=(0,1), direction (1,2), and coordinate s; an orthonormal direction is convenient for the theorem, but any injective affine parametrization works. The reduced objective is s²+2s+1=(s+1)². The point (2,5) is strictly feasible. For λ≥0, infimization of (s+1)²+λ(1−s) gives s=λ/2−1 and q(λ)=2λ−λ²/4. Its maximum is 4 at λ=4, matching the feasible optimum (1,3). At that point the ambient residual of objective and inequality gradients is (2,1)+4(−1,0)=(−2,1), normal to (1,2). For an explicit equality t−2s−1=0, ν=−1 cancels the residual. A correct proof checks the domain bijection, strict feasibility, both infimum calculations and the difference between normal and zero residual. Correct endpoint arithmetic alone is insufficient.

Apply

Return to min x subject to x²≤0. The primal optimum is zero at x=0, but no strictly feasible point exists. For λ>0, q(λ)=inf_x(x+λx²)=−1/(4λ); for λ=0 it is negative infinity. The dual supremum is zero as λ grows without bound, yet no finite multiplier attains it. Thus failed Slater does not necessarily mean a positive gap; it means the theorem’s guarantee is unavailable. This example also explains the absence of KKT multipliers despite primal optimality.

Separate three questions in every example: is the primal optimum attained, is the dual optimum attained, and do their optimal values agree? A proof of one does not settle the other two. Numerical multipliers growing large can be a symptom of a qualification or attainment issue rather than a request to run more iterations blindly.

A common convex domain, including its boundary

The affine-domain result above can be extended without pretending a half-line is an affine space. Let D be a nonempty convex subset of finite-dimensional space. Let f,g₁,…,gₘ be finite convex functions on D, not necessarily differentiable or continuous at its relative boundary. Outside D the objective may be represented as +∞; take the Lagrangian infimum over D, so undefined combinations such as zero times +∞ never occur. Suppose the primal value pis finite, equalities are Ax=b, and x̄ belongs to ri(D), satisfies Ax̄=b, and has every gᵢ(x̄)<0. Then some λ≥0 and free ν attain the dual value p. This version requires strictness for every inequality; the refined rule allowing some affine inequalities to be non-strict is a different theorem.

Why relative interior suffices

Use coordinates on aff(D), so ri(D) is ordinary interior in those coordinates. Delete dependent equality rows after checking consistency. The remaining equality map has full row rank on this coordinate space and a right inverse B. A finite convex function is continuous on the interior of its convex domain. One elementary justification is to enclose a small cube around a point in the domain: convexity bounds the function above by its finitely many vertex values; reflection through the center gives a lower bound on a smaller cube. Comparing secant slopes then bounds the change of the function on an even smaller cube. This gives continuity without assuming a derivative or continuity at a boundary point.

Define C to contain (u,v,t) when some x in D satisfies gᵢ(x)<uᵢ, Ax−b=v, and f(x)−p<t. It is convex. It has nonempty interior: choose u above g(x̄) and t above f(x̄)−p, then vary x as x̄+Bv for small v. Interior membership of x̄ and continuity keep x in D and preserve the strict margins, allowing u,v,t to vary in a small ball. The origin is not in C, since its witness would be feasible with objective below p*.

C need not be open at every witness; this is the precise defect in copying the full-domain argument unchanged. Apply the earlier open-set separation proof to int(C). To extend its inequality to C, choose z in int(C). For every c in C and 0<θ≤1, (1−θ)c+θz is interior: convexly combining c with an interior ball about z produces an interior ball of radius scaled by θ. Let θ decrease to zero. Therefore the separator is nonnegative on all of C.

Write the nonzero separator as (λ,ν,μ). Increasing u or t arbitrarily shows λ≥0 and μ≥0. If μ=0, use x̄, v=0 and strictly negative u between g(x̄) and zero. Then λ·u≥0 forces λ=0. The local right-inverse construction realizes both signs of every sufficiently small equality residual v, so ν·v≥0 for all such v forces ν=0. This contradicts nonzeroness. Hence μ>0. Normalize by μ and let u decrease to g(x), t decrease to f(x)−pfor each x in D. The resulting inequality is L(x,λ/μ,ν/μ)≥p. Taking the infimum over D and combining with weak duality proves equality and dual attainment. Primal attainment was never used.

A boundary example and a failure test

Minimize f(x)=x over D=[0,∞), subject to g(x)=1−x≤0. The strict point x̄=2 lies in ri(D). For λ≥0, q(λ)=inf over x≥0 of (1−λ)x+λ. Thus q(λ)=λ for 0≤λ≤1 and q(λ)=−∞ for λ>1. The maximum 1 at λ=1 equals the primal minimum at x=1. Taking the infimum over all real x would accidentally replace the stated domain-restricted problem and change the dual function for λ<1.

Remove strict feasibility in min x subject to x²≤0 on R. The only feasible point is 0 and p*=0. For λ>0, completing the square gives q(λ)=−1/(4λ); at λ=0 the infimum is−∞. The supremum 0 is approached but never attained by a finite multiplier. Zero gap is therefore not the same assertion as dual attainment.

Written transfer. On D=[0,∞), minimize (x−2)² subject to x≤1. Find a Slater point, an optimal multiplier and the domain-restricted Lagrangian minimizer. Feedback: x̄=1/2 is strict and interior; x=1, λ=2. L=(x−2)²+2(x−1)=x²−2x+2=(x−1)²+1, so its infimum over D is 1 at 1. Record the domain and strict point before invoking the theorem. A zero derivative in the ambient space is not the general nonsmooth KKT condition.

The theorem’s relative-interior setting can be compared with Boyd and Vandenberghe, section 5.2.3, checked 30 October 2026. The proof here states the common-domain convention and supplies the interior-separation extension; it does not assert arbitrary extended-function arithmetic or the refined affine-inequality qualification.

Continue

Use feasibility and bounds before interpreting a solver’s termination label. Continue to Barrier and interior-point methods to see how strict feasible points generate approximate complementary-slackness certificates along a central path. The gap formula will quantify optimization accuracy, while separate theory must bound the work required to find each central point.