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.
Thanks to those that have already responded, you were very helpful. Here I will give the solution I have come up with, with more exposition than is provided in some of the other responses.
First we need the following lemma:
Lemma: $\lim_{\|x\| \to \infty} f(x) = \infty$. Some authors refer to this as $f$ being coercive.
Proof: Let $x_0 \in \mathbb{R}^n$ and let $v$ be a subgradient of $g$ at $x_0$, i.e. $x_0 \in \partial g(x_0)$. By equivalence of norms in finite-dimensional vector spaces, there exists a constant $c > 0$ such that $\|x\|_2 \leq c \|x\|$ for all $x \in \mathbb{R}^n$. By Cauchy-Schwarz and the trinagle inequality, for $\|x\| > 0$ we have
$$
\begin{align*}
\frac{| v^T(x - x_0) |}{\frac{m}{2}\|x\|^2}
&\leq \frac{\|v\|_2 \|x - x_0\|_2}{\frac{m}{2}\|x\|^2} \\
&\leq \frac{\|v\|_2 \|x\|_2 + \|v\|_2 \|x_0\|_2}{\frac{m}{2}\|x\|^2} \\
&\leq \frac{c\|v\|_2 \|x\| + \|v\|_2 \|x_0\|_2}{\frac{m}{2}\|x\|^2} \\
&= \frac{2c\|v\|_2 \|x\|}{m} \frac{1}{\|x\|} + \frac{2\|v\|_2 \|x_0\|_2}{m} \frac{1}{\|x\|^2}
\end{align*}
$$
The far right hand side of this inequality $\to 0$ as $\|x\| \to \infty$, which implies that $v^T(x - x_0) + \frac{m}{2} \|x\|^2 \to \infty$ as $\|x\| \to \infty$. Now we use the definition of subgradient:
$$
\begin{align*}
v^T(x - x_0) &\leq g(x) - g(x_0) \\
v^T(x - x_0) + \frac{m}{2}\|x\|^2 &\leq g(x) + \frac{m}{2}\|x\|^2 - g(x_0) \\
v^T(x - x_0) + \frac{m}{2}\|x\|^2 + g(x_0) &\leq f(x)
\end{align*}
$$
The left hand side of this $\to \infty$ as $\|x\| \to \infty$, so we conclude that $f(x) \to \infty$ as $\|x\| \to \infty$. $\square$
On to the main result. First, assume that $A$ is unbounded. If it is bounded, then it is compact, and the result follows immediately. There are 2 mutually exclusive possibilities:
Case 1: $f$ has a minimizer on $A$, in which case it is unique (see this thread).
Case 2: $f$ does not have a minimizer on $A$.
Assume we have case 2. Let $f^\star := \inf_{x \in A} f(x)$. $f^\star < \infty$ by assumption. Let $(x_k)$ be a sequence in $A$ such that $f(x_k) \to f^\star$. We now have two mutually exclusive subcases:
Subcase 2.1: $\sup_k \|x_k\| = d < \infty$. Define $B_d := \{ x \in \mathbb{R}^n \ : \ \|x\| \leq d\}$. Then for all $k$, $x_k \in \{ A \cap B_d \}$ which is closed and bounded and hence compact. Therefore $(x_k)$ converges in $A$, i.e. $x_k \to x^\star$ for some $x^\star \in A$. Continuity of $f$ then implies $f(x^\star) = f^\star$, which is a contradiction.
Subcase 2.2: $\sup_k \|x_k\| = \infty$. This implies $\|x_k\| \to \infty$, and by the Lemma this implies $f(x_k) \to \infty$ which implies $f^\star = \infty$ which contradicts $f^\star < \infty$.
Thus we conclude that Case 2 cannot occur, and therefore Case 1 must occur.
EDIT: After writing all of this out, it is clear that $f$ strongly convex is a stronger assumption than we require. $f$ strictly convex and coercive is sufficient for $f$ to have a unique global minimum on the convex set $A$.
Best Answer
It can be proved by following three steps.
(a) Let $\left\{{\Omega_{\alpha}}\right\} (\alpha \in I)$ be a collection of convex subsets of $\mathbb{R}^n$. Then $\bigcap_{\alpha \in I}\Omega_{\alpha}$ is also a convex.
proof: Taking any $x_1,x_2\in \bigcap_{\alpha\in I}\Omega_{\alpha}$. We get that $x_1,x_2\in \Omega_{\alpha}$ for $\alpha\in I$. And then we have $\theta x_1+(1-\theta)x_2\in \Omega_{\alpha}$ for any $\theta\in [0,1]$ since $\Omega_{\alpha}$ are convex sets. Thus $\theta x_1+(1-\theta)x_2\in \bigcap_{\alpha\in I}{\Omega_{\alpha}}$.
(b) Hyperplanes are convex and halfsapces are also convex. \begin{equation} \text{Hyperplanes}: \left\{{x|a^Tx=b}\right\} \quad \text{Halfspaces}: \left\{{x|a^Tx\leq b}\right\} \end{equation} proof: Assume that $x_1,x_2\in \Omega$, and we have $a^Tx_1=b, a^Tx_2=b$. Hence we can get
\begin{equation} a^T(\theta x_1+(1-\theta)x_2)=\theta a^T x_1+(1-\theta)a^Tx_2=b \end{equation} i.e., $(\theta x_1+(1-\theta)x_2)\in \Omega$. similarly, we also can prove that halfspaces are convex.
(c) As we observed from the definition of polyhedra. A polyhedron is defined as the solution set of a finite number of linear equalities and inequalities. It mean that a ployhedron is the intersection of a finite number of halfspaces and hyperplanes. Based on (b), we know that halfspaces and hyperplanes are convex. Furthermore, we know polyhedron is convex based on (a).