Feasible Sets

What you will be able to do

Given a set of restrictions, the learner can determine whether the feasible set is empty, non-empty and bounded, or non-empty and unbounded, and can state that the classification does not depend on the objective function.

Orientation

The set of permitted choices exists before any objective does. Whether it is empty, bounded, or runs on forever is a question about the restrictions alone.

This is the abstraction that later units specialise. The feasible region of a linear program is one feasible set among many, and the reasoning that applies to it applies here first.

Intuition

The set of choices the restrictions allow

Each restriction rules some choices out. What remains after applying every restriction at once is the feasible set.

Two questions matter before any optimization begins. Is anything left? Restrictions can contradict each other, leaving nothing. Does what remains run on forever? A set can permit arbitrarily large choices, which changes what an optimum can mean.

Neither question mentions the objective. Whether a choice is allowed has nothing to do with whether it is good.

Figure

Four feasible sets before any linearity is assumed

nonlinear does not imply nonconvex

nonlinear does not imply nonconvex

Four separate coordinate frames side by side, each with its own marked origin and axis stubs labelled $x$ and $y$ ; the offsets between frames are page layout and carry no coordinate meaning. The first frame shows a filled circular disk, the set $x^{2} + y^{2} \leq r^{2}$ about its centre: defined by a nonlinear restriction, bounded, and convex, since the segment joining any two of its points stays inside. The second shows the region above a parabola, $y \geq x^{2}$ , with the curve drawn and the region shaded: nonlinear, unbounded upward, and still convex. The third shows a shaded triangle bounded by straight edges, a polyhedron defined by linear inequalities: the special case the later units restrict to. The fourth shows the region under one branch of the hyperbola $x y = 1$ in the first quadrant, the set $x y \leq 1$ with $x, y \geq 0$ : nonlinear and not convex, because $(4, 0)$ and $(0, 4)$ both satisfy the restriction while their midpoint $(2, 2)$ gives $x y = 4 > 1$ and does not. Comparing the second and fourth frames is the point: both are nonlinear, one is convex and one is not, so nonlinearity does not imply nonconvexity, and linearity and convexity are additional properties rather than part of the definition of a feasible set.

Four sets of restrictions, each drawn in its own frame with its own origin. All four are feasible sets: what remains after applying every restriction at once. Nothing about that definition mentions straight lines.

A disk, $x^{2} + y^{2} \leq r^{2}$ about its centre. Nonlinear, bounded, and convex: the segment between any two of its points stays inside.

$y \geq x^{2}$ . Nonlinear, unbounded — it continues upward forever — and still convex.

A polyhedron, from linear inequalities. This is the special case the rest of the course narrows to, and the flat edges follow from linearity.

$x y \leq 1$ with $x, y \geq 0$ . Nonlinear and not convex: $(4, 0)$ and $(0, 4)$ both satisfy it, but their midpoint $(2, 2)$ gives $x y = 4 > 1$ and does not.

Put the second and fourth side by side and the useful distinction appears: both are nonlinear, one is convex and one is not. Nonlinear does not mean nonconvex. Linearity and convexity are additional properties a feasible set may or may not have, and neither is part of what makes it feasible.

Emptiness is not drawn here, because an empty set has nothing to show. It is detected by contradiction among the restrictions, not by looking.

Definition

The feasible set

Given restrictions $g_{1}, \dots, g_{m}$ on a choice $x \in R^{n}$ , the feasible set is

F = {x \in R^{n} : x satisfies every g_{i}} .

A point of $F$ is a feasible point. $F$ is empty when no choice satisfies all the restrictions at once, and the problem is then infeasible. $F$ is bounded when it fits inside some ball of finite radius, and unbounded otherwise.

Nothing here requires the restrictions to be linear. When they are, each $g_{i}$ an inequality $a_{i}^{T} x \leq b_{i}$ , the feasible set is the feasible region of a linear program, and it inherits the flat faces and convexity that linearity brings. Those are properties of the special case, not of feasible sets in general.

Example

Four sets of restrictions

Non-empty and bounded. $x^{2} + y^{2} \leq 1$ . Every feasible point lies within distance 1 of the origin, so the set fits in a ball and is bounded.

Non-empty and unbounded. $y \geq x^{2}$ . The point $(t, t^{2})$ is feasible for every real $t$ , so the set contains points arbitrarily far from the origin.

Empty. $x \geq 1$ together with $x \leq 0$ . No number is at once at least 1 and at most 0, so nothing survives and the problem is infeasible.

Non-empty, unbounded, yet the objective is limited. $x \geq 0$ , minimizing $x$ . The set runs on without limit, but the smallest permitted value is 0. An unbounded feasible set does not by itself mean an unbounded answer. The two questions are separate.

Contrast

A restriction that is not linear

Linear. $x + y \leq 4$ , $x \geq 0$ , $y \geq 0$ . The set is a triangle: flat edges, and the segment between any two feasible points stays feasible.

Not linear. $x y \geq 1$ , $x > 0$ . The set is the region above one branch of a hyperbola. The points $(1, 1)$ and $(4, 0.25)$ are both feasible, yet their midpoint $(2.5, 0.625)$ has $x y = 1.5625 \geq 1$ , feasible here. But take $(0.5, 2)$ and $(2, 0.5)$ : both feasible, midpoint $(1.25, 1.25)$ with $x y = 1.5625$ , still feasible. Now $(0.1, 10)$ and $(10, 0.1)$ : midpoint $(5.05, 5.05)$ , feasible again.

The hyperbola region happens to be convex. Change the restriction to $x y \leq 1$ with $x, y \geq 0$ and it is not: $(4, 0)$ and $(0, 4)$ are feasible, their midpoint $(2, 2)$ has $x y = 4 > 1$ and is not.

The lesson is that convexity is something to check, not something a feasible set has by nature. Linear restrictions guarantee it; general restrictions do not.

Next step

Practice Feasible Sets

Practice this

Feasible Sets

The set of choices the restrictions allow

Four feasible sets before any linearity is assumed

The feasible set

Four sets of restrictions

A restriction that is not linear

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history