1
$\begingroup$

I am trying to solve exercise 2.3 of the book "Introduction to linear optimization" by Bertsimas and Tsitsiklis, which states:

$\textbf{ Exercise 2.3 (Basic feasible solutions in standard form polyhedra with upper bounds)}$ Consider a polyhedron defined by the constraints $Ax = b$ and $0 \leq x \leq u$, $u\geq0$ and assume that the matrix has linearly independent rows.

Prove an analog of Theorem 2.4.

Where Theorem 2.4 is:

$\textbf{Theorem 2.4}$ Consider the constraints $Ax=b$ and $\geq 0$ and as­ sume that the $m \times n$ matrix $A$ has linearly independent rows. A vector $x \in \mathbb{R}^n$ is a basic solution if and only if we have $Ax = b$, and there exist indices $B (1) , . . . , B (m)$ such that:

$\bullet\ \text{The columns $A_{B(1)},...,A_{B(m)}$ are linearly independent} \\ \bullet\ \text{If $i \neq B(1),...,B(m)$ then $x_i=0$}$


My reformulation of theorem 2.4 would be the following:

$\textbf{Theorem}$ Consider the constraints $Ax = b$ and $0\leq x\leq d$ and as­sume that the $p \times n$ matrix $A$ has linearly independent rows. A vector $x \in \mathbb{R}^n$ is a basic solution if and only if we have Ax = b, and there exist indices $B (1) , . . . , B (p)$ such that:

$\bullet\ \text{The columns $A_{B(1)},...,A_{B(p)}$ are linearly independent;}\\ \bullet\ \text{If $i\neq B (1) , . . . , B (p)$, then $x_i = 0 $ or its respective upper bound $d_i$.}$

$\textit{Proof}$: Suppose that $x$ satisfies both conditions. Then it is true that: \begin{align} \begin{split} Ax = \sum_{i=1}^{p} A_{B(i)} x_{B(i)}+\sum_{i\neq B(1),...B(p)} A_i x_i = b\\ \sum_{i=1}^{p} A_{B(i)} x_{B(i)} =b-\sum_{i\neq B(1),...B(p)} A_i x_i \end{split} \end{align} Since the columns $A_{B(i)}$ $i=1,...,p$ are linearly independent, $x_{B(i)}$ $i=1,...,p$ are uniquely determined. By Theorem 2.2 , there are n linearly independent active constraints, and this implies that x is a basic solution.

For the converse, let us assume x is a basic solution. Let $B(1),...,B(k)$ all the indices such that $x_{B(i)} \neq 0$ and $x_{B(i)} \neq d_i$ for all $i=1,...,k$.

Since $x^*$ is a basic solution, the system of equations formed by the active constraints $\sum_{i=1}^{n} A_i x_i = b$, $x_i=0$, $x_ i=d_i$ $i \neq B(1),...B(k)$ has a unique solution (Theorem 2.2). This implies that the columns $A_{B(1)},...,A_{B(k)}$ are linearly independent and so $k\leq p$.

Since $rank(A) = p$, we can choose $p-k$ more columns so that the columns $A_{B(1)},...,A_{B(p)}$ are linearly independent. Moreover if $i \neq B(1),...,B(p)$, then it is also true that $i \neq B(1),...,B(k)$, since $k \leq p$ and $x_i=0$ or $x_i=d_i$.


Where

$\textbf{Theorem 2.2}$ Let $x^*$ be an element of $\mathbb{R}^n$ and let I={i : $a_i^{'}x_i=b_i$} be the set of indices of constraints that are active at $x^*$. Then, the following are equivalent:

$\bullet\ \text{There exist n vectors in the set ${a_i : i \in I}$ that are linearly independent;}\\ \bullet\ \text{The system of equations $a^{'}_ix=b_i$ has a unique solution}$

Is my reformulation (and proof) of theorem 2.4 correct?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.