Maximum of quadratic form subject to equality and non-negativity constraints

Question

$$\begin{array}{ll} \text{maximize} & x^T A \, x\\ \text{subject to} & \sum_{i=1}^{n} x_i = k\\ & x_i \ge 0\end{array}$$

where

• $x$ is an $n \times 1$ vector

• $A \in \{0,1\}^{n \times n}$ is a symmetric Boolean matrix with zeros on the main diagonal (i.e., $A_{ii} = 0$)

• $k$ is a constant

Answer 1

This answer is incomplete, as it does not address the inequality condition. Leaving it up for now, as it does give the general direction for a solution.

---

The Karush–Kuhn–Tucker conditions state that a maximum value ^[1] $\mathbf{x}_0$ exists for $$f(\mathbf{x})=\mathbf{x}^T A \mathbf{x}$$ As long as a number $v$ exists such that: $$\left(\begin{array} & -A & \mathbf{1} \\ \mathbf{1}^T & 0\end{array}\right)\left(\begin{array} & \mathbf{x}_0 \\ v\end{array}\right)=\left(\begin{array} & \mathbf{0} \\ k\end{array}\right)$$ Thus we have:

$$A \mathbf{x}_0 = \mathbf{v},\quad \sum x_{0i} = k$$ If $A$ is invertible, and combining the above equations you get that: $$\mathbf{x}_0=k\cdot \frac{A^{-1}\mathbf{1}}{ \mathbf{1}^T A^{-1}\mathbf{1}}$$

N.B. In the above, all bold values are vertical $1\times n$ vectors.

Example:

Take: $$A=A^{-1}\left(\begin{array} & 0 & 1 \\ 1 & 0\end{array}\right)$$ This leads to $f(x) = 2x y$, which under the constraint $x+y=k$, clearly has a maximum at $\mathbf{x}=\mathbf{k}/2$, which is what you get from the solution as well.

^[1] _{Convex Optimization, Stephen P. Boyd, Lieven Vandenberghe, p. 522}