# Constraints involving $\max$ in a linear program?

Suppose

\begin{align*} \min A &\mathrm{vec}(U) \\ &\text{subject to } U_{i,j} \leq \max\{U_{i,k}, U_{k,j}\}, \quad i,j,k = 1, \ldots, n \end{align*}

where $U$ is a symmetric $n\times n$ matrix, and $\mathrm{vec}(U)$ reshapes $U$ into a one-dimensional vector with $n^2$ entries.

The part of the above program that gives me problems is the $\max\{⋅,⋅\}$. (Restricting solutions to nonnegative symetric matrices seems to be straightforward.)

Thanks in advance for any help or references!

• any reason why you can't add both constraints? – Aron Ahmadia Feb 21 '12 at 21:47
• @AronAhmadia: He can't add both constraints because that would be equivalent to $U_{i,j} \leq \min\{U_{i,k}, U_{k,j}\}$ for all $i, j, k$. I don't think there is an LP reformulation of this problem, but there could be an MILP reformulation, even though that likely makes it more expensive to solve. – Geoff Oxberry Feb 21 '12 at 22:15
• @N21: How big do you expect $n$ to be for the problems you want to solve? – Geoff Oxberry Feb 21 '12 at 22:15
• @Geoff: Thanks! I ultimately hope to have large $n$, but right now I am most concerned to get a preliminary solution with $n$ less than, say 100, or even 10. – N21 Feb 21 '12 at 23:23
• Thanks for clarifying @GeoffOxberry, I didn't fully think that through before posting. – Aron Ahmadia Feb 22 '12 at 6:13

## 6 Answers

Edit: Let's try this explanation again, this time when I'm more awake.

There are three big issues with the formulation (in order of severity):

1. There's no obvious reformulation of the problem that is obviously smooth, convex, or linear.
2. It's nonsmooth.
3. It's not necessarily convex.

## No obvious smooth/convex/linear reformulation

First off, there's no standard, obvious reformulation of each $\max$ constraint. Aron's suggestion applies to the more common $\min$ constraint, in which a constraint like $$U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\}$$ is replaced by the following two equivalent inequalities:$$U_{ij} \leq U_{ik}, \quad \forall k$$ $$U_{ij} \leq U_{kj}, \quad \forall k.$$ The reformulation isn't ideal, each $\min$ constraint has been replaced by $2n$ linear constraints, but it converts a nonsmooth nonlinear program into a linear program, which is orders of magnitude faster to solve.

Wolfgang points out that it might be possible (he doesn't include a proof) to reformulate the $\max$ constraints so that they are linear and smooth by adding slack variables. A slack variable needs to be added for each $\max$ constraint in the original formulation, which means that we're adding $n^2$ constraints in this reformulation. In addition, every $\max$ constraint is replaced by $2n$ (or so) linear constraints. The real killer is that the nonsmoothness is moved from the constraints to the objective, so Wolfgang's formulation still yields a nonsmooth nonlinear program.

There's no standard reformulation of $\max$ constraints in a minimization problem that I know of, having checked my linear programming textbook and having done a literature search. It doesn't mean that such a reformulation doesn't exist; it just means I haven't come across it. If I had to guess, I'd say an LP formulation doesn't exist.

## Nonsmoothness

In this context, nonsmoothness means that at least one of the functions in the formulation (the objective or the constraints) is not twice continuously differentiable. The nonsmooth functions in this formulation are the $\max$ functions.

Nonsmoothness is a huge problem because:

• it immediately makes your problem nonlinear
• most nonlinear programming solvers assume twice continuously differentiable functions

Since $\max$ functions aren't even once continuously differentiable, you can't even use traditional gradient descent methods without difficulty. Nonsmooth nonlinear programming algorithms are slower than their smooth counterparts.

## Possible nonconvexity

Your problem could be nonconvex, because in "standard form" for nonlinear programs (i.e., expressing all constraints in the form $\mathbf{g}(\mathbf{x}) \leq \mathbf{0}$), the troublesome constraints in your formulation are

$$U_{ij} - \max_{k}\{U_{ik}, U_{kj}\} \leq 0, \quad \forall i,j,k.$$

These functions are concave.

Proof: In this case, the functions $-U_{ij}$ and $\max_{k}\{U_{ik}, U_{kj}\}$ are both convex. The sum of convex functions is convex, and multiplying a convex function by -1 results in a concave function. (QED.)

As Tim points out, just because $\mathbf{g}$ is nonconvex doesn't mean that your problem is actually nonconvex, but if you're trying to solve an optimization problem to global optimality, you can only guarantee that a convex optimization solver will return a global optimum if your problem is convex. If you really want a global optimum, it would behoove you to determine if your feasible set is convex (or not). In the absence of such information, you have to assume that your problem might be nonconvex, and use algorithms that do not rely on convexity information. Even then, the nonsmoothness and lack of a good reformulation are much bigger issues.

## Options for solving the problem

• Settle for possibly finding a feasible solution. In this case, do what Aron said, and replace $$U_{ij} \leq \max_{k}\{U_{ik}, U_{kj}\} , \quad \forall i,j,k$$ with $$U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\} , \quad \forall i,j,k,$$ which can then be re-expressed as two separate inequalities using a standard LP reformulation. The resulting problem will be an LP restriction of the problem you want to solve; it should solve quickly relative to your original problem, and if it has a solution, that solution will be feasible for your original problem, and its objective function value will be a lower bound on the optimal objective function value of your original problem.

