# Is a posynomial concave under the following conditions?

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.

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\}$$.

• 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. Sep 11, 2023 at 18:53
• (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. Sep 11, 2023 at 19:00
• 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! Sep 12, 2023 at 3:49
• 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. Sep 12, 2023 at 14:55
• 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. Sep 12, 2023 at 23:36