The earlier duality unit verified certificates once suitable multipliers had been found. This unit explains why such multipliers exist, for finite-dimensional linear models.
Motivation
An unsuccessful search for a feasible point does not prove infeasibility. Likewise, repeatedly finding better lower bounds does not prove that one of them reaches the primal value. A theorem of alternatives resolves the first problem: exactly one of a feasible decision and a separating multiplier can exist. Strong duality resolves the second: a finite optimum has an attaining multiplier.
The existence arguments depend on a property special to finite linear systems. A cone generated by finitely many vectors is closed. Closedness lets a point outside the cone have a closest point, and the displacement to that closest point gives a separating linear functional. We will prove these steps rather than invoking separation as an unexplained geometric picture.
Sensitivity then becomes a consequence of certificates. A feasible dual multiplier remains feasible when only the right-hand side changes, so it gives a lower bound on the minimization value everywhere. An optimal multiplier gives a supporting lower bound at the original right-hand side. That bound is an exact affine formula only while an appropriate primal basis stays feasible. At a change of active basis, several supporting slopes may coexist.
Definitions
Definition 5.1.1
(Equality-form primal, dual, and generated cone)
Use the minimization convention
The multiplier is unrestricted in sign because the primal constraints are equalities. For vectors , their generated cone is . A theorem of alternatives says exactly one of two specified systems is feasible.
The Euclidean inner product is used in the geometric proof. Its choice does not restrict the LP theorem: the cone and feasibility statements themselves do not depend on an algorithmic norm. Empty systems and zero columns are allowed. A cone contains zero, is convex, and is closed under multiplication by nonnegative scalars; closedness as a topological set still requires proof.
The value function is the optimal value when the primal is feasible with finite infimum. A vector supports it at if wherever the perturbed value is finite. Such a supporting vector is sometimes called a subgradient. It need not be a unique ordinary derivative.
Theorem/proposition
Theorem 5.1.2
(Farkas' alternative)
For a real finite matrix and vector , exactly one of the following holds:
The second vector is an infeasibility certificate for the first system.
Theorem 5.1.3
(Strong duality, including attainment)
If is feasible and has finite infimum, its infimum is attained, the dual supremum is attained, and the two values agree. For feasible , equality of objectives is equivalent to
Thus primal feasibility, dual feasibility, and these products are necessary and sufficient for a feasible pair to be jointly optimal.
Finite dimension and finitely many linear constraints are doing real work. A general closed convex feasible set need not attain a finite infimum, and an arbitrary nonlinear optimization problem need not have an attaining dual multiplier.
Proof sketch or proof idea
A finite generated cone is closed
Lemma 5.1.4
(Finitely generated cones are closed)
For vectors , the generated cone is a closed subset of .
Proof
(Reduce to independent supports, then use a continuous inverse)
Any point of a generated cone has a representation using linearly independent generators. To see this, start with a nonnegative representation whose positive-support generators are dependent. Choose a nonzero dependence on that support, reversing its sign if needed so some . Subtract from the coefficients, where is the least positive ratio over positive . All coefficients remain nonnegative and at least one positive coefficient becomes zero. Repeat until the support is independent.
For a fixed independent subset, write its column matrix as . Its coefficient vector is uniquely recovered from its image by . If images converge, their coefficients converge by this continuous formula; nonnegative coefficients have a nonnegative limit. That subset therefore generates a closed cone. There are finitely many independent subsets, and their cones cover the full generated cone by the preceding reduction. A finite union of closed sets is closed. This proves the needed property, including the zero vector represented by the empty subset.
One cannot simply assume that the coefficients of an arbitrary representation stay bounded. For example, with generators and , zero is represented by two equal coefficients that both tend to infinity. The images stay bounded while the coefficients diverge, which is exactly the gap in a naive limit argument. Reducing to an independent support first supplies a continuous left inverse that controls the coefficients. Finiteness of the possible supports also guarantees that one fixed support can be used when analyzing the limit; a union of infinitely many closed sets is in general not closed, so "finite" is not a decorative word here.
A closest point supplies the alternative
Proof
(Separate from the cone by its nearest point)
Let be the cone of columns of . If , choose a nearest point . It exists because zero is a candidate and the search can be restricted to a sufficiently large closed ball, a compact set. Write . Minimizing squared distance along the segment from toward any gives
Taking and gives . Therefore for all . Set . Every column satisfies , while . This constructs the second system when the first fails. Both cannot hold, since for a feasible nonnegative . Farkas' alternative follows.
The separating certificate can be normalized. Since is strictly negative, replacing by makes the value exactly minus one without changing the nonnegative column inequalities. This is sometimes convenient when checking a computed certificate, but normalization does not replace sign verification. If the right-hand side is zero, the original system always has the solution , so the alternative correctly forbids any strict separating value.
Redundant columns cause no difficulty. They may give several nonnegative representations of the same point, but the support-reduction argument needs only one independent representation. Nor must the feasible set be bounded: the cone itself generally extends to infinity. Compactness is used only for the nearest-point search after excluding points too far away to improve on the zero candidate. This distinction prevents an accidental assumption that conic feasibility is a bounded problem.
Attainment and an optimal multiplier
Proof
(Epigraph cone for attainment, Farkas for the multiplier)
First establish primal attainment. The set of pairs for which some feasible has is the cone generated by together with . It is closed by the cone argument. If feasible objectives decrease to a finite infimum , the pairs converge to , which belongs to the cone. Its representation gives and , hence equality by the definition of infimum.
What is closed here is not an arbitrary projection but a set already written explicitly as a finitely generated cone. A linear image of a general closed set need not be closed, so the same sentence cannot be applied without the generator representation. The extra generator, whose last coordinate is one, represents exactly the nonnegative slack by which an allowed objective level exceeds some feasible cost; without it, the cone would describe only exact cost pairs, not the epigraph set. The representation also allows negative cost coefficients and never assumes that the objective itself is nonnegative.
Take an optimal . Let be its zero coordinates. We claim that
If no such representation existed, apply Farkas to the generator matrix consisting of the columns of , their negatives, and the coordinate vectors for , with right-hand side . The alternative supplies with , on , and .
For sufficiently small positive , the point remains nonnegative: zero coordinates cannot decrease, and initially positive coordinates have a positive margin. It also preserves the equalities. Its objective is smaller, contradicting optimality.
More explicitly, only the finitely many positions with a positive coordinate and a negative direction entry matter; taking the step smaller than the least of their positive ratios keeps every positive coordinate positive. If there are no such positions, any small positive step works. The zero coordinates are protected by the sign condition of the alternative system, the equalities by the null direction, and the decrease by the strictly negative cost product. These three checks correspond separately to feasibility and improvement and cannot be replaced by the phrase "move in a better direction." The claimed representation therefore exists. It gives a dual-feasible and
Weak duality now proves dual attainment and equal values. Finally, for any feasible pair the gap is , a sum of nonnegative products. Equality is equivalent to every product vanishing. This proves the remaining optimality statement.
Proof X-ray
Where multiplier existence enters
The nonnegative-gap identity proves sufficiency but cannot produce a multiplier. Existence comes from Farkas applied to the cost vector and the active coordinate constraints. Its separating vector would be a feasible improving direction, contradicting the primal optimum. Primal attainment is a separate earlier step using the epigraph cone. Keeping these steps separate prevents a circular proof that assumes the certificate it is meant to establish.
Worked examples
Worked example 5.1.5
(An explicit infeasibility multiplier)
The equations and , with nonnegative variables, have identical left sides and different right sides. Take . Then , but . Any proposed feasible point would imply the impossible inequality . The strict negative scalar makes this a finite, directly checkable certificate rather than a record of an unsuccessful search.
Worked example 5.1.6
(Recover the exact sensitivity function)
Minimize with , , and . Feasibility requires . For , take and dual . Its inequalities are , , and . The common objective is .
For , take and . The same three inequalities hold and both objectives equal . Therefore
The old multiplier remains dual feasible beyond two, but gives only lower bound . The primal basis that made it exact has lost feasibility. This is why a valid multiplier is not automatically an exact global sensitivity formula.
Worked example 5.1.7
(A corner has several supporting slopes)
At in the preceding model, every dual vector with is feasible and has objective two. Each produces the valid bound
whenever . For negative , the largest right-hand side comes from the smallest slope one; for positive , it comes from the largest slope three. The value has left derivative one and right derivative three, so no single ordinary derivative exists there. Dual nonuniqueness correctly records this corner rather than an inconsistency.
Concept lensAnalytic
The value function is a maximum of finitely many linear functions
If has full row rank, the dual polyhedron contains no line, so it has finitely many vertices , and a linear objective bounded above on it is maximized at one of them. Strong duality then gives wherever is finite. Hence is convex and piecewise linear. In the example the vertices are and , giving ; the corner at is where both vertices are optimal.
A general basis sensitivity calculation
After deleting redundant equality rows, let an optimal basis satisfy , , and . Changing only to leaves the reduced costs unchanged. The same basis remains optimal exactly throughout its feasibility region , and there its value is . The intersection of these linear inequalities gives an exact polyhedral parameter region. At a zero basic coordinate, some perturbation directions may leave that region immediately. Cost perturbations require a different check because they change the reduced costs themselves.
If all current basic values are strictly positive, a sufficiently small right-hand-side perturbation in any direction preserves them by continuity. The value is then affine on an open neighborhood with gradient equal to this multiplier. If some basic value is zero, that argument no longer gives an open neighborhood; a corner or a feasibility boundary may appear. Thus the same basis calculation explains both a smooth local price interpretation and the limits of that interpretation, without assuming differentiability in advance.
Common mistakes
Common mistake
(Accepting a zero value as an infeasibility certificate)
Infeasibility certificates use a strict sign, not a numerical equality rounded away. A vector with and does not separate from the cone. It may be useful for another purpose, but does not prove this system impossible. For instance always has and , whatever the system.
Common mistake
(Importing dual signs from another convention)
The dual signs belong to the minimization equality convention stated here. They differ from the earlier upper-inequality maximization convention because the models differ. Re-derive weak duality by multiplying feasible inequalities before trusting a remembered sign pattern.
Closedness is necessary for the nearest-point argument. A separate issue is attainment of an objective, and there the polyhedral hypothesis of strong duality cannot be weakened to closed convexity.
Counterexample mode
A closed convex set whose finite infimum is not attained
A plausible claim is that a convex problem with closed feasible set and finite infimum attains it, as linear programs do. Minimize over . The set is convex, as the region above the graph of the convex function on . It is closed despite its strict-looking description: if converges, the are bounded, say by , so ; the limit has and , so it lies in . The points give objective values , so the infimum is , yet every point of has . The attainment proof used closedness of a finitely generated epigraph cone; a curved set has no such description, and this example does not contradict polyhedral attainment.
Summary
A finite generated cone is closed; nearest-point geometry yields Farkas; the epigraph cone yields primal attainment; a second alternative produces an optimal dual multiplier. Sensitivity follows by keeping dual feasibility and tracking the primal basis region. These are distinct logical steps, and each explains a different part of a trustworthy optimality certificate.
Exercises
Quick check
(For with , give a Farkas certificate.)
Solution · Answer
Take scalar . Then , while . This rules out nonnegative solutions even though the equality has unrestricted real solutions.
Quick check
(Minimize subject to , . Find a primal optimum, a dual optimum, and all complementary products.)
Solution · Answer
Take , value six. The dual is maximize subject to and , so attains six. The surplus is and the products are and . A positive dual surplus is compatible with a zero primal variable.
Quick check
(In the sensitivity example, evaluate and . Compare the two bounds obtained by keeping the multiplier .)
Solution · Answer
The values are and , respectively. Keeping gives lower bounds and . The first is exact because the old basis remains feasible; the second is strict because its candidate slack would be negative.
Quick check
(Prove that any optimal dual supports wherever the perturbed primal value is finite. Does this prove differentiability?)
Solution · Answer
The dual feasible set is independent of the right-hand side. Weak duality gives , and optimality gives . Subtract to obtain the supporting inequality. It does not prove differentiability: at the corner the interval of supporting slopes in the worked example yields different one-sided derivatives.