I am a network engineer who is studying some optimization problems in the field of communication theory mostly for pleasure. Out of pure curiosity, I see that there is some optimization problem in which this logarithmic constraint appear $y\log \left( {1 + \frac{x}{y}} \right) \ge t \Leftrightarrow x + y \ge y{e^{\frac{t}{y}}}$
It seems that this constraint can be turned into some sort of things is called as exponential cone.
The exponential cone object is defined as follow:
$K_{exp} = {( (x_1, x_2, x_3) : x_1 \geq x_2 e^{x_3/x_2}, x_2 > 0 )} ∪ {( (x_1, 0, x_3) : x_1 \geq 0, x_3 \leq 0 )}.$
A little bit search on google schorlar return a lot of results but due to my limited knowledge of convex analysis I do not understand what is really nice about these "exponential cone" object.
Therefore, my question is "What kind of interesting properties that make exponential cone attractive for convex optimization ?"
Since this question is quite broad I hope that you could as least show some criteria for example: presentability, or maybe it make the interior point method converge faster, etc…
Would you kindly help me with this ?
Thank you for your enthusiasm
Best Answer
Mathematical attractiveness:
A main difference of power and exponential cones, in comparison with positive orthant, Lorentz, or semidefinite cones, is that they are not symmetric, which makes them more attractive for researchers.
Theoretical attractiveness:
From a theoretical point of view, optimization problems with exponential cones can be solved (finding an $\epsilon$-optimal solution for any $\epsilon>0$) in polynomial time using the barrier interior-point method when the barrier function is $\phi(t)=-\log t$ (see Section 11.5 of [1]) In fact, it can be shown that
$$- \log g_1(x,y,z)- \log g_2(x,y,z)- \log g_3(x,y,z) \\ = -\log (y \log(z/y) - x) - \log y - \log z$$
is a self-concordant function [2] where $g_1(x,y,z)$, $g_2(x,y,z)$, and $g_3(x,y,z)$ define the exponential cone as follows:
$$\mathcal K_{\text{exp}}=\{ (x,y,z) \in \mathbb R^3 \mid ye^{x/y} \leq z, y > 0 \} \\= \{ (x,y,z) \in \mathbb R^3 \mid g_1(x,y,z)=y \log(z/y) - x \ge 0, g_2(x,y,z)=y>0,g_3(x,y,z)=z>0 \}.$$
Computational attractiveness:
Moreover, efficient primal-dual interior point algorithms have been recently developed and made available in cvx and mosek for solving such problems, which have been successful and more efficient compared to the barrier method in practice; see this paper [3].
Application attractiveness:
Due to the recent computational progress and availability of solvers, several studies have recently reformulated new or old optimization problems as exponential cone optimization models, which can be solved more efficiently or more easily using the existing solvers instead of implementing specialized algorithms. A nice new one is the reformulation of Lambert function as cone optimization model, mentioned in a comment by @JeanMarie. Another example is the reformulation of portfolio optimization with Entropic Value-at-Risk as an exponential conic model given in [5], whereas the problem has been convexified and solved earlier by specialized convex optimization methods in [6].
More details:
Consider the following optimization model:
$$\min \quad f_0(x) \\ \text{s.t.:}\, Ax=b, \, f_i(x)\le 0,\, i=1,\dots,m, \tag{1}$$
which is assumed to have an optimal solution $x^*$ and a strict feasible solution $x_0$, i.e., $Ax_0=b \, f_i(x_0)< 0,\, i=1,\dots,m$.
Assume that both functions $f_0$ and $ \phi(x)$, defined below:
$$ \phi(x)= -\sum_{i=1}^m \log (-f_i(x)), \tag{2}$$
are self-concordant. Then, from the key result presented in Section 11.5 of [1], it is known that there is a barrier interior-point algorithm that can find an $\epsilon$-optimal solution $x^*_\epsilon$, i.e., $f(x^*_\epsilon)-f(x^*)< \epsilon$ such that the number of its iterations is order of $O\left (\log\frac 1\epsilon \, \sqrt{m} \right).$
Now consider the following exponential cone programming model:
$$\min \quad f_0(x) \\ \text{s.t.:}\, Ax=b, \\ w=Bx \in\prod_{i=1}^{k} \mathcal K_{\text{exp}, i}, w \in \mathbb R^{3k} \tag{3}$$
where each $\mathcal K_{\text{exp}, i}$ is an exponential cone: $$\mathcal K_{\text{exp}}=\{ (w_i,w_{i+1},w_{i+2}) \in \mathbb R^3 \mid w_{i+1} e^{w_{i+2}/w_{i+1}} \leq w_{i}, w_{i+1} > 0 \}.$$
Model (3) can be rewritten as
$$\min \quad f_0(x) \\ \text{s.t.:}\, Ax=b, w=Bx \\ f_i(w_i,w_{i+1},w_{i+2})=-w_{i+1} \log(w_{i+2}/w_{i+1}) + w_{i} \le 0,\\ g_i(w_i,w_{i+1},w_{i+2})=-w_{i+1}<0,h_i(w_i,w_{i+1},w_{i+2})=-w_{i+2}<0, \, i=1,\dots,k.$$
This model is of the initial form (1) given above with $m=3k$. So we can apply the barrier algorithm. Fortunately, it is also known that for each $i \in [k]$
$$- \log (- f_i(w_i,w_{i+1},w_{i+2}))- \log (- g_i(w_i,w_{i+1},w_{i+2}))- \log (- h_i(w_i,w_{i+1},w_{i+2}))$$
is a self-concordant function. Hence, function $\phi$ defined earlier in (2) for this model is also self-concordant. Finally, when $f_0$ is self-concordant and $x_0$ and $x^*$ exist, any $\epsilon$-optimal of the the above reformulation of the exponential cone programming model can be obtained in $O\left (\log\frac 1\epsilon \, \sqrt{3k} \right)=O\left (\log\frac 1\epsilon \, \sqrt{k} \right)$ iterations.