3.2. Linear Programming

Linear Program

A Linear Program (LP) is a convex optimization problem where the objective function and constraints are all affine. Its matrix form is given as
$\begin{array}{rl}\underset{x\in {\mathbb{R}}^n}{\min }& a_0^{\top }x\\ \text{s.t.}& Ax=b,\\ & Cx\le d.\end{array}$
where $A,C\in {\mathbb{R}}^{m\times n}$, and $b,d\in {\mathbb{R}}^m$ for some $x\in {\mathbb{R}}^n$

Each equality constraint $a_i^{\top }x=b_i$ defines a hyperplane, while each inequality constraint $c_j^{\top }x\le d_j$ defines a half-space. The feasible set of an LP is therefore the intersection of finitely many hyperplanes and half-spaces:
${\mathcal{S}}_{\text{LP}}=\left(\underset{\text{hyperplane}}{\underbrace{\bigcap _{i=1}^m\{x\in {\mathbb{R}}^n\mid a_i^{\top }x=b_i\}}}\right)\cap \left(\underset{\text{half-space}}{\underbrace{\bigcap _{j=1}^k\{x\in {\mathbb{R}}^n\mid c_j^{\top }x\le d_j\}}}\right).$
This set is called a polyhedron. If it is bounded, it is called a polytope. In two dimensions, a polyhedron is simply a (possibly unbounded) convex polygon.

A key structural property of LPs is that if an LP has an optimal solution, then at least one optimal solution occurs at a vertex (extreme point) of the feasible set. Vertices correspond to points where enough constraints are active (tight) to uniquely determine a solution. In ${\mathbb{R}}^n$, this typically means selecting $n$ linearly independent active constraints and solving the resulting linear system. Algebraically, this is known as a basic feasible solution.

Two vertices of a non-degenerate LP are adjacent if they differ in exactly one active constraint. Equivalently, they share all but one of their zero components in the standard form representation. This adjacency structure forms the edges of the polyhedron.

The simplex algorithm exploits this geometry to solve LPs as follows:

1. Start at any feasible vertex $y$.
2. Check all adjacent vertices to $y$.
3. If an adjacent vertex $\hat{y}$ exists, such that $a_0^T\hat{y}<a_0^{T}y$, update the parameter $y$ to be $\hat{y}$ and repeat the process starting from 2.
4. Otherwise, if no adjacent vertices exist or meet the condition, $y$ is the optimal solution to the LP.

To convert a general optimization problem to an LP, one can employ slack variables through the epigraph technique. The problem
${\min }_{x\in {\mathbb{R}}^n}f(x)\text{s.t. }x\in S$
can be rewritten using the epigraph technique as
$\begin{array}{rl}\underset{x\in {\mathbb{R}}^n,t\in \mathbb{R}}{\min }& t\\ \text{s.t.}& x\in \mathcal{S},\\ & f(x)\le t.\end{array}$
For LPs, since $f(x)$ is affine, the constraint $f(x)\le t$ is also affine, preserving linearity. Minimizing $t$ geometrically pushes the upper bound down until it touches the graph of $f$.

Intuition

Intuitively, in linear programming:

• You have a collection of variables $x_1,x_2,\dots ,x_n$.
• You form a linear expression $c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$ (the “objective”) that you want to make as large (maximize) or as small (minimize) as possible.

At the same time, each variable combination must satisfy a series of linear constraints, such as:

• $a_{1,1}{x}_1+a_{1,2}{x}_2+\cdots +a_{1,n}{x}_n\le b_1,$
• $a_{2,1}{x}_1+a_{2,2}{x}_2+\cdots +a_{2,n}{x}_n\le b_2,$
  and possibly some equalities, like
• $a_{3,1}{x}_1+a_{3,2}{x}_2+\cdots +a_{3,n}{x}_n=b_3.$

Each constraint chops off a portion of the space of all possible $x$. Because the constraints are linear, the feasible region (the set of all allowable solutions) is a convex polytope (think of a polygon in 2D, a polyhedron in 3D, etc.).

Properties

Examples

Finding Vertices of an LP

Formulating LPs I

Formulate the problem
${\min }_{x\in {\mathbb{R}}^n}f(x)$
for the following functions using the epigraph technique or explain why you cannot.

$f_1(x)=\max x-\min x$ We can initialize two slack variables, $t_1$ and $t_2$ that bound the two functions, such that

& x_{i} \le t_{1} \\ & x_{i} \ge t_{2} \qquad \text{for } i = 1, \ldots, n, & t_1 \ge 0, & t_2 \ge 0. \end{aligned}$$ Then, the objective becomes $t_{1}-t_{2}$. Note that the non-negativity of slack variables is not implied by the maximum and minimum here, and the two additional constraints should be explicitly added.

$f_2(x)={\sum }_{i=1}^n|x_i|$ We initialize a vector $t\in {\mathbb{R}}^n$, such that $-t_i\le x_i\le t_i\text{for }i=1,\dots ,n,$ and $t\ge 0$ (which is implied by the constraint). The objective is simply $1^{T}t$.

$f_3(x)=\Vert Ax-y{\Vert }_{\infty }+\Vert x{\Vert }_1$ Since $\Vert Ax-y{\Vert }_{\infty }=\max (|Ax-y|)$ is a single variable we only need the slack variable $t\in \mathbb{R}$. We add the constraint $-t\le (Ax-y{)}_i\le t\text{for }i=1,\dots ,m.$ However, because the L1 norm uses all vector elements, we must define a slack variable $u_i$ for each $x_i$. As such, we add the constraint $-u_i\le x_i\le u_i\text{for }i=1,\dots ,n.$ Then, the objective function becomes $t+1^{T}u$ and we minimize over $x,t,u$. Non-negativity of slack variables is implied by the rest of the constraints.

Formulating LPs II

Given constants ${\alpha }_1,\dots ,{\alpha }_n$, consider the optimization problem
$\begin{array}{rl}\underset{x\in {\mathbb{R}}^n}{\min }& \exp \left(\sum _{i=1}^n{\alpha }_i{x}_i\right)\\ \text{s.t.}& {\left(\Vert x{\Vert }_{\infty }+10\Vert x{\Vert }_1\right)}^2\le 5.\end{array}$

Formulate this problem as an LP. $e^x$ is non-decreasing in $x$, we can reduce the objective function to simply ${\sum }_{i=1}^n{\alpha }_i{x}_i$. As done before, for the constraint we introduce two slack variables: $t\in \mathbb{R}$ and $u\in {\mathbb{R}}^n$. For $\Vert x{\Vert }_{\infty }=t$, we add the constraint $-t\le x_i\le t\text{for }i=1,\dots ,n,$ whereas for $\Vert x{\Vert }_1$, we introduce the constraint $-u_i\le x_i\le u_i\text{for }i=1,\dots ,n.$ Our original constraint becomes $t+10\cdot 1^{T}u\le \sqrt{5}.$

Since