Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Statement

"Base is degenerate IFF its corresponding basis matrix is singular" is wrong according to my Linear-programming teacher Mat-2.3140 in Aalto University (translated from Finnish here/here)

Why it is wrong according to my teacher below

Because "singularity corresponds to the fact that two or more restrictions are collinear (Finnish, "samansuuntaiset") while the degeneration requires only that sufficient amount of lines cuts at the same point" translated from Finnish here.

Now the key problem is collinearity, I think my teacher made a slight mistake there. Collinearity is not sufficient condition but necessary condition. The left case has a solution and the right case does not have because of the collinearity and the oppositely pointing gradients.

enter image description here

Where the left has the orange-spot solution while the right has no solution because the feasible set is empty (because of the collinear opposite restrictions).

Now what is the purpose of the term "singular" if two totally-different cases are described with the same adjective? Does this singular basis matrix just mean that the rank of the restriction n-times-n -matrix is n? And the term Degeneracy is just some technical term?

share|improve this question
1  
This answer might be of interest. –  user17794 Dec 18 '12 at 22:02
    
@TimDuff thank you, I wish people used more pictures...they convey so much more information here, not having to second-guess different terms. –  hhh Dec 18 '12 at 22:11
    
@hhh: I killed the singularity tag. It means way too many different things in too many fields of mathematics. –  Willie Wong Dec 19 '12 at 9:34

1 Answer 1

up vote 0 down vote accepted

Definitions

  • Basic solution is such that it satisfies the conditions mentioned on the page 50 here.
  • The difference between the terms basic solution and basic feasible solution is the other-than-equal constraints: equal-constraints need to be valid for basic solution but the feasible solution also requires inequality constraints to be valid.
  • "A basic solution of $\bar x\in \mathbb R^n$ is said to be degenerate if more than $n$ of the constraints are active at $\bar x$." Page 58 or scan here.
  • This basically means that when you have more than two lines or restrictions in one point valid, you have a degenerate point. The word degenerate is purely technical term, just think its definition.
  • "If a vector $\bar x^*$ satisfies $\bar a_{i}^{'} \bar x^*=b_i$ for some $i$ in $M_1$, $M_2$ or $M_3$, we say that the corresponding constraint is active or binding at $\bar x^*$" or scan here of the page 48.
  • This is a very unintuitive way of defining the term but it basically means things such as "Suppose restriction line L1 cuts the optimal value X1, now you say that L1 is active at point X1. If you have more lines cutting the point X1, then you say that they such as L1, L2 and L3 are active at X1. If you have more than one restriction active then you have degenerate solution. I suggest you to take a pen-and-paper, this over-formalism is very unintuitive but things are very simple -- think it with your hands: if they cross and the optimal is in crossing, you have two active constraints."

I try to solve this puzzle myself. We use the Bertsimas book "Introduction to Linear Optimization" so I refer to its definitions. You can find my explanations between the lines to recite on the formalism.

I think this is a trick question. Degenerate base means that you have more than two restrictions valid in one point: it can be a problem with Simplex algorithm when the algorithm will never terminate. The singular basis matrix means collinearity and has nothing per se to do with the degeneration.

When you have a degenerate solution, you may not have global solution but you do have at least local solution. When you proceed Simplex, you go from one extreme point to another (not counting the arbitrary starting point). This is because in linear programming you mostly consider convex problems making the optimization easier -- at least my course and problems from the book have been convex.

Counter example to falsify the proposition

Suppose you have restrictions $y=x$ and $y=2x$. By the first implications, your basis matrix is singular but $B=\begin{pmatrix} 1 & 0 \\ 0 & 2 \\ \end{pmatrix}$ so that $\bar y = B \bar x$ where $B$ is not a singular matrix because its determinant is not zero namely $det(B)=2$. Singular basis matrix means the same as in linear algebra i.e. the determinant is zero. So the statement is false.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.