# Almost a linear program. How to solve efficiently?

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$$

• Check your question: $i$ doesn't contained in the summand max{…} – Boris Novikov Dec 5 '13 at 15:28
• You can convert any maximization problem into a minimization problem by multiplying the function to be maximized by $-1$. – Nameless Dec 5 '13 at 15:41
• @Nameless: Changing the sign doesn't really help because of the max inside the sum. The -1 can be absorbed into the coefficients $a_{ij}$ and the max will turn to a min as well. – Innuo Dec 5 '13 at 15:49
• You iterate over $i$ in the summand and you iterate over $j$ in the max function. Given that $\mathbf{A}$ lives in $R^{n \times d}$, Are you sure $a_{ij}$ lives in $R^d$? Reads like it's just a scalar. Please try to explain your objective function in a clear fashion. Are you trying to say that the maximum is over a list of linear expressions involving $\mathbf{x}$ and some column from $\mathbf{A}$? – baudolino Dec 26 '13 at 18:39
• What is the relation between the matrix A and the aij? What is the dimension of A? – Sergio Parreiras Dec 26 '13 at 18:54

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.

• I don't understand how your constraints constrain the problem to be boolean. Don't they just constrain the variables to be in unit interval: $x \in (0, 1)$ – Innuo Dec 27 '13 at 17:07
• Yes, you're right !! hopefully, it does not change the end. Every $m_i$ will be $\in(0,1)$, But only if there are equal to $1$ the clause will be considered as satisfied, and only if the overall maximum is $c$ will the entire formulae will be satisfied. – Xoff Dec 27 '13 at 17:11
• I don't follow your argument very well. I will have to come back to it. To aid me, can you show why a similar argument doesn't work if I had a minimize on the outside instead of maximize? (With a minimize instead of maximize my problem can be transformed into a linear program which can be solved in polynomial time.) – Innuo Dec 27 '13 at 17:25
• Because both maxima (the one outside and the inside-sum ones) work "in the same direction", so they can use to ensure some properties of the sum. If you minimize on the outside, you can only see if one clause is satisfied, so it only cares about disjunctive formula (formula with only $\vee$), this is much simpler. (can be solved in linear time) – Xoff Dec 27 '13 at 19:00
• Hmm, shouldn't your opening claim be "it is not possible unless P=NP"? ;) – baudolino Dec 27 '13 at 20:06

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.

• Thanks. Is there any way to visit the vertices efficiently? Xoff's answer above suggests not. – Innuo Dec 30 '13 at 20:43
• @Innuo: I'm afraid I don't know the answer and agree that Xoff's answer suggests that in theory there is no way. But algorithms that sometimes have bad theoretical properties may perform quite well in practical problems so I would not lose all hope. – Sergio Parreiras Dec 30 '13 at 21:00