Consider a bounded polytop $P = \{x \in \mathbb{R}^n \mid Ax \geq b\}$, we know the extreme points of $P$ are $p_1, p_2, …, p_r$.
Then consider the following two problem:
$$\min e^T(x + \mid x\mid)$$
$$s.t. x \in P$$
where $\mid x\mid = \begin{bmatrix}\mid x_1\mid \\ \mid x_2\mid \\ \vdots \\ \mid x_n\mid\end{bmatrix}$.
$$\max e^T(\mid x\mid – x )$$
$$s.t. x \in P$$
For the min problem, we can transform it into a linear program by introducing $\mid x\mid \leq t$. As for the max problem, I think it can not be transformed into a LP since the objective function is convex.
My question is how to solve these two problems based on known information. Can we check every extreme points to get the optimal solution?
I think we can solve the max problem by checking every extreme points.
Let $v(x) = e^T(\mid x\mid – x )$, then it is a convex function.
By Jensen’s inequality, we know for any point $ \bar{x} \in P$, $v(\bar{x}) = v(\sum\limits_{i=1}^{r} \lambda_i p_i) \leq \sum\limits_{i=1}^{r}\lambda_iv(p_i) \leq \max_{i \in \{1, 2, …, r\}}v(p_i)$.
Best Answer
To find the minimum, it does not suffice to compare the function values at the extreme points. For example, take the polyhedron $\{x \in \mathbb{R}^2 : ||x-(0.9,0.9)||_1 \leq 1\}$. The function values at the extreme points are $f((-0.1,0.9)) = f((0.9,-0.1) = 1.8$, $f((1.9,0.9)) = f((0.9,1.9))=5.6$, but $f((0.4, 0.4))=1.6$.