Almost a linear program. How to solve efficiently?

Question

How can one go about solving this optimization problem efficiently? Unfortunately it is a maximization instead of a minimization, which stymied my attempts at converting it into an LP.

$$ \mbox{maximize} \sum_i \mbox{max}_{j=1}^{k} \{ {\bf c_{ij}^T x}\} $$ $$\mbox{s.t.} \;{\bf A x} \le {\bf b}$$ $$ \mbox{and} \; {\bf x} \ge 0$$

$$ {\bf x} \in {R}^d$$ $$ {\bf c_{ij}} \in {R}^d \;\;\ \forall i, j$$ $$ A \in {R}^{n \times d} $$ $$ b \in {R}^n$$

We can assume that the constraints ${\bf A x} \le {\bf b}$ define a compact polyhedron.

---

A simpler version of the problem to make it a bit more clear. (Here all four ${\bf c_{ij}}$ are known d-dimensional vectors.)

$$ \mbox{maximize} \;\; \{ \mbox{max}({\bf c_{11}^T x}, {\bf c_{12}^T x}) + \mbox{max}({\bf c_{21}^T x}, {\bf c_{22}^T x})\}$$ $$\mbox{s.t.} \;{\bf A x} \le {\bf b}$$ $$ \mbox{and} \; {\bf x} \ge 0$$

Answer 1

This is not possible (yet or never). I will show that this problem is NP-complete by reducing SAT into your problem.

Consider an instance of SAT as a boolean formula under conjunctive normal form, using $c$ clauses and $n$ different variables ($v_1$, $v_2$,…, $v_n$). We will make an instance of your problem with vector size $n+1$ and $1\le i \le c$.

First let $A$ be the identity matrix of size $n+1$, and $b$ the vector with only $1$. Hence $Ax<b$ and $x>0$ implies that $x$ is a boolean vector (only $0$s and $1$s).

Next consider the clause $i$ formed by a disjunction of $v$ variables. Let $c_{ij}$ ($1\le j\le v$) such that :

• if the $j$th variable used in the clause $i$ is positive and equals to $v_m$, let $c_{ij}$ be a vector with only $0$ except in position $m$ equals to $1$.
• if the $j$th variable used in the clause $i$ is negative and equals to $\neg v_m$, let $c_{ij}$ be a vector with only $0$ except in position $m$ equals to $-1$ and $1$ in position $n+1$.

If you try to maximize $m_i=\max_{j=1}^{v}c_{ij}^Tx$, you remark that :

• you can put a $1$ at position $n+1$ in $x$, because in $c_{ij}$ at position $n+1$ you will always have $0$ or $1$.
• you need to have a $1$ at the right position if $c_{ij}$ is linked to a positive variable in clause $i$ to have $c_{ij}^Tx=1$, else $c_{ij}^Tx=0$.
• you need to have a $0$ at the right position if $c_{ij}$ is linked to a negative variable in clause $i$ to have $c_{ij}^Tx=1$, else $c_{ij}^Tx=0$.

Hence $m_i=1$ if and only if the clause $i$ is satisfied by $x$ (considering the $n$ first coordinates of $x$ as true/false value for variable $v_1$, …, $v_n$).

So, the formula is satisfiable iff the maximum of the instance created is equal to $c$ (the number of clauses satisfied).

Hence your problem is NP-hard, because this reduction is polynomial (quadratic indeed)

It is NP-complete, because with the right $x$, you can easily compute the maximum (and verify any assumption on it).

---

Note that you can fill with $c_{ij}=0$, if you need to have $1\le i\le k$ and $1\le j \le k$ with the same $k$ for both.

Answer 2

We have that $\mathbf{c_{ij}^T\,x} $ is linear in $\mathbf x$ so $\max_j \mathbf{c_{ij}^T\,x} $ is convex in $\mathbf x$, thus $\sum_i \max_j\mathbf{c_{ij}^T\,x}$ is also convex in $\mathbf x$. Now we are given that the set $C=\{\mathbf x : \mathbf{Ax}\le \mathbf{b}\text{ and } \mathbf x \ge 0\}$ is a compact polyhedron, in particular it is a convex set. Since we are maximizing a convex function on a convex set we know that at least one of its maxima must lie on an extreme point. Thus, to find one maximum we need to evaluate the objective function at the vertices of $C$, which is a finite set.