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):
- There's no obvious reformulation of the problem that is obviously smooth, convex, or linear.
- It's nonsmooth.
- 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.