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?
Best Answer
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)