# Perturbation approach to lexicography in Linear Programming

Consider a standard form problem, under the usual assumption that the rows of $$\textbf{A}$$ are linearly independent. Let $$\epsilon$$ be a scalar and define $$\textbf{b}(\epsilon)=\textbf{b}+\begin{bmatrix} \epsilon \\ \epsilon^{2} \\ \vdots \\ \epsilon^{m} \end{bmatrix}$$ For every $$\epsilon>0$$, we define the $$\epsilon$$-perturbed problem to the linear programming obtained by replacing $$\textbf{b}$$ with $$\textbf{b}(\epsilon)$$.

(a) Given a basis matrix $$\textbf{B}$$, show that the corresponding basic solution $$x_B(\epsilon)$$ in the $$\epsilon$$-perturbed problem is equal to $$\textbf{B}^{-1}[\textbf{b}|\textbf{I}]\begin{bmatrix} 1 \\ \epsilon \\ \vdots \\ \epsilon^{m} \end{bmatrix}$$

(b) Show that there exists some $$\epsilon^*>0$$ such that all basic solutions to the $$\epsilon$$-perturbed problem are nondegenerate, for $$0<\epsilon<\epsilon^*$$.

This is a question (3.15) from 'Introduction to Linear Optimization' by Dimitris Bertsimas. I am practicing all the problems in this textbook but I'm having hard time even understanding this question and solving it. Could anyone please help me how to approach to this problem or how to solve it? Thank you.

For part (a), we note that our basic solution for the perturbed problem is $$B^{-1} b(\epsilon) = B^{-1}b + B^{-1}I (\epsilon, \epsilon^2, ..., \epsilon^m)' \\ = B^{-1}[b | I] (1, \epsilon, ..., \epsilon^m)'$$
For part (b), we note that if $$(B^{-1}b)_i = 0$$, then $$(B^{-1}b(\epsilon))_i >0$$ for every $$\epsilon >0$$. If $$(B^{-1} b)_i \ne 0$$, then by continuity there exists $$\epsilon_i^B > 0$$ such that $$(B^{-1}b(\epsilon))_i \ne 0$$ for every $$0 < \epsilon < \epsilon_i^B$$. Letting $$\epsilon^* = \min_{B, i: (B^{-1}b)_i \ne 0} \epsilon_i^B$$ yields the result. Note $$\epsilon^* > 0$$ since there are finitely many basis matrices $$B$$ and finitely many rows in each, so we are taking the minimum of finitely many strictly positive numbers.
• This seems mostly right, but I'm not convinced that if $(B^{-1}b)_i =0$, then $(B^{-1}b(\epsilon))_i >0$ for every $\epsilon>0$. In this case, $(B^{-1}b(\epsilon))_i$ is some essentially-arbitrary linear combination of $\epsilon^1, \dots, \epsilon^m$ - but it's nontrivial (because $B^{-1}$ is invertible, so it can't have zero rows) and so it equals $0$ for at most $m$ values of $\epsilon$, one of which is $\epsilon=0$. In this case, let $\epsilon_i^B$ be the least positive root of $(B^{-1}b(\epsilon))_i$, and we again have $(B^{-1}b(\epsilon))_i \ne 0$ for every $0 < \epsilon < \epsilon_i^B$. Oct 10, 2022 at 13:59
• You are absolutely correct. My apologies on missing this. My brain ignored the $B^{-1}$ for some reason, so I was treating this as obvious since $(\epsilon, ... ,\epsilon^m)' > 0$, but it's more complicated. Thank you!! Oct 10, 2022 at 15:12