1
$\begingroup$

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} According to this answer:

if all of the exponents are nonnegative, and $\sum_i a_{ik}\leq 1$ for each $k=1,2,\dots,K$, then this expression is concave.

Translating this statement, if $a_{ik} \geq 0$ for every $i$ and $k$, and if $\sum_{i=1}^{n} a_{ik} \leq 1$ for each $k$, then $f(x_1,\dots,x_n)$ is concave with respect to $x_1,\dots,x_n$. I'm trying to formally prove this statement, but I'm not sure how to complete the proof, so I would appreciate any suggestions on this.

We first rewrite $f$ as \begin{align} f(x_1,\dots,x_n) &= \sum_{k=1}^K c_k \cdot \prod_{i=1}^n x_i^{a_{ik}} \\ &= \sum_{k=1}^K c_k \cdot \prod_{i=1}^n \exp\left(\log\left(x_i^{a_{ik}}\right)\right) \\ &= \sum_{k=1}^K c_k \cdot \prod_{i=1}^n \exp\left(a_{ik}\log\left(x_i\right)\right) \\ &= \sum_{k=1}^K c_k \cdot \exp\left[\sum_{i=1}^n a_{ik}\log\left(x_i\right)\right] \\ &= \sum_{k=1}^K \exp(\log(c_k)) \cdot \exp\left[\sum_{i=1}^n a_{ik}\log\left(x_i\right)\right] \\ &= \sum_{k=1}^K \exp\left[\sum_{i=1}^n a_{ik}\log\left(x_i\right) + \log(c_k)\right] \\ &= \sum_{k=1}^K \exp\left[g_k(x_1,\dots,x_n)\right] \\ \end{align} where $g_k : \mathbb R^n \to \mathbb R$ is defined as $$ g_k(x_1,\dots,x_n) = \sum_{i=1}^n a_{ik}\log\left(x_i\right) + \log(c_k) $$ To show that $f$ is concave with respect to $x_1,\dots,x_n$, we proceed as follows. Given that $a_{ik} \geq 0$ for every $i$ and $k$ and $\sum_{i=1}^{n} a_{ik} \leq 1$ for each $k$, we want to show that, for each $k = 1,\dots,K$ and for every $t \in [0,1]$ and $x_1,\dots,x_n,y_1,\dots,y_n \in \mathbb R$, $$ \exp[g_k(tx_1 + (1-t)y_1,\dots,tx_n + (1-t)y_n)] \geq t\exp[g_k(x_1,\dots,x_n)] + (1-t)\exp[g_k(y_1,\dots,y_n)] $$ We attempt to do this as follows. Because each $\log\left(x_i\right)$ term is concave and monotone increasing in $x_i$, and because $a_{ik} \geq 0$ for each $i$ and $k$, then we can conclude that $g_k(x_1,\dots,x_n)$ is a concave and monotone increasing function of $x_1,\dots,x_n$. This means that, for every $t \in [0,1]$ and $x_1,\dots,x_n,y_1,\dots,y_n \in \mathbb R$, $$ g_k(tx_1 + (1-t)y_1,\dots,tx_n + (1-t)y_n) \geq tg_k(x_1,\dots,x_n) + (1-t)g_k(y_1,\dots,y_n) $$ Because the $\exp$ function is increasing, then $$ \exp[g_k(tx_1 + (1-t)y_1,\dots,tx_n + (1-t)y_n)] \geq \exp[tg_k(x_1,\dots,x_n) + (1-t)g_k(y_1,\dots,y_n)] $$ I'm not sure how to proceed beyond this point. Using the fact that the $\exp$ function is convex does not seem to be helpful here, as this only shows that $$ \exp[tg_k(x_1,\dots,x_n) + (1-t)g_k(y_1,\dots,y_n)] \leq t\exp[g_k(x_1,\dots,x_n)] + (1-t)\exp[g_k(y_1,\dots,y_n)] $$ I've not made use of the assumption that $\sum_{i=1}^{n} a_{ik} \leq 1$ for each $k$, so I think this should be used somehow.

$\endgroup$

1 Answer 1

1
$\begingroup$

Firstly, notice that we only need to show that $h(x) = \prod_{i=1}^n x_i^{\alpha_i}$ is concave, as $f$ is a positive linear combination of such functions. Also, for now, we will consider only $\alpha$ such that $\sum_{i=1}^n \alpha_i = 1$.

