I need help for the following problem:
$$ \max_x x^Tx\quad \mathrm{s.t.}\quad x^TAx+b^Tx\leq c, $$ where A is symmetric, square and positive semidefinite, c is a real scalar and b is a real vector.
I tried to solve it with the KKT conditions, but I get stuck at the point where I have to determine the Lagrange multiplier $\lambda$.
My steps look like this
1. Define
$$
H(x,\lambda)=x^Tx-\lambda (x^TAx+b^Tx-c)
$$
2. Get a candidate of the optimal solution $x^*$ via
$$
\dfrac{\delta H}{\delta x}=2x^*-\lambda (2Ax^*+b)=0,
$$
which leads to
$$
2(I-\lambda A)x^*=\lambda b
$$
and assume we choose $\lambda$ so that $I-\lambda A$ is nonsingular I get
$$
x^*=\frac{1}{2}(I-\lambda A)^{-1}\lambda b
$$
3. I try to determine $\lambda > 0$ by
$$
(x^*)^TAx^*+b^Tx^*\leq c
$$
$$
\Leftrightarrow \frac{\lambda^2}{4} b^T(I-\lambda A)^{-1}A(I-\lambda A)^{-1}b + \frac{\lambda}{2}b^T(I-\lambda A)^{-1}b \leq c
$$
$$
\Leftrightarrow \frac{\lambda}{2} b^T(I-\lambda A)^{-1}[\frac{\lambda}{2}A(I-\lambda A)^{-1} + I]b \leq c
$$
$$
\Leftrightarrow \frac{\lambda}{2} b^T(I-\lambda A)^{-1}[\frac{\lambda}{2}A + (I-\lambda A)](I-\lambda A)^{-1}b \leq c
$$
$$
\Leftrightarrow \frac{\lambda}{2} b^T(I-\lambda A)^{-1}[(I-\frac{\lambda}{2} A)](I-\lambda A)^{-1}b \leq c
$$
And that is the point where I am stuck... Does someone have an idea how I could continue?
I assume the data are at least such that the problem is feasible. Let $g(x) = x^T A x + b^T x$ for every $x$. Let $\ker A$ denote the null space of $A$.
There are two cases.
Case 1:
If $A$ has rank deficit, then the feasible set is unbounded and thus the problem is unbounded. Here again we have two cases. Let $b = b_0 + b_1$ where $b_0\in\ker A$ and $b_1$ is in the image (orthogonal to $\ker A$).
Sub case 1: $b_0 \ne 0$.
Then, for every $t \ge 0$ we have $$ g(x - tb_0) = g(x) - t\|b_0\|^2 \le g(x). $$ So, if there is a feasible point $y$, then the ray $y-tb_0$ is also feasible. As it is unbounded, the problem is unbound.
Sub case 2: $b_0=0$.
Let $u\in\ker A\setminus\{0\}$. Then, we have $g(x + u) = g(x)$ for any $x$. Thus, the feasible set contains at least a line and is unbounded again.
Case 2:
Let $A$ be positive definite. Notice that the minimum $y$ of $g$ is feasible. Thus, the feasible set is in fact the ellipsis $y+E$ with $E = \{ u \mid u^T A u \le r^2 \}$ and $r = \sqrt{c - g(y) }$. In particular we have $$ \max_{g(x)\le c} \| x \| = \max_{u\in E} \| y+u \| = \max_{\|v\|\le r} \| y + A^{-1/2} v\|. $$
I don't see an analytical solution in case of $y\ne 0$. In case $A, b, c$ are given, one can at least (try to) solve it with numerical methods. We can also obtain following non-trivial lower bound. Let $N$ be an $n\times (n-1)$ matrix whose columns are an orthonormal basis of the orthogonal space of $y$. Then, for $B = N^T A N$ we have $$ \max_{u^T A u \le r^2} \|y + u \| \ge \|y\| + \max_{w^T B w \le r^2} \|w\|. $$ The solution of right hand side is given by an eigenvector $w^*$ to the least eigenvalue $\lambda_1$ of $B$ with $\|w^*\| = r/\sqrt{\lambda_1}$.