Exercise 4.3 (Solving linear programming problems is no harder than solving systems of linear inequalities)

Question

The purpose of this exercise is to show that solving linear programming problems is no harder than solving systems of linear inequalities.
ewline 
Suppose that we are given a subroutine which, given a system of linear inequality constraints, either produces a solution or decides that no solution exists. Construct a simple algorithm that uses a single call to this subroutine and which finds an optimal solution to any linear programming problem that has an optimal solution.

Elu Thingol · Accepted Answer

Consider the following algorithm:
\begin{itemize}
\item Step 1. Calculate the parameters $\mathbf{c}$, $\mathbf{A}$ and $\mathbf{b}$ which bring the given optimization problem into the usual primal and dual forms:
  \begin{equation}
    \begin{array}{ll}
      	ext{minimize}\quad   &\mathbf{c}^{\prime}\mathbf{x}\
      	ext{subject to}\quad &\mathbf{A}\mathbf{x} \geq \mathbf{b}\
                             &\mathbf{x} \geq \mathbf{0},
    \end{array}
    \quad\quad\quad
    \begin{array}{ll}
      	ext{maximize}\quad   &\mathbf{p}^{\prime}\mathbf{b}\
      	ext{subject to}\quad &\mathbf{p}^{\prime}\mathbf{A} \leq \mathbf{c}^{\prime}\
                             &\mathbf{p} \geq \mathbf{0}.
                               
    \end{array}
    \label{linopt}
  \end{equation}

\item Step 2. Solve the following system of linear inequalities for $(\mathbf{x},\mathbf{p})$:
  \begin{equation}
    \left\{
      \begin{array}{ll}
        \mathbf{A}\mathbf{x} \geq \mathbf{b}\
        \mathbf{x} \geq 0\
        \mathbf{p}^{\prime}\mathbf{A} \leq \mathbf{c}^{\prime}\
        \mathbf{p} \geq 0\
        \mathbf{c}^{\prime}\mathbf{x} = \mathbf{p}^{\prime}\mathbf{b}
      \end{array}ight.
    \label{linsys}
  \end{equation}
\end{itemize}

The above subroutine will always give us an optimal solution to the linear programming problem that has an optimal solution.
\begin{proof}
  \begin{description}
  \item[$\implies$] Suppose that the primal problem \eqref{linopt} has an optimal solution $\mathbf{x}^*$. By the strong duality (Theorem 4.4), its dual must also have an optimal solution $\mathbf{p}^*$, and the respective optimal costs are equal, i.e., $\mathbf{c}^{\prime}\mathbf{x} = \mathbf{p}^{\prime}\mathbf{b}$. Thus, the pair $(\mathbf{x}^*,\mathbf{p}^*)$ constitutes for a solution of the system of linear inequalities in \eqref{linsys}.
  \item[$\impliedby$] Let $(\mathbf{x}^*,\mathbf{p}^*)$ be the solution of \eqref{linsys}. In other words, $\mathbf{x}^*$ is some feasible solution to the primal problem, $\mathbf{p}^*$ is some feasible solution of the dual problem, and their objective values coincide $\mathbf{c}^{\prime}\mathbf{x} = \mathbf{p}^{\prime}\mathbf{b}$. By the Weak duality (Corollary 4.2), $\mathbf{x}^*$ and $\mathbf{p}^*$ are optimal solutions to the primal and the dual problems in \eqref{linopt}, respectively.
  \end{description}
\end{proof}

Exercise 4.3 (Solving linear programming problems is no harder than solving systems of linear inequalities)

Answers

Comments

Exercise 4.3 (Solving linear programming problems is no harder than solving systems of linear inequalities)

Answers

Comments

Add answer