why maximizing the L1 norm of a vector can not be formed as a linear programming problem

Question

I am new to optimization, and one of the examples the professor gave in class was that we cannot form $\max \lvert\lvert x \rvert\rvert$ subject to $Ax=b$ as a linear programming problem. The reason the professor gave was that it was nonconvex. I was wondering why not being convex implies it cannot be written as a linear programming problem (since we can write $\min \lvert\lvert x \rvert\rvert$ as an LP), and how to prove it is not convex?

Answer 1

An $L_{1}$ maximization problem can have multiple isolated local maximum solutions but that can never happen in an LP. Thus, in general, you can't construct an equivalent (having the same set of local maximum points) LP. Yes, it's possible in some trivial cases, but not in general.

For example, consider

$\max | x | $

$ -1 \leq x \leq 2$

Here, the local maximum points are isolated at $x=-1$ and $x=2$. Since the optimal solutions to an LP form a convex set, you cannot construct an LP that has only these two optimal solutions.

It's relatively easy to show that $L_{1}$ maximization is NP-Hard. Start with a 0-1 ILP feasibility problem:

$Ax=b$

$x \in \left\{ 0,1 \right\}^{n}$

You can relax the constraints to $0 \leq x \leq 1$ but add the objective

$\max \sum_{i=1}^{n} | x_{i}- 1/2 |$.

to get

$\max \sum_{i=1}^{n} | x_{i} - 1/2 |$

subject to

$Ax=b$

$0 \leq x \leq 1$.

If the globally optimal value of this maximization problem is $n/2$, then the original 0-1 ILP feasibility problem has a $0-1$ integer solution. If the globally optimal value is less than $n/2$, then the original 0-1 ILP has no feasible solution.