4
$\begingroup$

I am trying to find a DCP formulation for the following convex objective function (using CVXPY):

Let $x$ be the $N$-dimensional vector variable on which we optimize on, $c$ be a known scalar value such that $0 < c \le 1$ and and $L$ be a known $N$-dimensional vector with $L_i > 0 \: \forall i=1,..., N$. The (convex) objective is formulated as:

$$ f(x) = \sum_{i=1}^N\left(c^{\max(x_i,0)/L_i}\cdot L_i - \ln(c)\cdot\max(x_i,0)\right) $$

Single out any $i=1,...,N$, the issue I am facing is that each convex element of the sum above is given by the sum of a nonconvex and a convex function:

$$ c^{\max(x_i,0)/L}\cdot L_i - \ln(c)\cdot\max(x_i,0) $$

The expected behavior of the above sum is to be equal to: \begin{align} c^{\max(x_i,0)/L}\cdot L_i - \ln(c)\cdot\max(x_i,0)=\begin{cases} c^{x_i/L}\cdot L_i - \ln(c)\cdot x&\quad x_i \ge 0 \\ L_i &\quad x_i < 0 \end{cases} \end{align}

But using standard atoms it is not trivial to provide a DCP certificate for the above due to non-convexity of the first term.

Do you have any ideas/suggestions on how one could rewrite the problem and make it DCP compliant?

$\endgroup$
4
  • $\begingroup$ Which of x,L,c are optimization variables, and which are input data? $\endgroup$ Oct 29, 2021 at 11:40
  • $\begingroup$ @MarkL.Stone added more color in the corpus of the question. Answering your question: x is the variable on which we optimize on. L and c are known scalar vector and value, respectively. $\endgroup$
    – LowOdds
    Oct 29, 2021 at 12:34
  • $\begingroup$ I think this is convex, but haven't proven it. The scalar case should suffice. In any event, this could be a candidate for @ErlingMOSEK 's challenge twitter.com/J_P_Vielma/status/1014513695605608448 as a (possible example of) convex expression which can't be modeled by (extreme) DCP. But, maybe one of the clever MOSEK people can come up with a DCP formulation (perhaps some way of effectively combining the two terms) $\endgroup$ Oct 29, 2021 at 15:20
  • $\begingroup$ Do you have a convexity proof? if so, it might be helpful to show it. If the proof is "constructive" (in a DCP building block kind of way), that would be even better. $\endgroup$ Oct 29, 2021 at 15:37

1 Answer 1

2
$\begingroup$

For all $c>0$ the function of one variable $$g(x)=c^{x/L}\cdot L - \ln(c)\cdot x=\exp(\ln(c)x/L)\cdot L-\ln(c)\cdot x$$ is convex increasing on $x\geq 0$ (derivative check) and DCP representable (verbatim). So we can model your extension to all real numbers via

$$u\geq \max(x,0),$$ $$t\geq g(u).$$

Now if $x\geq 0$ then we have $t\geq g(x)$ and if $x\leq 0$ then we have $t\geq g(0)=L$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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