3
$\begingroup$

Note: this question was already posted on Math.SE but received no answers, so I'm re-posting it here for better reach.


Consider the following posynomial with respect to the variables $x_1,\dots,x_n$: $$ \begin{align} f(x_1,\dots,x_n) &= \sum_{k=1}^K c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}} \\ &= \sum_{k=1}^K c_k \cdot \prod_{i=1}^n x_i^{a_{ik}} \end{align} $$ Using the change of variables $\tilde x_i = \log x_i$, such that $x_i = e^{\tilde x_i}$, we get the following expression $$ \begin{align} f(\tilde x_1,\dots,\tilde x_n) &= \sum_{k=1}^K c_k \cdot \prod_{i=1}^n e^{\tilde x_i a_{ik}} \\ &= \sum_{k=1}^K c_k \cdot \exp\left[\sum_{i=1}^n \tilde x_i a_{ik}\right] \\ &= \sum_{k=1}^K \exp(\log(c_k)) \cdot \exp\left[\sum_{i=1}^n \tilde x_i a_{ik}\right] \\ &= \sum_{k=1}^K \exp\left[\sum_{i=1}^n \tilde x_i a_{ik} + \log(c_k)\right] \end{align} $$ This expression is convex with respect to $\tilde x_1,\dots,\tilde x_n$ (see here for a proof). My question is: does there exist a similar change of variables such that the resulting expression is concave (not convex) with respect to $\tilde x_1,\dots,\tilde x_n$? That is, does there exist functions $g_1,\dots,g_n$ such that $f(\tilde x_1,\dots,\tilde x_n)$, where $\tilde x_i = g_i(x_i)$, is concave with respect to $\tilde x_1,\dots,\tilde x_n$?

$\endgroup$
1
  • $\begingroup$ I see you implicitly assume $c_k > 0 \;\forall k$ and $x_i > 0 \;\forall i$. $\endgroup$ Sep 19, 2023 at 7:34

1 Answer 1

3
$\begingroup$

You implicitly assume $c_k > 0$ for all $k$, and $x_i > 0$ for all $i$, and I will do the same. Using the change of variables $\tilde x_i = x_i^M$, such that $x_i = \tilde x_i^{1/M}$, for a big constant $M$ at least the size of the largest monomial degree, $\max_k \left(\sum_{i=1}^n \alpha_{ik}\right)$, we get the following expression $$ \begin{align} f(\tilde x_1,\dots,\tilde x_n) &= \sum_{k=1}^K c_k \cdot \prod_{i=1}^n {\tilde x_i^{a_{ik}/M}}, \\ \end{align} $$ which is a sum of monomials of degree $p_k = \sum_i \frac{a_{ik}}{M} \leq 1$ known to be concave and representable by a power cone in conic optimization; see here for homogenous case $p_k=1$, and here for the nonhomogenous case $p_k<1$. The expression above is thus concave with respect to $\tilde x_1,\dots,\tilde x_n$.

$\endgroup$
4
  • $\begingroup$ Very clever. Thank you for this answer. $\endgroup$
    – mhdadk
    Sep 20, 2023 at 16:50
  • $\begingroup$ Just wondering, do you know if there is a similar change of variables such that the function $$h(x,y) = \prod_{i=1}^n x_i^{z_i} \cdot y_i^{1-z_i}$$ where $x,y \in \mathbb R_+^n$ and $h(x,y)$ is a monomial in $(x,y)$, is concave in $(x,y)$? That is, does there exist $\tilde x = g_1(x)$ and $\tilde y = g_2(y)$ such that $h(\tilde x,\tilde y)$ is concave? You can further assume that $z_i \in [0,1]$ and $x_i,y_i \in [0,1]$ if it makes things easier. I can also post this as a separate question if you prefer. $\endgroup$
    – mhdadk
    Sep 20, 2023 at 23:30
  • 1
    $\begingroup$ If $z_i$ are constant isn't this just a special case of the above with K=1 where the monomial degree is (z1 + (1-z1) + z2 + (1-z2) + ...) = n? If in doubt, create a separate question yes. $\endgroup$ Sep 21, 2023 at 10:54
  • $\begingroup$ Ahh yes! Don't know why I didn't see that. Thanks again. $\endgroup$
    – mhdadk
    Sep 21, 2023 at 12:32

Your Answer

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

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