I am trying to get the optimality condition for the following problem
$$\begin{array}{ll} \text{minimize} & c^T y\\ \text{subject to} & Ay = 0\\ & y^T B y \le 1\end{array}$$
where $B$ is positive semidefinite.
I observed that $y^TBy$ must be equal to $1$ because if it is not the case, we can scale $y$ to let $y^TBy$ equals to 1 so that we can make $c^Ty$ smaller. Can we derive this fact using KKT conditions?
The Lagrangian function of this problem is
$$L(y,\lambda,\mu)=c^Ty + \lambda^T(Ay)+\mu(y^TBy-1)$$
and, according to the KKT condition,
\begin{align*} c + A^T \lambda + \mu(By)& =0\\ Ay&=0\\ \mu(y^TBy-1)&=0 \\ y^TBy-1&\le 0\\ \mu&\ge0 \end{align*} It seems as if it doesn't matter whether if $y^TBy = 1$. What am I missing? And what is the optimility condition for this problem?
I found it interesting to try and tease this out myself.
As I suggested in the comment, it is not necessary for $y^TBy=1$ at the optimum. For one thing, this problem can be unbounded below. For instance, suppose there exists a vector $v$ satisfying $$c^Tv=1\quad Av=0\quad Bv=0$$ Then clearly, $y=tv$ is feasible for any value of $t$; in particular, $y^TBy=0\leq 1$. And by driving $t\rightarrow-\infty$, we see that $c^Ty\rightarrow-\infty$ as well.
But even if the problem does have a finite solution, it need not satisfy $y^TBy=1$. As Andrea hints at, the complementary slackness condition $\mu(y^TBy-1)$ implies that $\mu=0$ or $y^TBy=1$ (or both). If $\mu=0$, then the optimality conditions reduce to $$c+A^T\lambda = 0 \quad A y = 0 \quad y^TBy \leq 1$$ Interestingly, the first condition is independent of $y$, and if it is true, then $$c^Ty = (-A^T\lambda)^T y = \lambda^T A y = 0$$ Aha! So if $c+A^T\lambda=0$ for any $\lambda$---that is, if $c\in\mathop{\textrm{Range}}(A^T)$---then the optimal value is zero, and $y=0$ is one of those optimal points.
On the other hand, if $c\not\in\mathop{\textrm{Range}}(A^T)$, then it cannot be the case that $\mu=0$, so the optimality conditions become $$c+A^T\lambda + \mu By=0 \quad Ay=0 \quad y^TBy=1 \quad \mu > 0$$ And in that case, we have $$c^T y= -(A^T\lambda+\mu B y)^Ty = -\lambda^TAy-\mu y^TBy=-\mu$$ Wow! The value of the Lagrange multiplier for the $y^TBy\leq 1$ constraint is equal to the negative of the optimal value of the problem. And that's true for $\mu=0$ and for $\mu>0$.