0
$\begingroup$

Is there a way to convert a product of a convex and a log-convex function to the DCP ruleset? Specifically, I am interested in the following functions of ${\textbf{x}}$ where ${\textbf{x}}$ and ${\textbf{y}}$ are in $\mathbb{R}^d$:

$$ {{||{\textbf{y} - \textbf{x}}||}^{p}}{\exp\left( ||{\textbf{y} - \textbf{x}}||\right)} $$

Does there exist a simple transformation to convert this expression to a DCP for implementation in CVX in MATLAB?

As an example, I have the following problem:

$$ \text{minimize} \quad \sum_{i=1}^N {{||{\textbf{y}_i - \textbf{x}}||}^{p}}{\exp\left( ||{\textbf{y}_i - \textbf{x}}||\right)} \\ s.t. \quad {{||{\textbf{y}_i - \textbf{x}}||}^{p}}{\exp\left( ||{\textbf{y}_i - \textbf{x}}||\right)} \leq \epsilon, \quad \forall i \\ \textbf{x} \in \mathcal{A} $$ where $\mathcal{A}$ is a convex set. Assume $\textbf{y}_i, \textbf{x} \in \mathbb{R}^2$. Furthermore, $p \in \mathbb{R}^+$.

$\endgroup$
  • $\begingroup$ How does this expression appear in your problem? Is it the objective function? $\endgroup$ – LinAlg Jul 3 '18 at 0:42
  • $\begingroup$ @LinAlg, Thanks for your comment. I have this expression in both the objective function and the constraints. I have edited the question to give an example of this problem. $\endgroup$ – Gourab Ghatak Jul 3 '18 at 6:35
  • $\begingroup$ There is one thing I am missing. In any DCP rule set you have atomic functions you are allowed to use. Is $x \exp(x)$ on $x\geq 0$ one of your atomic functions? In addition, what do you know about $p$? $\endgroup$ – Alex Shtof Jul 3 '18 at 8:45
  • $\begingroup$ @Alex:Thanks for your comment. In my problem, I have $p \in \mathbb{R}^+$. Furthermore, I don't think $\textbf{x}\exp(\textbf{x})$ is an atomic function, otherwise it would have been simpler I guess, to solve the problem. I might be wrong, in which case, I would be grateful if someone can point out if there is an atomic function that can be utilized here. $\endgroup$ – Gourab Ghatak Jul 3 '18 at 8:55
  • $\begingroup$ As a simple case, let us assume p = 2. $\endgroup$ – Gourab Ghatak Jul 3 '18 at 8:56
1
$\begingroup$

Ok. I assume that $p \geq 1$, and I also assume that you have $x \log(x)$ and $-\log(x)$ as atoms in your DCP rule-set. CVX allows you to use them, although it only guarantees an approximation.

First, note that $\phi(t) = t^p \exp(t)$ is increasing on $t \geq 0$. Thus, we can reformulate the problem as follows over the variables $\mathbf{x}, \mathbf{y_i}, \mathbf{s}, \mathbf{t}, \mathbf{r}$: $$ \begin{aligned} \text{minimize} &\quad \sum_{i=1}^n s_i \\ \text{s.t.} &\quad t_i^p \exp(t_i) \leq s_i & \forall i \\ &\quad \|\mathbf{y}_i - \mathbf{x}\| \leq t_i &\forall i \\ &\quad r_i^p \exp(r_i) \leq \epsilon & \forall i \\ &\quad \|\mathbf{y}_i - \mathbf{x}\| \leq r_i &\forall i \\ &\quad \mathbf{x} \in \mathcal{A} \\ &\quad \mathbf{t}, \mathbf{s}, \mathbf{r} \geq 0 \end{aligned} $$ Now, note that $t^p \exp(t) \leq s$ if and only if $t \exp(t/p) \leq s^{1/p}$. Substituting $u_i = \exp(t_i / p),~ w_i = \exp(r_i / p)$ we obtain the following equivalent problem: $$ \begin{aligned} \text{minimize} &\quad \sum_{i=1}^n s_i \\ \text{s.t.} &\quad p u_i \log(u_i) - s_i^{1/p} \leq 0& \forall i \\ &\quad \|\mathbf{y}_i - \mathbf{x}\| -p \log(u_i) \leq 0 &\forall i \\ &\quad p w_i \log(w_i) - \epsilon^{1/p} \leq 0 & \forall i \\ &\quad \|\mathbf{y}_i - \mathbf{x}\| -p \log(w_i) \leq 0 &\forall i \\ &\quad \mathbf{x} \in \mathcal{A} \\ &\quad \mathbf{s} \geq 0 \\ &\quad \mathbf{u}, \mathbf{w} \geq 1 \end{aligned} $$ This problem can be built from the DCP rule-set with the additional aproximate atoms.

$\endgroup$
  • $\begingroup$ This looks perfect. I think with these transformations, the final problem is compliant with DCP ruleset. $\textbf{x}\log\textbf{x}$ can be implemented using the function "entr" representing entropy in DCP. Thanks. $\endgroup$ – Gourab Ghatak Jul 4 '18 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.