• Try your luck on your formulation as is with a bundle solver for nonsmooth programs. I don't have a lot of experience with these types of solvers. (A colleague of mine uses them in his research.) They are probably slow, since they can't use derivative information. (I think they use subgradient or Clarke's generalized gradient information instead.) It is also unlikely that you will be able to solve large problem instances with a bundle solver.

• Geoff, good stuff; this hits the key points and offers lots of constructive insight and suggestions. I voted it up. But you seem to be treating the nonconvexity as something separate from the fact that, as you put it, "there's no standard reformulation of max constraints in a minimization problem that I know of". But in fact, the former is precisely why the latter is not possible. Non-convex constraints cannot be expressed in linear programming---full stop! This is a non-convex problem, and it will either have to be reformulated as a mixed-integer problem or some other heuristic applied. – Michael Grant Mar 23 '13 at 3:24
• @MichaelGrant: I made that argument in revisions 1 and 2 over a year ago, and then got into a long comment thread about my assertion that the problem is nonconvex. (See Tim's answer below.) As I recall, at the time, Tim argued that an inequality $\mathbf{g}(x) \leq \mathbf{0}$ with $\mathbf{g}$ concave does not make a feasible set nonconvex. I am not sure why, because by definition, a convex program must be able to be expressed such that $\mathbf{g}(\mathbf{x}) \leq \mathbf{0}$ for $\mathbf{g}$ convex. I got tired of arguing with Tim about it; I should revert some of my previous edits. – Geoff Oxberry Mar 23 '13 at 16:21
• It is true that non-convex constraint functions can describe convex sets (indeed the notion of quasiconvexity covers most of these cases). But the fact is that $x \le \max\{y,z\}$ describes a non-convex set in $(x,y,z)$. So Tim's claim is irrelevant to this particular problem. It is also conceivable that the intersection of non-convex sets ends up being convex, but that's an unlikely occurrence. – Michael Grant Mar 23 '13 at 16:40
• Yes, you can prove that particular statement because such a set is the hypograph of $\max\{y,z\}$, and the set defined by the hypograph of a function is convex iff the function is concave. – Geoff Oxberry Mar 23 '13 at 16:46

The solution to your question is $-\infty$.

Let $$U=\left(\begin{matrix} 1&\cdots &1\\ \vdots & & \vdots\\1&\cdots&1\end{matrix}\right).$$ Since $A\cdot\mbox{vec}(U)$ and your constraints are linear in $U$, any positive multiple $t$ of $\pm U$ satisfies the constraints. Therefore, $\min_V(A\cdot\mbox{vec}(V)) \le min_{t}(A\cdot \mbox{vec}(tU))=-\infty$.

• Definitely a solution to the question as posed. My guess is that the OP is going to pose some nonnegativity constraint on $U$, in which case, the optimal objective function value may not be $-\infty$. – Geoff Oxberry Feb 24 '12 at 17:29
• @GeoffOxberry: True. Even with positivity constraints on $U$ the answer is $\le 0$. The form as posed implies that it's really a matrix optimization question a la $2\mbox{tr}(\hat{A}^\ast U)=\|\hat{A}-U\|^2-\|\hat{A}\|^2-\|U\|^2$. – Deathbreath Feb 24 '12 at 17:42

In order to formulate the constraints $f \le \max \{ f_1, f_2,...,f_n \}$, we create $n$ binary variables, $b_i \in \{0,1\}$, $1 \le i \le n$. Let $M$ be the bound of variable $f$, then we only need to add the following constraints:

1) $f \le f_i + (1-b_i) M, \forall i$

2) $\sum_i b_i = 1$

Normally, set $M := max_i f_i - min_i f_i$ if we can estimate the value of $f_i$.

Can't you introduce a slack variable? So to reformulate the constraint $$x_i <= \max(a_{i1}, a_{i2}, ..., a_{in})$$ write it as follows: $$x_i <= s_i$$ $$s_i >= a_{i1}$$ $$s_i >= a_{i2}$$ $$...$$ $$s_i >= a_{in}$$ This will have an infeasible solution with respect to the original problem if you choose s=infinity. But I'm pretty sure you can show that if you add a term $$c*\max(s_i-\max(a_i), 0)$$ to the objective function (i.e., you want to have $s_i-\max(a_i)$ as small as possible, preferably zero) and $c$ sufficiently large, then you'll get back a feasible solution if the original problem had feasible solutions with objective value less than infinity.

