2
$\begingroup$

Consider the optimization problem:

\begin{equation} \begin{array}{l} \min_{(x,y)\in \mathbb{R}^2_{+}} \quad x_{1}a_{1} + x_2a_{2} \\ \text {subject to } \quad\; y_{2} \ge \frac{1}{{x}_2}, \\ \quad \quad \quad\quad \quad y_{1} \ge y_{2} + \frac{1}{{x}_1}, \\ \quad \quad \quad\quad \quad y_0 \ge y_{1}, \\ \quad \quad \quad\quad \quad a_0 \ge y_0, \end{array} \end{equation} where $x,y$ are positive variables and $a$ are non-negative constants.

Is it possible to solve the problem in a distributed manner through e.g., the ADMM algorithm? (note a distributed solution is useful since the original problem is high dimensional, has many more inequality constraints with the same structure, and includes additional separable equality constraints).

What I have tried: We can reformulate the problem with auxiliary variables $z_1 = y_1$ and $z_2 = y_2$, so that: \begin{equation} \begin{array}{l} \min_{x,y} \quad \quad \;\;x_{1}a_{1} + x_2a_{2} \\ \text {subject to } \quad\; y_{2} \ge \frac{1}{{x}_2}, \\ \quad \quad \quad\quad \quad y_{1} \ge z_{2} + \frac{1}{{x}_1}, \\ \quad \quad \quad\quad \quad y_0 \ge z_{1}, \\ \quad \quad \quad\quad \quad a_0 \ge y_0, \\ \quad \quad \quad\quad \quad y_2 = z_2, \\ \quad \quad \quad\quad \quad y_1 = z_1, \end{array} \end{equation}

Now the constraints are "separated" and we can have three sets of variables $(x_2,y_2)$, $(x_1,y_1,z_2)$, and $(y_0,z_1)$, with three corresponding sub-problems. Does it make sense to proceed this way?

I don't really know how to handle inequality constraints since it seems that ADMM is mainly tailored to affine equality constraints. Adding slack variables for any constraint doesn't really work since the inequality constraints are non-affine. This paper generalizes ADMM to non-linear inequality-constrained problems but it seems to complicate the derivation and potentially the solution to the local sub-problems.

Maybe ADMM is not really suited to solve this kind of problem. Any idea on better distributed methods better suited to solve it? I thought of Generalized Benders decomposition but I am not sure how to formulate the problem.

$\endgroup$
9
  • $\begingroup$ My 2 cents is from a user perspective: Most solvers can handle large scale optimization problems using interior points, dynamic column/row generation, automated Benders' etc. Still every other day research is going on to invent newer faster methods to handle high dimensionality. So I wouldn't bother much about a method unless it's commercialized or started to be used in practice. $\endgroup$ Feb 25, 2023 at 17:04
  • $\begingroup$ Thanks for your comment, but I do not understand what you mean. I tried to solve my problem with CVXPY and MOSEK and it takes days to solve since it has and an exponentially large number of variables and constraints. I need to parallelize in order to solve it faster. You say that there are solvers that do the parallelization automatically, but to my understanding you still need to formulate the problem properly, and check that the parallelization can be done, and that's what I am trying to do here. $\endgroup$
    – Apprentice
    Feb 25, 2023 at 19:07
  • $\begingroup$ @Apprentice, Why not try using the Lagrangian relaxation to find at least a $LB$ ( and if being lucky enough a good feasible solution) on the original problem? Also, maybe some other reformulation(!) like MISOCP would be helpful. $\endgroup$
    – A.Omidi
    Feb 26, 2023 at 8:55
  • 1
    $\begingroup$ It looks like your problem is $\min a^T x$ subject to ${\rm HARMONIC\_MEAN}(x) \geq a_0^{-1}$, is this correct? If so you don't need an exponential number of constraints. As shown in docs.mosek.com/modeling-cookbook/cqo.html#harmonic-mean, if you have $n$ variables, $x_1,\ldots,x_n$, you only need $1$ linear constraint and $n$ rotated quadratic cones. $\endgroup$ Feb 28, 2023 at 7:17
  • 2
    $\begingroup$ It is easy to formulate this class of optimization in cvxpy.org. You can also use Mosek directly. Also maybe if study the cookbook a bit you will learn something $\endgroup$ Mar 4, 2023 at 9:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.