# Is this problem convex?

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? • 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)$? Apr 18, 2021 at 2:20 • @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. Apr 18, 2021 at 3:17 • @LinAlg Actually$\sum_i bi$is constant so after removing that the objective is convex. For the constraint Im not sure though Apr 18, 2021 at 3:25 • @LinAlg To check the convexity of the constraint$f(x) = 0$, is that equivalent to checking if$f(x)$is convex? Apr 19, 2021 at 0:39 •$f(x)=0$is convex only if$f$is linear;$f(x)\leq 0$is convex if$f$is convex Apr 19, 2021 at 1:05 ## 1 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) • Thank you. Why is the last constraint non-convex? Both sides of the equality are convex right? Apr 18, 2021 at 17:27 • 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)? Apr 18, 2021 at 18:10 • 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? Apr 19, 2021 at 0:37 • 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... Apr 19, 2021 at 5:35
• 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? Apr 19, 2021 at 16:08