Why existence needs a separate argument
A first-order optimality condition can certify a minimum in a convex problem—for example, zero gradient for an unconstrained differentiable convex function—but it does not produce such a point. Even a continuous convex function can have an infimum that is never reached. The missing issue is escape: can a sequence of increasingly good feasible points travel arbitrarily far away? A recession direction describes a straight route along which a whole convex feasible set can be translated without leaving it. This is particularly useful when the set is unbounded and compactness cannot be assumed at the outset.
All spaces below are finite-dimensional Euclidean spaces. A set is bounded if it lies in a ball of finite radius. A minimizer is a feasible point attaining the infimum; a finite infimum alone does not imply one exists. The conclusions concerning recession directions require the stated closedness and convexity; they are not merely consequences of a picture of an unbounded set.
From one ray to translation of the whole set
For a nonempty closed convex set , define its recession cone by
It always contains zero. It is a closed convex cone: the defining conditions are closed in ; nonnegative scaling only changes the parameter ; and for in the cone, convexity puts in , so replacing by gives in the cone. More generally nonnegative linear combinations belong to it.
Theorem 5.3.1
(One ray determines a recession direction)
Let be nonempty, closed and convex. If for one and every we have , then . Moreover, is bounded if and only if .
Proof
(Shrinking convex combinations and a limit)
Fix and . For every integer large enough that , convexity gives
The points converge to , which belongs to because is closed. This proves the first claim. If is bounded, a nonzero recession direction would generate an unbounded ray, so its recession cone contains only zero.
Conversely, suppose is unbounded and choose and with . By compactness of the unit sphere, a subsequence of converges to a unit vector . For fixed , eventually , so the convex combination lies in . Closedness yields . This holds for every fixed , and the first claim makes the nonzero vector a recession direction.
Proof X-ray
Why closedness transfers a ray to every base point
Closedness is used twice, each time at the very end. In the first claim the convex combinations lie in for every large , and only closedness lets the error term be removed. The non-obvious move is to push the far point outward while shrinking its weight , so that the step from is always up to that error. Convexity is what makes each intermediate point feasible. In the converse, compactness of the unit sphere manufactures a candidate direction from an unbounded sequence, closedness again passes to the limit, and the first claim upgrades a ray from to a recession direction.
The limit step cannot be skipped, as the following set shows.
Counterexample mode
Closedness cannot be omitted from the one-ray theorem
Let be the convex hull in of the ray and the point . Thus contains , but its only point with second coordinate is . Define
The set is convex: segments in its boundary part remain in , while a segment with a positive- endpoint has positive except possibly at its other endpoint. It is not closed. From , the whole ray in direction lies in , but does not. Hence is not in . The limit step in the proof really uses closedness.
Linear constraints and a quantitative existence certificate
For , assume is nonempty. Then
Indeed makes for all feasible and . Conversely, if a component of were positive, the corresponding inequality would eventually fail along for any feasible starting point . An equality contributes in the same way. Thus the cone depends on the constraint normals, not the right-hand sides, once feasibility is known.
Theorem 5.3.2
(A sufficient condition for linear-objective attainment)
Let be nonempty, closed and convex and let . If for every nonzero , then attains its minimum on , and its set of minimizers is nonempty and compact.
Proof
(A compact sublevel set)
Choose any and put . This nonempty set is closed and convex. If it were unbounded, the preceding theorem would give a nonzero . Because , the ray lies in , hence ; the upper bound defining also forces , a contradiction. Thus is compact. Continuity of gives a minimum on , and points outside have larger objective than , so it is also a minimum on . The minimizer set is a closed subset of , hence compact.
The strict inequality is sufficient, not necessary for attainment. If some recession direction has , the objective tends to on every feasible ray in that direction. If a nonzero recession direction has , moving in that direction changes no objective value; this prevents compactness of the minimizer set if a minimizer exists, but it does not by itself prevent attainment. The remaining case, a finite infimum with no minimum, can occur on a closed convex feasible set for a linear objective, as the next example shows.
Worked example 5.3.3
(Three objectives on the same unbounded set)
Let . Its recession cone is itself. For , every nonzero has , so the theorem gives a compact minimizer set; direct inspection gives the unique minimizer . For , the direction has zero cost. The minimum is still attained, at every with , and the minimizer set is unbounded. For , the direction has negative cost, so the infimum is . A positive slope on every nonzero recession direction guarantees a compact minimizer set; a negative slope forces an infimum of ; a zero slope on a nonzero recession direction rules out compactness if a minimizer exists. Attainment for was checked directly.
Worked example 5.3.4
(A polyhedral feasible set)
Let and minimize . Writing the constraints as , the recession cone is given by , and ; the last is redundant, so is the nonnegative quadrant. The cost is positive for each nonzero cone element, so the theorem proves attainment. To find the minimizers, fix : the smallest feasible is . On the objective is at least ; for it is at least . Equality occurs only at , so this is the unique minimizer, with value . The right-hand sides played no role in the recession cone, only in locating the minimizer.
Counterexample mode
Closed feasible set, finite infimum, no minimizer
Let and minimize the linear objective . The epigraph is closed and convex because is continuous and convex. Every feasible point has , but is feasible and its objective tends to zero. The infimum is zero and is not attained. Here is a recession direction with zero objective slope. This example rules out the inference “closed and convex plus finite infimum implies attainment.” It also shows why a zero-cost recession direction does not decide attainment either way.
Nonlinear objectives and level sets
The same compactness reasoning applies without linearity.
Proposition 5.3.5
(A bounded sublevel set gives a minimizer)
Let be nonempty and closed, and let be continuous. If some nonempty sublevel set is bounded, then attains its minimum on , and the set of minimizers is compact.
Proof
(Restrict to the sublevel set)
The set is closed, as the preimage of under a continuous function on a closed set, and it is bounded, so it is compact. A continuous function on a nonempty compact set attains its minimum, say at . A point outside has value greater than , so minimizes on all of . The minimizer set is a closed subset of , hence compact. Convexity is not needed for this existence argument.
One useful sufficient hypothesis is coercivity on : for every sequence with . It makes every sublevel set bounded. Coercivity is sufficient, not necessary: the constant zero function on attains its minimum everywhere but is not coercive. A different sufficient condition for uniqueness is strict convexity: if is convex and is strictly convex on , two distinct minimizers would have a midpoint with strictly smaller value. Strict convexity alone does not establish existence: is strictly convex on , but approaches zero without attaining it.
Common mistake
(Coercivity is tested on , not on )
Take and . On the function is not coercive, because while ; but those points are infeasible once . For a feasible sequence with we have , so and . Thus is coercive on , and its minimizer set is compact. Testing coercivity on the whole space would discard a valid existence argument.
Worked example 5.3.6
(Existence without uniqueness)
Let on . It is continuous and coercive, since as . Its sublevel set is nonempty and compact, so the proposition guarantees a minimizer. From the candidates are and , with and . Hence the minimum value is , attained at both and . Existence needed no convexity; uniqueness fails because is not convex: exceeds the average of and .
Concept lensGeometric
Existence and uniqueness answer different questions
A nonempty compact sublevel set contains a minimizer and supplies a bounded minimizing sequence. Strict convexity prevents two distinct points from sharing the lowest value. Neither statement supplies the other: on has both properties, the constant function has attainment without uniqueness, and has strict convexity without attainment.
Exercises with solutions
Quick check
(Minimize over . Find the minimizers and decide whether the minimizer set is compact. Is the objective coercive on ?)
Look along the direction .
Solution · Answer
Since , the smallest value is , attained at every with . This set is closed but unbounded, hence not compact. Along the norm tends to infinity while the objective stays , so the objective is not coercive on . Nevertheless it attains its minimum. The linear-objective theorem is not being applied to .
Quick check
(Minimize over . Determine the infimum and whether it is attained. Which hypothesis of the sublevel-set proposition fails?)
Follow the sequence .
Solution · Answer
The infimum is zero, as for approaches zero, but every feasible has . Although the feasible set and its sublevel subsets are bounded, every nonempty sublevel set here is an interval or , which is not closed in , hence not compact. In particular, the sequence has no feasible limit. The proposition does not apply because is not closed.
Quick check
(Let . Show that is a recession direction. For each of , , and , determine the infimum and whether it is attained.)
For , do not restrict attention to straight rays.
Solution · Answer
Adding increases while leaving fixed, so it preserves feasibility for all . For , , with equality only at ; the minimum is zero. For , the feasible ray sends the objective to . For , the feasible points send the objective to . The vertical direction has zero slope for , showing that a zero-slope direction does not rule out escape along a curved sequence or establish a finite infimum. In fact the recession cone here is only the upward vertical ray: a nonzero horizontal component would make grow quadratically in while grows only linearly. If and , then eventually falls below the fixed value .