Bounded Quadratic Concave Minimization

Question

Say I have the following optimization problem \begin{equation*} \begin{aligned} & \underset{x \in \mathbb{R}^n}{\text{minimize}} & & x^\top Qx + c^\top x \\ & \text{subject to} & & 0 \leq x_i \leq u_i, \; \forall i \end{aligned} \end{equation*}where $Q$ is a negative semi-definite matrix and each $u_i$ is a non-negative real number. This problem is non-convex as we are trying to minimize a concave function. However, since the problem is bounded there exists a solution. If we envision the bounded region as a hyper-cube, my question is this: is one of the corners of the hyper-cube always a minimizer of the function? Note I am not asking if it is possible for a non-corner point to also minimize the function, just if is possible for a non-corner point to have a strictly lower function value than any of the corner points.

Answer 1

Let $u_i$ be given positive real numbers for $i \in \{1, ..., n\}$. Define the box $H$ by:
$$H = \{(x_1, …, x_n) \in \mathbb{R}^n : 0 \leq x_i \leq u_i \quad \forall i \}$$ Note that $H$ is the convex hull of its corner points. Let $f:H\rightarrow\mathbb{R}$ be a concave function.

Suppose $z \in H$. But $z = \sum_{i=1}^{M} \theta_i c_i$ for some positive integer $M$, corner points $c_i \in H$, and probabilities $\theta_i\geq 0$ such that $\sum_{i=1}^M \theta_i=1$. Then $$ f(z) = f\left(\sum_{i=1}^M \theta_i c_i\right) \overset{(a)}{\geq} \sum_{i=1}^M \theta_i f(c_i) \geq \sum_{i=1}^M\theta_i\min_{i \in \{1, …, M\}} f(c_i) = \min_{i \in \{1, …, M\}} f(c_i)$$ where (a) uses the definition of concave. So for every point $z \in H$, there is a corner point $c_j \in H$ such that $f(z) \geq f(c_j)$. A similar argument implies that if $W$ is any subset of $\mathbb{R}^n$ and $f:Conv(W)\rightarrow\mathbb{R}$ is a concave function, then for any $z \in Conv(W)$, there is a point $c \in W$ such that $f(z) \geq f(c)$.

---

The case when $H$ is a box allows one to represent every point $z=(z_1, ..., z_n) \in H$ as a convex combination of the corner points as follows: $$ z = \sum_{i_1=0}^1\sum_{i_2=0}^1...\sum_{i_n=0}^1 p_{1,i_1}p_{2,i_2}...p_{n,i_n} \underbrace{(u_1i_1, u_2i_2, ..., u_ni_n)}_{\mbox{corner point}} $$ where $p_{i,1} = z_i/u_i$ and $p_{i,0} = 1-z_i/u_i$. This representation sums over all $2^n$ corner points. (There are representations that sum over only $n+1$ corner points.) To see that this particular representation works, take the first entry: \begin{align} \sum_{i_1=0}^1\sum_{i_2=0}^1...\sum_{i_n=0}^1 p_{1,i_1}p_{2,i_2}...p_{n,i_n} u_1i_1 &= \sum_{i_1=0}^1 p_{1,i_1}u_1i_1 \sum_{i_2=0}^1...\sum_{i_n=0}^1p_{2,i_2}...p_{n,i_n} \\ &= \sum_{i_1=0}^1 p_{1,i_1}u_1i_1 \\ &= (1-z_1/u_1)0 + (z_1/u_1)u_1 \\ &= z_1 \end{align} Similar holds for all other entries $\{2, ..., n\}$.