0
$\begingroup$

I'm trying to solve the following max-flow type problem using convex optimization.

I have $n$ nodes which each have an input currency $u_i$ and output currency $v_i$. My decision variables are $x_i$ which is the amount of currency inputed to node $i$. If $x_i$ of currency $u_i$ flows into node $i$ then $b_i - (a_i b_i) / (a_i+x_i)$ of currency $v_i$ flow outs.

I would like to maximize the total output in some currency, e.g. dollars:

Maximize: $\sum_i b_i - (a_i b_i) / (x_i a_i)$, only where $v_i$ is the target currency e.g. $

Constraints:

  • $\sum_i x_i = c$ where $u_i = £$. (Total input in some currency e.g. £ is $c$)

  • $x_i \geq 0$: (Flow is non-negative)

  • $\sum_i x_i = \sum_j (b_j - (a_j b_j) / (a_j + x_j)$ only where $u_i = v_j$ (Flow is conserved, except source and target currencies)

And $a_i$, $b_i$ and $c$ are positive constants.

I understand how to solve this as an LP if the flow out of a node was just $x_i$ but in this case I would like to understand three things about this problem:

  • What are the steps to convert this to an SOCP so that I can solve it with a convex optimization library?
  • If the objective function convex
  • Are the constraints convex?
$\endgroup$
6
  • $\begingroup$ what do you think about the convexity of the constraint $\sum_i x_i = \sum_j b_j - (a_j b_j) / (a_j + x_j)$? $\endgroup$
    – LinAlg
    Apr 18, 2021 at 2:20
  • $\begingroup$ @LinAlg I feel that the epigraph of $b-ab/(a+x)$ shows that that is not convex so I'm assuming the sum is not convex either. $\endgroup$ Apr 18, 2021 at 3:17
  • $\begingroup$ @LinAlg Actually $\sum_i bi$ is constant so after removing that the objective is convex. For the constraint Im not sure though $\endgroup$ Apr 18, 2021 at 3:25
  • $\begingroup$ @LinAlg To check the convexity of the constraint $f(x) = 0$, is that equivalent to checking if $f(x)$ is convex? $\endgroup$ Apr 19, 2021 at 0:39
  • $\begingroup$ $f(x)=0$ is convex only if $f$ is linear; $f(x)\leq 0$ is convex if $f$ is convex $\endgroup$
    – LinAlg
    Apr 19, 2021 at 1:05

1 Answer 1

1
$\begingroup$

Convexity (and SOCP-representability) has already been answered in your other post How can I solve this form of optimization problem?.

To obtain an SOCP representation of the objective, you use the fact that minimizing a term $\frac{1}{z}$ can be done by introducing an epigraph variable $t$ to use in the objective and add constraint $\frac{1}{z}\leq t$ which is written as $1 \leq zt$ which is socp-representable as $\left\lVert \begin{matrix}2\\z-t\end{matrix}\right\rVert\leq z+t$. This is repeated on all fractions in the objective.

The last equality is nonlinear, hence nonconvex and definitely not SOCP-representable (unless the equality can be relaxed to $\leq$ which would allow you to use same strategy as objective, but a quick analysis indicates to me that would possibly decrease the objective, and thus not possible)

$\endgroup$
6
  • $\begingroup$ Thank you. Why is the last constraint non-convex? Both sides of the equality are convex right? $\endgroup$ Apr 18, 2021 at 17:27
  • $\begingroup$ Take a pen and paper. Draw any curve (i.e. the feasible set to an equality). Which forms can this curve have so that if a point p1 is on the curve, p2 is on the curve, all points between p1 and p2 are on the curve (i.e. for the feasible set to be convex)? $\endgroup$ Apr 18, 2021 at 18:10
  • $\begingroup$ Hmmm, I understand checking if a set is convex, or a function (using the epigraph). But I don't think I'm clear on how to check if a constraint is convex. This plot looks OK to me dropbox.com/s/fagfqkfe2bg4edz/… It's a plot of $x1 - b2 - (a2*b2)/(a2 + x2)$ for a fixed $a2$ and $b2$ or did you mean something else? $\endgroup$ Apr 19, 2021 at 0:37
  • $\begingroup$ I don't know what that picture is supposed to show. Equality $f(x,y)=0$ is curve in 2d. Draw for instance $x^2 + y^2 =1$, and now take any two points on the feasible set (the circle) and judge if all points in-between also are on the circle... $\endgroup$ Apr 19, 2021 at 5:35
  • $\begingroup$ Thanks I see that convex equality constraints need to be linear. So I guess the constraints prevent this being solved using SOCP. Given this constraint can YALMIP still solve it? $\endgroup$ Apr 19, 2021 at 16:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .