8
$\begingroup$

I am working on a problem involving the average number of jobs $L$ in an M/M/1 queue with arrival rate $\lambda$, service rate $\mu$. For traffic intensity $\rho = \frac{\lambda}{\mu}$,

$$ L = \frac{\rho}{1 - \rho} = \frac{\lambda}{\mu - \lambda}. $$

I wanted to assess if $L(\lambda, \mu)$ is jointly convex, so I started by finding the Hessian $H$ of the function.

$$ H = \begin{bmatrix} \frac{2\lambda}{(\mu-\lambda)^3} + \frac{2}{(\mu-\lambda)^2} & -\frac{2\lambda}{(\mu-\lambda)^3} - \frac{1}{(\mu-\lambda)^2} \\ -\frac{2\lambda}{(\mu-\lambda)^3} - \frac{1}{(\mu-\lambda)^2} & \frac{2\lambda}{(\mu-\lambda)^3} \end{bmatrix}. $$

As I understand, my next step should be to assess the value of the function $\vec{x}^TH\vec{x}$ where $\vec{x} = \begin{bmatrix}\lambda \\ \mu\end{bmatrix}$ over the feasible region (which is $\lambda, \mu \ge 0, \mu \gt \lambda$). However, through factoring and simplification I found that

$$ \begin{bmatrix}\lambda & \mu\end{bmatrix} \begin{bmatrix} \frac{2\lambda}{(\mu-\lambda)^3} + \frac{2}{(\mu-\lambda)^2} & -\frac{2\lambda}{(\mu-\lambda)^3} - \frac{1}{(\mu-\lambda)^2} \\ -\frac{2\lambda}{(\mu-\lambda)^3} - \frac{1}{(\mu-\lambda)^2} & \frac{2\lambda}{(\mu-\lambda)^3} \end{bmatrix}\begin{bmatrix}\lambda \\ \mu\end{bmatrix} = 0. $$

This indicates the matrix $H$ is both positive semidefinite and negative semidefinite which in turn means $L(\lambda, \mu)$ is both convex and concave.

Is this correct or am I missing something here? Either my computations or my intuitions are flawed because I thought only linear functions could be both convex and concave. And if it is correct, are there any implications that would disallow me from having $L(\lambda, \mu)$ as the objective in a convex optimization problem? Thanks!

$\endgroup$

1 Answer 1

9
$\begingroup$

Your calculations (factoring and simplification) are incorrect. $L$ is neither convex nor concave as a function of $\lambda$ and $\mu$.

This can be concluded by examining the eigenvalues of the Hessian of $L$ with respect to $\lambda$ and $\mu$. I used MAPLE to compute the Hessian, and then evaluate its eigenvalues at the point $\lambda = 0.5, \mu = 1$. The eigenvalues are 24.649 and -0.649. This shows that the Hessian is indefinite at that point, and therefore that $L$ is neither convex nor concave at that point, or in general.

$\endgroup$
1
  • $\begingroup$ Indeed, if λ and μ are non-zero and not equal to each other, the determinant of the Hessian, and therefore the product of its eigenvalues, is negative, which implies that there must be one positive and one negative eigenvalue, and therefore the Hessian is indefinite, and L is neither convex nor concave, other than at these excluded points $\endgroup$ Nov 25, 2019 at 17:46

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.