Closed form solution to an LP

Question

Consider only inequality constrained LP defined as \begin{align*} \sup_{x} \;&c^\top x\\ \mathrm{s.t.}\;& Ax\leq b \end{align*}

I would like to know is there a closed-form solution for this LP?

Answer 1

Let us introduce slack variables and rewrite the problem into: \begin{align*} \sup_{x} \;&c^\top x\\ \mathrm{s.t.}\;& Ax = b \\ & x \ge 0 \end{align*} where this $x$ contains the old $x$ and the slack variables. Suppose you know the active $\mathcal{A} := \{ i ~|~ x_i = 0 \}$ and inactive $\mathcal{I} := \{ i ~|~ x_i > 0 \}$ sets. Then $A_{:, \mathcal{I}}$, the submatrix of all rows of $A$ and the columns of $\mathcal{I}$, is invertible, and the primal-dual solution of the problem is: \begin{equation} \begin{aligned} x_\mathcal{I}^* & = A_{:, \mathcal{I}}^{-1} b \\ x_\mathcal{A}^* & = 0 \\ \lambda^* & = A_{:, \mathcal{I}}^{-T} c_\mathcal{I} \\ z_\mathcal{A}^* & = c_\mathcal{A} + A_{:, \mathcal{A}}^T \lambda^* \\ z_\mathcal{I}^* & = 0 \end{aligned} \end{equation} where $\lambda$ are the Lagrange multipliers of $Ax = b$ and $z$ are the Lagrange multipliers of $x \ge 0$.

The simplex method attemps to find the correct active set, using basically trial and error. It updates the active set by iteratively removing one active constraint and activating one inactive constraint until dual feasibility ($z \ge 0$) is attained.