(A proof would go along the lines of showing that if $s_i>=\max(a_i)$ and if $x_i=s_i$, then the solution is infeasible; in other words, $s_i-\max(a_i)$ is a measure of infeasibility wrt to the original problem. If the problem is stable, there should be a finite improvement in objective function value for a finite violation of feasibility. If you choose c to be larger than the ratio between change in objective value and violation of feasibility, then the modified objective function would grow for problems that go into the infeasible region.)

• It's a good idea. Assuming your proof goes through, the issue then becomes moving the nonlinearity and nonsmoothness from the constraints into the objective, both of which are still undesirable qualities in a formulation. – Geoff Oxberry Feb 26 '12 at 5:36
• I'm afraid this will not work. If the $a_{ij}$ quantities are variables, not constants, then your original constraint is not a convex set in $(x_i,a_{i1},a_{i2},...,a_{in})$. Your reformulated set of constraints, on the other hand, is a convex set in $(x_i,s_i,a_{i1},a_{i2},...,a_{in})$. The two sets of constraints cannot be equivalent. – Michael Grant Mar 23 '13 at 3:12

I can't find the comment button...

As Geoff pointed out, it is a concave constraint function. However, it doesn't matter if the function itself is concave or not. Concave functions under linear constraints can be convex sets ( e.g. $$log(x)<5$$ ).

If it is a convex set, you could perform gradient descent on your objective function, using something like Dykstra's_projection_algorithm to project back onto the space of constraints.

• Upvoted for the comment about concave functions; I should've thought more about my explanation. Projecting onto the feasible set is a possibility, though I'm not sure off the top of my head if you could apply those algorithms with nonsmooth constraints. – Geoff Oxberry Feb 24 '12 at 21:44
• I'm not sure if they apply to non-smooth constraints. Also note, non-convex problems are only NP-hard if they have an NP number of possible solutions. If the number of possible solutions is in P, brute force exactly solves a non-convex optimization task. Lastly, the method cannot be formed as an LP, but this has nothing to do with the concave nature of the constraint. It's because the constraint is a non-linear function that also yeilds a non-linear (convex or not) constraint space. There are many convex constraints that also can't be solved using LPs. e.g. $x^2+y^2<5$ – Tim Feb 24 '12 at 22:21
• "Nonconvex problems are only NP-hard if they have an NP number of possible solutions." NP stands for "nondeterministic polynomial". I'm completely lost about what you're talking about. Secondly, I mentioned concavity because linear functions are concave and convex; the function isn't convex. Just because the function is nonsmooth and piecewise linear does not immediately exclude the possibility that an LP reformulation exists. – Geoff Oxberry Feb 24 '12 at 22:27
• For instance, $U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\}$ is "nonlinear" and can be reformulated as a pair of linear constraints, and thus, admits an LP reformulation. Finally, you're right, there are many constraints that can't be reformulated as linear constraints, such as smooth nonlinear constraints. – Geoff Oxberry Feb 24 '12 at 22:37
• Sorry, had to short-hand the comment, so I used NP for non-polynomial, and P for polynonomial. The point was that non-convex optimization isn't always NP-hard. It's only NP-hard if the number of possible solutions is WORSE than polynomnial. Sorry for the confusion :) You're right about the reformulating as linear. You seemed to say "Consequently, there is no way to reformulate your program as a linear program," because of the non-convexity, I was just noting that its not related to convexity but linearity. – Tim Feb 24 '12 at 22:43

Are there more inequality constraints not being mentioned? As stated, the problem is to minimize a linear function over a cone, so the optimal value is always either $-\infty$ or $0$.

Even with the constraint $U \ge 0$, the problem reduces to a discrete decision problem. Think of the linear function $A$ as corresponding to positive/negative weights of the edges of the complete graph on $n$ vertices. If there is a graph of diameter 2 connecting all the vertices with the sum of its weights strictly negative, then the optimal value is $-\infty$, otherwise the optimal value is $0$.

A quick sketch on how to prove this. First note that if $a \le b \le c$, then $c \le \max(a,b)$ implies $b=c$. So then the inequalities imply that for every triple $i,j,k$, exactly one of the following must be true:

1. $U_{ij} < U_{jk} = U_{ik}$
2. $U_{ik} < U_{jk} = U_{ij}$
3. $U_{jk} < U_{ik} = U_{ij}$
4. $U_{ij} = U_{jk} = U_{ik}$

So if you fix some threshold $t$ and form a graph $G(t)$ with an edge wherever $U_{ij}=t$, then every 3 vertices must have exactly 0,2, or 3 edges connecting them. So if $U_{ij}=U_{j k}=t$, then for every other vertex $\ell$, we must have either $U_{j \ell}=t$ or $U_{i\ell}=U_{k\ell}=t$. So if the graph $G(t)$ has any edges, it must be of diameter 2.