This example is drawn from the following slide: http://www.ece.ust.hk/~palomar/ELEC5470_lectures/07/slides_Lagrange_duality.pdf
The pound symbol denotes the pseudo-inverse. Can someone explain why we need the positive semidefinite constraint on $A+\lambda I $ and more mysteriously, why do we need the range constraint?
I have the feeling that the positive semidefinite is needed to ensure existence of pseudo-inverse (Although I thought every matrix had a pseudo inverse)?
The Lagrangian is $$L(x,\lambda) = x^TAx+2b^Tx - \lambda(1-x^Tx) = x^T(A+\lambda I)x + 2b^Tx - \lambda$$ The dual problem is \begin{array}{ll} \text{maximize} & g(\lambda) \\ \text{subject to} & \lambda \geq 0 \end{array} where $g(\lambda)$, the dual function, is given by $$g(\lambda) = \inf_x L(x,\lambda) = \inf_x x^T(A+\lambda I)x + 2b^Tx - \lambda$$
PEDANTRY ALERT: Note the absence of any other constraints on $\lambda$. How is this possible? Well, the additional constraints are implicit, included in the domain of the dual function, $g$. That is for some values of $\lambda$, the infimum on $x$ is unbounded below; i.e., $g(\lambda) = -\infty$. What we always do is determine just what those domain constraints are, and make them explicit, by adding them to the list of dual constraints. Since it's so common to do this we tend to call the resulting model "the dual problem" instead. It is technically not the dual, but it is definitely equivalent to it.
With that said, let's explain what these implicit constraints are, by expanding just a bit on what Brian said above.
First, suppose $A+\lambda I \not\succeq 0$. Then there is at least one vector $v$ such that $v^T(A+\lambda I)v < 0$. In that case, define $x=t v$, and let $t\rightarrow +\infty$; then $g(tv) \rightarrow -\infty$. Therefore, for $g(\lambda)$ to be finite, it must be the case that $$A+\lambda I \succeq 0 \quad\Longleftrightarrow\quad \lambda \geq -\lambda_\min(A)$$ Either one of these will do---$\lambda_\min(\cdot)$ is actually a concave function of its input, so that is a convex constraint in $A$.
Second: consider the optimality condition on $x$: $$2(A+\lambda I)x + 2 b = 0$$ If $b\not\in\mathop{\textrm{Range}}(A+\lambda I)$, there is no solution to this condition. If this is so, then there must exist a $v$ such that $$(A+\lambda I)v = 0 \quad b^T v = 1$$ Then letting $x = -tv$ and allowing $t\rightarrow +\infty$ will again drive the infimum to $-\infty.$ So the second implicit constraint is indeed $$b\in\mathop{\textrm{Range}}(A+\lambda I)$$
If both of these constraints holds, then we have $x=-(A+\lambda I)^\# b$, as the slide says. Substituting this into $g(\lambda)$ yields $$g(\lambda) = b^T(A+\lambda I)^\#(A+\lambda I)(A+\lambda I)^\# b - 2 b^T (A+\lambda I)^\# b - \lambda$$ which, since $ZZ^\#Z = Z$ for any matrix $Z$, simplifies to $$g(\lambda) = -b^T(A+\lambda I)^\# b - \lambda$$