2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ There is always an extreme point solution, in this case a corner point. Any other point can be formed as a convex combination of corner points. $\endgroup$ – Michael Dec 4 '16 at 3:19
  • $\begingroup$ @Michael if you've got the time I recommend developing that into an answer. If in particular you offer the simple proof that the non-corner points cannot have a lower value than those on the corresponding corners, you'd be done. $\endgroup$ – Michael Grant Dec 5 '16 at 0:22
  • $\begingroup$ @MichaelGrant : Thanks, I just did that below. $\endgroup$ – Michael Dec 5 '16 at 1:31
2
$\begingroup$

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\}$.

$\endgroup$

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.