3
$\begingroup$

I have the following function in $p$ variables $y=\begin{bmatrix}y_1 & \dots & y_p \end{bmatrix}$:

$$ f(y) = \sum_{i=1}^p b_i \exp \left(\sum_{j \leq i} y_j \right) - \sum_{i=1} c_i y_i, $$

where the $b_i$ and $c_i$ are positive constants. I am trying to determine if this function is convex. In my attempt to do so I tried to see if the Hessian matrix is positive definite.

I found the $p \times p$-dimensional Hessian matrix as follows:

$$ H= \begin{bmatrix} a_1 + \dots + a_p & a_2 + \dots + a_p & \cdots & a_p \\ a_2 + \dots + a_p & a_2 + \dots + a_p & & \\ \vdots & & \ddots & \vdots \\ a_p & a_p & \dots & a_p \end{bmatrix}, $$

with $a_i=b_i \exp \left(\sum_{j \leq i} y_j \right)$, such that $a_p \geq a_{p-1} \geq \dots \geq a_1 > 0$. I feel like this matrix is positive definite, but am not sure how to show it. What I have tried so far is to see if $x^T H x > 0$. I have gotten to here so far:

$$ x^T A x = \sum_{i=1}^p \left(x_i^2 \sum_{j \geq i} a_j + x_i \sum_{j > i} x_j \sum_{k \geq j} a_k + x_i \sum_{j < i} x_j \sum_{k \geq i} a_k \right), $$

but am unsure how to continue from here.

$\endgroup$
  • $\begingroup$ The Hessian approach is pretty much the last way I'd consider proving convexity here. Rather I'd use a combination of rules, such as those outlined in Boyd & Vandenberghe, to show this is convex via a combination of composition rules. $\endgroup$ – Michael Grant Jun 21 '17 at 0:05
2
$\begingroup$

Let $v\in\mathbb{R}^p$ be a fixed vector. For $y\in\mathbb{R}^p$, let $\langle y,v\rangle$ denote the standard inner product. The function $h_v:\mathbb{R}^p\to\mathbb{R}$ defined by

$$h_v(y)=\exp(\langle y,v\rangle )$$ is convex, because $e^t$ is convex. Indeed, if $0\leq\lambda\leq 1$, then for every $y_1,y_2\in\mathbb{R}^p$:

$$ h_v(\lambda y_1+(1-\lambda)y_2)=e^{\lambda\langle y_1,v\rangle+(1-\lambda)\langle y_2,v\rangle}\leq \lambda e^{\langle y_1,v\rangle}+(1-\lambda)e^{\langle y_2,v\rangle}=\lambda h_v(y_1)+(1-\lambda)h_v(y_2) $$ by the convexity of $e^t$. For $1\leq k\leq p$, let $e_k$ denote the standard unit vectors in $\mathbb{R}^p$. Put $$v_k=\sum_{i=1}^ke_i$$ Given positive numbers $b_i$, the functions $b_i h_{v_i}$ are convex for each $i$, and so also their sum. Note that $$F(y)=\sum_{i=1}^pb_i\exp(\sum_{j\leq i}y_j)=\sum_{i=1}^p b_i h_{v_i}(y)$$ So $F$ is a convex function. Observe that the Hessian of $F$ coincides with with the Hessian of the given function $f$. Therefore, the function $f$ is also convex.

It can be shown that if $H_y$ is the Hessian of $f$ (or of $F$) evaluated at some point $y\in\mathbb{R}^p$ then

$$\langle H_y v,v\rangle=\exp(-\sum_{i=1}^py_i)\sum_{j=1}^pb_j\exp(\sum_{2\leq i\leq j}x_i)\left(\sum_{i=1}^jv_i\right)^2$$ which is seen to be positive for $v\neq 0$, but it is much easier to prove that $F$ is convex as above.

$\endgroup$

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.