A useful technique for showing that multivariate functions are concave is to show that their restriction to any line is concave. In this case, this amounts to showing that, for each $x_0, v\in \mathbf{R}^n$ the univariate function $$ g(t) = h(x_0 + tv) = \exp\Bigl\{\sum_{i=1}^n \alpha_i \log(x_{0i} + t v_i)\Bigr\} $$ is concave in $t$.

Now, we can directly compute $$ g''(t) = g(t) \Bigl[ \Bigl(\sum_{i=1}^n \alpha_i \frac{v_i}{x_{0i} + t v_i}\Bigr)^2 - \sum_{i=1}^n \alpha_i \Bigl(\frac{v_i}{x_{0i} + t v_i}\Bigr)^2 \Bigr], $$ and notice that, since $\sum_{i=1}^n \alpha_i = 1$ and $y\mapsto y^2$ is convex, Jensen's inequality yields that, $$ \sum_{i=1}^n \alpha_i \Bigl(\frac{v_i}{x_{0i} + t v_i}\Bigr)^2 \geq \Bigl(\sum_{i=1}^n \alpha_i \frac{v_i}{x_{0i} + t v_i}\Bigr)^2. $$

Together with the fact that $g(t) \geq 0$, this is enough to show that $g''(t) \leq 0$, so that $g$ and thus $h$ is concave.

Now, for the $\sum_{i=1}^n \alpha_i \leq 1$ case, define $\tilde{h} \colon\mathbf{R}^{n+1} \rightarrow \mathbf{R}$ by $$ \tilde{h}(x) = \prod_{i=1}^n x_i^{\alpha_i} \cdot x_{n+1}^{1 - \sum_{i=1}^n \alpha_i}, $$ which is concave by our previous discussion, since its exponents add to $1$.

But then we have that $h(x) = \tilde{h}(x, 1)$, which is concave since it is the restriction of the concave function $\tilde{h}$ to the convex set $\{x \in \mathbf{R}^{n+1} : x_{n+1} = 1\}$.

$\endgroup$
6
  • $\begingroup$ Thank you very much for this answer. Just had a few questions: (1) Shouldn't you write "this is enough to show that $g''(t) \leq 0$,..." and not "this is enough to show that $g''(t) < 0$,..." since if $a \geq 0$ and $b \leq 0$, then $ab \leq 0$ and not $ab < 0$? Alternatively, you can say that $y \mapsto y^2$ is strictly convex and Jensen's inequality becomes a strict one. $\endgroup$
    – mhdadk
    Sep 11, 2023 at 18:53
  • $\begingroup$ (2) I lost you a bit when you wrote "Now, if we allow $\sum_{i=1}^n \alpha_i \leq 1$,..." I don't understand how writing $h$ the way that you did shows that it is still concave when $\sum_{i=1}^n \alpha_i \leq 1$, so I would appreciate any elaboration on this part. $\endgroup$
    – mhdadk
    Sep 11, 2023 at 19:00
  • 1
    $\begingroup$ Thanks for your comments! (1) was indeed an error on my part, and I have fixed it. We want the conclusion to be concavity rather than strict concavity, since $h(x) = x$ satisfies the hypotheses but isn't strictly concave. I've also added some text to clarify (2) - hopefully it's helpful! $\endgroup$ Sep 12, 2023 at 3:49
  • $\begingroup$ Thanks a lot for the edits. Much clearer now. Minor quibble at the end (emphasis mine): "...is the restriction of the concave function $\tilde{h}$ to the line $\{x \in \mathbf{R}^{n+1} : x_{n+1} = 1\}$." Isn't this set an $n$-dimensional subspace of $\mathbb R^{n+1}$ and not a 1D line? I would imagine the line you are referring to is the set (for a chosen $x$ and $v$ in $\mathbb R^{n+1}$) $\{(1-t)x + tv \mid x_{n+1}=v_{n+1}=1,t \in \mathbb R\}$. Of course, this doesn't change anything. $\endgroup$
    – mhdadk
    Sep 12, 2023 at 14:55
  • 1
    $\begingroup$ Whoops, that's right of course! The point is that that set it affine (not actually a subspace, since it doesn't contain the origin), and therefore convex. $\endgroup$ Sep 12, 2023 at 23:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .