Author: Umberto Natale, [email protected]
The problem of finding the optimal routing solution and the existence of arbitrage opportunities can be framed as a convex optimization problem. In order to understand where this formulation comes from, it is necessary to give some definitions, see Angeris et al 2021a, Boyd et al for a deeper overview of the topic.
Definition 1.1: Convex set - *Given a vector space $V$, a subset $C$ of $V$ is a convex ***set if, for all $x$ and $y$ in $C$, the segment connecting $x$ and $y$ is included in $C$.
Definition 1.2: Convex function - A function $f$ defined on a set $D$, subset of $n$-dimensional real numbers, with real values if
$$ \begin{align} & f: D\to \mathbb{R},\quad D\subseteq\mathbb{R}^n\\ & f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y), \quad \forall x,y \in D, \,\,\,\,\,\,\, 0\le\theta\le 1\,.\end{align} $$
If $f$ is differentiable we can characterize the convexity property as
$$ \begin{equation} f(z)\ge f(x)+\nabla f(x)^\top(z-x)\,,\end{equation} $$
this for all $x\,,y$ in $D$. Since if $f$ is convex, $-f$ is concave, it immediately follows that for a differentiable function
$$ \begin{equation}f(x)\le f(z)+\nabla f(z)^\top(x-z)\,.\end{equation} $$
By adding Eq. (3) and Eq. (4) we obtain the following relation for a concave function
$$ \begin{equation}\left(\nabla f(x)-\nabla f(z)\right)^\top(x-z)\le0\,.\end{equation} $$
Thus, from Eq. (4) we have that the Taylor approximation is a global upper bound on the concave function, and from Eq. (5) we have that for a concave function its gradient is a monotone operator.
With these definitions we can define the convex optimization problem.
Definition 1.3: Convex optimization - A convex optimization problem as the for
$$ \begin{align} &\textrm{minimize}\,\,\,\,\,\,\,\,\,f_0(x)\\ &\textrm{subject to}\,\,\,\,\,\,\,f_i(x)\le0\,,\,\,\,\,i=1,\ldots,m\\ &\qquad\qquad \,\,\,\,\,\,\,\,\, g_i(x)=0\,,\,\,\,i=1,\ldots,p\,. \end{align} $$
This describes the problem of finding an $x$ that minimizes Eq. (6) among all $x$ that satisfy the condition defined in Eqs. (7) and (8). Here $f$ is a convex function. The function in Eqs. (7) and (8) are called, respectively, inequality constraint and equality constraint functions.
Since $f$ is convex, we can rephrase the previous problem for concave function as
$$ \begin{align}&\textrm{maximize}\,\,\,\,\,\,\,f_0(x)\\&\textrm{subject to}\,\,\,\,\,\,\,f_i(x)\ge0\,,\,\,\,\,i=1,\ldots,m\\&\qquad\qquad \,\,\,\,\,\,\,\, g_i(x)=0\,,\,\,\,i=1,\ldots,p\,.\end{align} $$