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?

  • $\begingroup$ please the re-edited problem above, thanks! $\endgroup$ – 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^*$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.