4 Completely redid the explanation so that it's more accurate, and so I look like less of an ass.
source | link

SoEdit: Let's try this explanation again, upon further thoughtthis 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, yourthere'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

There isn't any apparent way to reformulate theAs Tim points out, just because $\mathbf{g}$ is nonconvex doesn't mean that your problem asis actually nonconvex, but if you're trying to solve an LPoptimization problem to global optimality, and it's not clearyou can only guarantee that the feasible regiona convex optimization solver will return a global optimum if your problem is convex. Nonconvex programs are NP-hardIf you really want a global optimum, so thereit would behoove you to determine if your feasible set is no "efficient" algorithm for solving such problems for large enough $N$, whereconvex $N$ is(or not). In the numberabsence of decision variables in your program (insuch information, you have to assume that your caseproblem might be nonconvex, $N = n^2$)and use algorithms that do not rely on convexity information.

Your troublesome constraints are also non-smooth Even then, because they involvethe nonsmoothness and lack of a $\max$ functiongood reformulation are much bigger issues. You have a couple options:

Options for solving the problem

So, upon further thought, 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

There isn't any apparent way to reformulate the problem as an LP, and it's not clear that the feasible region is convex. Nonconvex programs are NP-hard, so there is no "efficient" algorithm for solving such problems for large enough $N$, where $N$ is the number of decision variables in your program (in your case, $N = n^2$).

Your troublesome constraints are also non-smooth, because they involve a $\max$ function. You have a couple options:

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

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

3 More clarification and minor corrections.
source | link

So, upon further thought, your problem iscould 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 constraintsfunctions 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.)

Consequently, there is noThere isn't any apparent way to reformulate your programthe problem as a linear programan LP, and it's probably not aclear that the feasible region is convex program. Nonconvex programs are NP-hard, so there is no "efficient" algorithm for solving such problems for large enough $N$, where $N$ is the number of decision variables in your program (in your case, $N = n^2$).

Your troublesome constraints are also non-smooth, because they involve a $\max$ function. You have a couple options:

  • 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.

Sorry to be the bearer of bad news; I hope this helps.

So, upon further thought, your problem is 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 constraints 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.)

Consequently, there is no way to reformulate your program as a linear program, and it's probably not a convex program. Nonconvex programs are NP-hard, so there is no "efficient" algorithm for solving such problems for large enough $N$, where $N$ is the number of decision variables in your program (in your case, $N = n^2$).

Your troublesome constraints are also non-smooth, because they involve a $\max$ function. You have a couple options:

  • 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.

Sorry to be the bearer of bad news; I hope this helps.

So, upon further thought, 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.)

There isn't any apparent way to reformulate the problem as an LP, and it's not clear that the feasible region is convex. Nonconvex programs are NP-hard, so there is no "efficient" algorithm for solving such problems for large enough $N$, where $N$ is the number of decision variables in your program (in your case, $N = n^2$).

Your troublesome constraints are also non-smooth, because they involve a $\max$ function. You have a couple options:

  • 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.

2 Weakened statement about convexity in light of Tim's answer.
source | link

So, upon further thought, your problem is 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 constraints 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.)

Consequently, there is no way to reformulate your program as a linear program (or even as, and it's probably not a convex program). Nonconvex programs are NP-hard, so there is no "efficient" algorithm for solving such problems for large enough $N$, where $N$ is the number of decision variables in your program (in your case, $N = n^2$).

Your troublesome constraints are also non-smooth, because they involve a $\max$ function. You have a couple options:

  • 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.

Sorry to be the bearer of bad news; I hope this helps.

So, upon further thought, your problem is 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 constraints 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.)

Consequently, there is no way to reformulate your program as a linear program (or even as a convex program). Nonconvex programs are NP-hard, so there is no "efficient" algorithm for solving such problems for large enough $N$, where $N$ is the number of decision variables in your program (in your case, $N = n^2$).

Your troublesome constraints are also non-smooth, because they involve a $\max$ function. You have a couple options:

  • 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.

Sorry to be the bearer of bad news; I hope this helps.

So, upon further thought, your problem is 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 constraints 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.)

Consequently, there is no way to reformulate your program as a linear program, and it's probably not a convex program. Nonconvex programs are NP-hard, so there is no "efficient" algorithm for solving such problems for large enough $N$, where $N$ is the number of decision variables in your program (in your case, $N = n^2$).

Your troublesome constraints are also non-smooth, because they involve a $\max$ function. You have a couple options:

  • 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.

Sorry to be the bearer of bad news; I hope this helps.

1
source | link