Some Definitions & Graphing#
Some definitions#
The goal of an LP is to find the decision that optimizes some objective subject to certain constraints.
[LINEAR MAP]
A function \(f:\mathbb{R}^n\rightarrow\mathbb{R}\) is linear if \(f(a\mathbf{x}+\mathbf{y})=af(\mathbf{x})+f(\mathbf{y})\,\,\,\forall{\mathbf{x},\mathbf{y}}\in\mathbb{R}^n,\forall{a}\in\mathbb{R}\).
Note that if \(f:\mathbb{R}^n\rightarrow\mathbb{R}\) is linear, then \(f(\mathbf{0})=0\).
[W] Linear Function/Map/Transformation
[AFFINE MAP]
A function \(f:\mathbb{R}^n\rightarrow\mathbb{R}\) is affine if \(f(\mathbf{x})=g(\mathbf{x})+c\,\,\,\forall{\mathbf{x}}\in\mathbb{R}^n\) where \(g\) is linear and \(c\in\mathbb{R}\).
In other words, an affine function is just a linear function plus a constant.
[W] Affine Function/Map/Transformation
[LINEAR CONSTRAINT]
A linear constraint uses a linear function \(f:\mathbb{R}^n\rightarrow\mathbb{R}\) and a constant \(b\in\mathbb{R}\) to limit the values of a variable \(\mathbf{x}\in\mathbb{R}^n\) by requiring either \(f(\mathbf{x})\le b\), \(f(\mathbf{x})\ge b\), or \(f(\mathbf{x})=b\).
Only weak inequalities \(\le,\ge\) are allowed which means that the solution set is closed.
Note that any affine constraint can be rewritten as a linear constraint.
[LINEAR PROGRAM (LP) & OBJECTIVE FUNCTION]
An LP is a problem of optimizing an affine function called the objective function subject to finitely many linear constraints.
Note that any affine objective function \(f(\mathbf{x})+c\) attains its optimum where \(f(\mathbf{x})\) attains its optimum. The constant \(c\) only changes the optimal value of \(f\), not the values of \(\mathbf{x}\) at which \(f\) attains its optimum.
[FEASIBLE SET]
The feasible set \(\Gamma\) of an LP is the set of all \(\mathbf{x}\in\mathbb{R}^n\) that satisfy all the constraints of the LP.
Another way to look at it is that the feasible set \(\Gamma\) of an LP is just the intersection of the feasible sets of the individual constraints of the LP.
[W] Feasible Region/Set
[OPTIMAL/SOLUTION SET]
Let \(\Gamma\) be the feasible set of an LP.
If the LP is to maximize \(f\), then the optimal set of the LP is
\(\argmax_{\Gamma}(f)=\{\mathbf{x}\in\Gamma\mid f(\mathbf{x})\ge f(\mathbf{y})\,\,\,\forall{\mathbf{y}}\in\Gamma\}\)
the set of points at which \(f\) attains its maximum over the set \(\Gamma\).
If the LP is to minimize \(f\), then the optimal set of the LP is
\(\argmin_{\Gamma}(f)=\{\mathbf{x}\in\Gamma\mid f(\mathbf{x})\le f(\mathbf{y})\,\,\,\forall{\mathbf{y}}\in\Gamma\}\)
the set of points at which \(f\) attains its minimum over the set \(\Gamma\).
[OPTIMAL VALUE]
Let \(\Gamma\) be the feasible set of an LP.
If the LP is the maximize \(f\), then the optimal value is
\(\max_{\Gamma}(f)\)
If the LP is the minimize \(f\), then the optimal value is
\(\min_{\Gamma}(f)\)
[LP SOLUTION]
The solution to an LP consists of both the optimal set and the optimal value.
either
\(\argmax_{\Gamma}(f)\) and \(\max_{\Gamma}(f)\)
or
\(\argmin_{\Gamma}(f)\) and \(\min_{\Gamma}(f)\)
In other words, solving an LP means finding both the optimal set and the optimal value.
[INFEASIBLE LP]
If there are no \(\mathbf{x}\in\mathbb{R}^n\) which satisfy all the constraints of the LP, then the LP is called infeasible.
The LP has no solution.
[FEASIBLE LP]
If there is at least one \(\mathbf{x}\in\mathbb{R}^n\) which satisfies all the constraints of the LP, then the LP is called feasible.
The LP may or may not have a solution depending on its boundedness.
[UNBOUNDED LP]
If the constraints allow the objective function to increase without bound (i.e., to positive infinity), then the LP to maximize the objective function subject to the constraints is unbounded.
If the constraints allow the objective function to decrease without bound (i.e., to negative infinity), then the LP to minimize the objective function subject to the constraints is unbounded.
The LP has no solution.
[BOUNDED LP]
The objective function is bounded on the feasible set.
The LP has a solution.
THEOREM
Every LP is either infeasible, feasible but unbounded, or has a solution.
PROOF
The feasible set \(\Gamma\) of an LP is closed by the requirement on linear constraints.
If the LP has a bounded feasible set, then it has a compact (bounded + closed) feasible set.
A continuous function on a compact set attains its maximum.
Add the following constraints to the LP to get a new LP.
constraints that are parallel to the gradient of the objective function and therefore do not constrain the optimum
a constaint that is normal to the gradient, which places a lower bound on the objective
A compact feasible set must have a maximum.
The argmax of the LP with additional constraints is a subset of the argmax of the original LP.
[GRADIENT]
Let \(f:\mathbb{R}^n\rightarrow\mathbb{R}\) be a function.
The gradient of \(f\) is
\( \begin{aligned} \nabla{f}=\left\langle\frac{\partial f}{\partial x_1},...,\frac{\partial f}{\partial x_n}\right\rangle \end{aligned} \)
Note that if \(f\) is affine (or linear), then \(\nabla{f}\) is constant.
The significance of the vector \(\nabla{f}\) is that it points in the direction of the maximum rate of increase of \(f\) per unit Euclidean distance change in the variable \(\mathbf{x}\) as it varies through \(\mathbb{R}^n\).
[W] Gradient
[DIRECTIONAL DERIVATIVE]
Let \(\mathbf{u}\in\mathbb{R}^n\) be a nonzero vector and \(f:\mathbb{R}^n\rightarrow\mathbb{R}\) be a function.
The directional derivative of \(f\) in the direction of \(\mathbf{u}\) is
\( \begin{aligned} \frac{\nabla f\cdot\mathbf{u}}{\|\mathbf{u}\|} \end{aligned} \)
Note that the sign of the directional derivative does not depend on the magnitude of \(\mathbf{u}\), so \(\nabla f\cdot\mathbf{u}\) can be used in place of the true directional derivative when only the sign is needed.
The sign (of the directional derivative of \(f\) in the direction of \(\mathbf{u}\)) is enough to tell whether \(f\) increases, decreases, or remains constant when the variable \(\mathbf{x}\) is changed in the direction of \(\mathbf{u}\).
\(\nabla f\cdot\mathbf{u}\ge0\implies f\) increases
\(\nabla f\cdot\mathbf{u}\le0\implies f\) decreases
\(\nabla f\cdot\mathbf{u}=0\implies f\) remains constant
Note also that because the gradient of an affine (or linear) function is constant, the directional derivative in any direction is constant.
[W] Directional Derivative
[LEVEL SET]
Let \(f:\mathbb{R}^n\rightarrow\mathbb{R}\) be a function.
A level set \(S\) of \(f\) is a subset of \(\mathbb{R}^n\) on which \(f\) has constant value \(f(\mathbf{x})=b\) for some constant \(b\in\mathbb{R}\).
\(f(\mathbf{x})=b\) may be used as an abbreviation to refer to the level set
\(S=\{\mathbf{x}\in\mathbb{R}^n\mid f(\mathbf{x})=b\}\subseteq\mathbb{R}^n\)
[W] Level Set
Let \(S\subseteq\mathbb{R}^n\) be a level set of \(f\).
\(\mathbf{u}=\mathbf{x-y}\) where \(\mathbf{x,y}\in S\implies\nabla f\cdot\mathbf{u}=0\)
That is, a function has zero directional derivative on any level set.
[HYPERPLANE]
The boundary of a linear inequality constraint
\(f(\mathbf{x})\le b\)
\(f(\mathbf{x})\ge b\)
in \(\mathbb{R}^n\) is a hyperplane of dimension \(n - 1\).
The solution of a linear equality constraint
\(f(\mathbf{x})=b\)
in \(\mathbb{R}^n\) is a hyperplane of dimension \(n - 1\).
In \(\mathbb{R}\), a hyperplane of dimension \(1-1=0\) is a point.
In \(\mathbb{R}^2\), a hyperplane of dimension \(2-1=1\) is a line.
In \(\mathbb{R}^3\), a hyperplane of dimension \(3-1=2\) is a plane.
In \(\mathbb{R}^4\), a hyperplane of dimension \(4-1=3\) is a hyperplane.
Graphing in \(\mathbb{R}^2\)#
The boundary of a linear constraint
\(f(\mathbf{x})\le b\)
\(f(\mathbf{x})\ge b\)
\(f(\mathbf{x})=b\)
is the line \(f(\mathbf{x})=b\), a line perpendicular to \(\nabla f\).
Since \(f(\mathbf{0})=0\) for linear \(f\), \(\nabla f\) can be traced from the origin out to the level set \(f(\mathbf{x})=b\).
[EXAMPLE]
the boundary of the constraint
\( f=2x_1+3x_2\le6 \)
is the line
\( 2x_1+3x_2=6 \)
perpendicular to
\( \nabla f=\langle2,3\rangle \)
which passes through the first quadrant with negative slope
\( \begin{aligned} x_2=-\frac{2}{3}x_1+2\impliedby2x_1+3x_2=6 \end{aligned} \)
[EXAMPLE]
the boundary of the constraint
\( f=2x_1-3x_2\le6 \)
is the line
\( 2x_1-3x_2=6 \)
perpendicular to
\( \nabla f=\langle2,-3\rangle \)
which passes through the fourth quadrant with positive slope
\( \begin{aligned} x_2=\frac{2}{3}x_1-2\impliedby2x_1-3x_2=6 \end{aligned} \)
[EXAMPLE]
the boundary of the constraint
\( f=-2x_1-3x_2\le6 \)
is the line
\( -2x_1-3x_2=6 \)
perpendicular to
\( \nabla f=\langle-2,-3\rangle \)
which passes through the third quadrant with negative slope
\( \begin{aligned} x_2=-\frac{2}{3}x_1-2\impliedby-2x_1-3x_2=6 \end{aligned} \)
[EXAMPLE]
the boundary of the constraint
\( f=-2x_1+3x_2\le6 \)
is the line
\( -2x_1+3x_2=6 \)
perpendicular to
\( \nabla f=\langle-2,3\rangle \)
which passes through the second quadrant with positive slope
\( \begin{aligned} x_2=\frac{2}{3}x_1-2\impliedby-2x_1+3x_2=6 \end{aligned} \)
Mark the feasible region#
Which side of an inequality constraint is feasible? (In other words, which side of an inequality constraint satisfies the constraint?)
\( f(\mathbf{x})\ge b\implies\text{the side}\,\nabla f\,\text{points to} \)
\( f(\mathbf{x})\le b\implies\text{the side}\,-\nabla f\,\text{points to}\\\text{(that is, the side opposite the side}\,\nabla f\,\text{points to)} \)
The feasible set of a linear equality constraint is just the line itself.
\( f(\mathbf{x})=b\implies\text{the line}\,f(\mathbf{x})=b\,\text{itself} \)
To graph the feasible set \(\Gamma\) of an LP, graph each boundary line and mark its feasible side.
If both sides of an equality constraint are marked as feasible, then only the line itself is in their intersection.
If there is a non empty intersection, mark it as the feasible set.
Mark the direction of optimization#
Draw vectors parallel to each constraint boundary#
Since the boundary of a constaint
\( c_1x_1+c_2x_2=b \)
is just a level set of the constraint function
\( f=c_1x_1+c_2x_2\ge b \)
a vector \(\mathbf{v}=\langle v_1,v_2\rangle\) which is parallel to the boundary is perpendicular to the constraint’s gradient \(\nabla f=\langle c_1,c_2\rangle\)
\( \nabla f\cdot\mathbf{v}=\langle c_1,c_2\rangle\cdot\langle v_1,v_2\rangle=0 \implies \mathbf{v} \) is parallel to the boundary
Convenient choices for \(\mathbf{v}\)
\( \mathbf{v}=\langle c_2,-c_1\rangle \implies \langle c_1,c_2\rangle\cdot\langle c_2,-c_1\rangle=c_1c_2-c_1c_2=0 \)
\( \mathbf{v}=\langle-c_2,c_1\rangle \implies \langle c_1,c_2\rangle\cdot\langle-c_2,c_1\rangle=c_1c_2-c_1c_2=0 \)
Construct vectors \(\mathbf{v}_i\) parallel to each constraint boundary to determine in which direction along the boundary the objective \(z(\mathbf{x})\) increases and in which direction it decreases, or whether it stays constant in both directions.
Determine the sign of the directional derivative on each constaint boundary.
\(\nabla z\cdot\mathbf{v}\gt0\implies z\) increases in the direction of \(\mathbf{v}\)
\(\nabla z\cdot\mathbf{v}\lt0\implies z\) increases in the direction of \(-\mathbf{v}\) (i.e., \(z\) decreases in the direction of \(\mathbf{v}\))
\(\nabla z\cdot\mathbf{v}=0\implies z\) remains constant in both directions
When the boundaries are marked, follow the arrows to maximize the objective \(z(\mathbf{x})\) and go against the arrows to minimize it.
A level set boundary must be either \(\argmax_{\Gamma} z\) or \(\argmin_{\Gamma} z\).