# Maximizing convex quadratic form over hypercube

Given an $n$-dimensional positive-definite matrix $A$, I want to solve the following optimization problem: $$\max_{x\in\mathbb{R}^n}\ x^TAx\quad \mathrm{s.t.}\quad \underline{x}_i \leq x_i \leq \overline{x}_i\,\forall i\in\{1,\ldots,n\},$$ where the $\underline{x}_i$ and $\overline{x}_i$ are constants definining a box bounding my optimization domain.

The maximizer of this problem seems to always be either $x^*=(\underline{x}_1,\cdots,\underline{x}_n)^{\top}$, or $x^*=(\overline{x}_1,\cdots,\overline{x}_n)^{\top}$ (the northeast or southeast corners of box), in all of the numerical examples that I've tried. Is this always true, and if so, how do I prove it formally?

• please the re-edited problem above, thanks! – Devin Jan 11 '18 at 4:02

Think about the problem geometrically: the quadratic function $x^TAx$ has a unique local minimum (at the origin) and grows in all directions, with isosurfaces in the shape of ellipsoids, in a way that can be formalized by computing the SVD of $A$. It is true that the maximum of the function, restricted to a box, will occur at a corner of the box (but not necessarily one of the two corners you've identified.)

Here's a hint: suppose $x^*$ is a critical point of $f(x) = x^TAx$, subject to the box constraint, and lies on a face of the box of dimension $\geq 1$ (so that there exists a direction $v$ with $x^* \pm \epsilon v$ on the boundary of the box for all sufficiently small $\epsilon$.)

1) Argue that $\nabla f \cdot v = 0$;

2) Prove that $f(x^*+\epsilon v) > f(x^*)$ for sufficiently small $\epsilon > 0$;

3) Explain the consequences of the above for the character of the critical point $x^*$.

• thanks a lot, but pls. notice that the problem is a maximization rather minimization, so the maximizer must be the extreme point – Devin Jan 11 '18 at 5:24
• @Devin ?? All of my answer is about maximization, not minimzation... – user7530 Jan 11 '18 at 5:49