Exercise 3.25

Question

Consider a problem of the form $$ \min \; c^\top x \quad \text{s.t.} \quad A x = b, \quad 0 \le x \le u, $$ where $A$ has linearly independent rows and dimensions $m \times n$, and $u_i > 0$ for all $i$. \begin{itemize} \item[(a)]Let $A_{B(1)}, \ldots, A_{B(m)}$ be linearly independent columns of $A$ (the \textit{basic columns}). Partition the set of all $i \notin \{B(1), \ldots, B(m)\}$ into two disjoint subsets $L$ and $U$. Set $x_i = 0$ for all $i \in L$, and $x_i = u_i$ for all $i \in U$. Then solve $A x = b$ for the basic variables $x_{B(1)}, \ldots, x_{B(m)}$. Show that the resulting vector $x$ is a basic solution, and that it is nondegenerate if and only if $0 < x_i < u_i$ for every basic variable $x_i$. \item[(b)]Assume the basic solution constructed in part (a) is feasible. Form the simplex tableau and compute the reduced costs as usual. Let $x_j$ be a nonbasic variable such that $x_j = 0$ and $\bar{c}_j < 0$. As in Section~3.2, increase $x_j$ by $\theta$ and adjust the basic variables from $$ x_B \to x_B - \theta B^{-1} A_j. $$ To preserve feasibility, determine the largest possible value of $\theta$. How are the new basic columns determined? \item[(c)]Let $x_j$ be a nonbasic variable such that $x_j = u_j$ and $\bar{c}_j > 0$. We decrease $x_j$ by $\theta$ and adjust the basic variables from $$ x_B \to x_B + \theta B^{-1} A_j. $$ Given that feasibility must be maintained, what is the largest possible value of $\theta$? How are the new basic columns determined? \item[(d)]Assuming that every basic feasible solution is nondegenerate, show that the cost strictly decreases with each iteration of the method and therefore the algorithm terminates.

Aymen Mehrez · Accepted Answer

\noindent (a) For the first part of this question, the result is demonstrated in Exercise 2.3. \ Now, we prove that the resulting vector $x$ is nondegenerate if and only if $0 < x_i < u_i$ for every basic variable $x_i$. $$ \Rightarrow $$ Assume $x^*$ is an arbitrary nondegenerate basic feasible solution (Definition 2.10). Then, at most $n$ linearly independent constraints are active at $x^*$. Since the equality constraints $A x^* = b$ are already $m$ linearly independent and active, let $z_L$ and $z_U$ denote the numbers of active lower and upper bound constraints, respectively. Hence, $$ m + z_L + z_U \leq n \quad \Longleftrightarrow \quad z_L + z_U \leq n - m. $$ If equality holds ($z_L + z_U = n - m$), exactly $n$ constraints are active, and the solution is nondegenerate. Now, for any basic feasible solution, exactly $n - m$ variables are basic. If the solution is nondegenerate, none of the basic variables are at their bounds; otherwise, an additional bound constraint would become active, violating $z_L + z_U = n - m$. Therefore, for all basic variables $x_i$, $$ 0 < x_i^* < u_i. $$ $$ \Leftarrow $$ Conversely, if any basic variable satisfies $x_i^* = 0$ or $x_i^* = u_i$, then an additional constraint becomes active, implying $z_L + z_U > n - m$, and the basic feasible solution is degenerate. \vspace{1em} \noindent (b) Increase $x_j$ by $\theta$. Basic variables update as $$ x_B \mapsto x_B + \theta d_B,\qquad d_B := -B^{-1}A_j. $$ Feasibility $0 \le x_B + \theta d_B \le u_B$ gives, coordinatewise, $$ - x_{B(i)} \le \theta\, d_{B(i)} \le u_{B(i)} - x_{B(i)} \qquad (i=1,\dots,m). $$ If $d_{B(i)}=0$ the $i$-th constraint imposes no restriction on $\theta$. Otherwise divide by $d_{B(i)}$: $$ \begin{cases} d_{B(i)}>0: & \theta \le \dfrac{u_{B(i)}-x_{B(i)}}{d_{B(i)}},\[6pt] d_{B(i)}<0: & \theta \le \dfrac{-x_{B(i)}}{d_{B(i)}}\; (= -x_{B(i)}/d_{B(i)}). \end{cases} $$ Hence the largest feasible step is the usual ratio test $$ \theta^* \;=\; \min_{\,i:\,d_{B(i)}\neq 0} \begin{cases} \dfrac{u_{B(i)}-x_{B(i)}}{d_{B(i)}}, & d_{B(i)}>0,\[6pt] \dfrac{-x_{B(i)}}{d_{B(i)}}, & d_{B(i)}<0. \end{cases} $$ (The indices with $d_{B(i)}=0$ are ignored.) The leaving variable is any basic index $i$ attaining the minimum; $x_j$ then enters the basis. \vspace{1em} \noindent (c) Now let $x_j = u_j$ and $\bar{c}_j > 0$. We decrease $x_j$ by $\theta$, so $$ x_B \mapsto x_B - \theta d_B, \qquad d_B := -B^{-1}A_j. $$ Feasibility $0 \le x_B - \theta d_B \le u_B$ requires, componentwise, $$ - x_{B(i)} \le -\theta\, d_{B(i)} \le u_{B(i)} - x_{B(i)}. $$ Multiplying by $-1$ (and reversing inequalities where needed): $$ x_{B(i)} - u_{B(i)} \le \theta\, d_{B(i)} \le x_{B(i)}. $$ If $d_{B(i)} = 0$, no restriction on $\theta$. Otherwise, dividing by $d_{B(i)}$: $$ \begin{cases} d_{B(i)} > 0: & \theta \le \dfrac{x_{B(i)}}{d_{B(i)}}, \[6pt] d_{B(i)} < 0: & \theta \le \dfrac{x_{B(i)} - u_{B(i)}}{d_{B(i)}}. \end{cases} $$ Hence the largest feasible step preserving $0 \le x_B - \theta d_B \le u_B$ is $$ \theta^* = \min_{\,i:\,d_{B(i)}\neq 0} \begin{cases} \dfrac{x_{B(i)}}{d_{B(i)}}, & d_{B(i)} > 0, \[6pt] \dfrac{x_{B(i)} - u_{B(i)}}{d_{B(i)}}, & d_{B(i)} < 0. \end{cases} $$ The leaving variable corresponds to the basic index $i$ attaining this minimum, and $x_j$ enters the basis from its upper bound. \vspace{1em}

Exercise 3.25

Answers

Comments

Exercise 3.25

Answers

Comments

Add answer