To minimize $x^TAx$ where $A$ is not necessarily positive semi-definite with constrains?

Question

Let $A\in \mathbb{n\times n}$ be a symmetric matrix. Let $x\in \mathbb{R}^{n\times 1}$ be an unknown vector.

The problem is $$\min \limits_x \{E(x)=x^TAx\}$$

where $x\in C$, $C$ is a convex set. $C=\{x|\sum\limits_i^n x_i=0\}$.

Is there any way to find $x^*=\arg\min\limits_{x\in C} x^TAx$?

Since $A$ is an input, I am not sure

1 it is positive semidefinite (the objective is convex);

2 or it is negative semidefinite (the objective is concave);

3 or indefinite (the objective is neither concave nor convex. )

Case 1 is simple to calculate the global solution.

In case 2, 3, is there any way to calculate $x^*$?

The convex conjugate of the convex conjugate of $E(x)$ is convex.

The convex conjugate of $E(x)$ is, $$E^*(x)=\max\limits_y<x,y>-y^TAy.$$

Since $A $ may be indefinite, it is still difficult for me. Is there any available literature for this problem? Thank you in advance.

Answer 1

The orthogonal projection on the linear subspace $C$ is $P = I - e e^T/n$ where $e$ is the vector of all $1$'s. You're essentially asking whether the matrix $PAP$ is positive or negative semidefinite.

If $A$ has more than one positive eigenvalue, $PAP$ can't be negative semidefinite, and if $A$ has more than one negative eigenvalue, $PAP$ can't be positive semidefinite. For example, suppose $u$ and $v$ are eigenvectors for positive eigenvalues $\lambda$ and $\mu$ respectively. If neither $u$ nor $v$ is in $C$, then $w = (v^T e) u - (u^T e) v$ is a nonzero vector in $C$, and $w^T A w = \lambda (v^T e)^2 (u^T u) + \mu (u^T e)^2 (v^T v) > 0$.

Answer 2

The indefinite case cannot generally have a solution. Look at an easy example like $$A := \begin{pmatrix} 1 & 0 \\ 0 & -2 \\ \end{pmatrix}$$ Letting $y := \begin{pmatrix} -x \\ x \\ \end{pmatrix}$, $$y'Ay = -x^{2}$$ which diverges.

Similarly, in the negative (semi-)definite case, taking $$A := \begin{pmatrix} -1 & 0 \\ 0 & a_{2,2} \\ \end{pmatrix}$$, with $a_{2,2} = 0 (-1)$, and $y$ as above, $$y'Ay = -x^2 (-2x^{2}).$$