Making difference of log constraints convex

Question

I have the discrete likelihood estimation problem $\max \sum m_i\log p_i $ where $m$ is a given vector of length $n$. The constraints are $0 \preceq p \preceq 1$, $\sum_{i=1}^n p_i = 1, $ and one final constraint which is not convex: $$ \log p_i \geq \frac{1}{2}(\log p_{i-1} + \log p_{i+1}); \quad i = 2, \dots, n-1. $$

This constraint ensures that the probability distribution is log concave.

I am trying to make this constraint something I can put into a convex program. I've tried some basic substitutions and combining terms, but that hasn't proven fruitful.

For example, if I write $x_i = \frac{p_i^2}{p_{i-1}p_{i+1}}$, then I don't know how I'd rewrite the objective in terms of the $x_i$'s.

Answer 1

The constraints are not convex. Consider the example below in which x1 and x2 are each vectors of 3 elements which satisfy the inequality in question, as shown. 0.5(x1 + x2) does not satisfy the inequality, thereby proving it is not convex.

>> x1 = [0.868417827606570   0.121582145814843 0.010000025679806];
>> x2 = [0.017508300926335 0.264007818119070 0.718483881445100];
>> x3 = 0.5*(x1 + x2)
x3 =
   0.442963064266453   0.192794981966956   0.364241953562453
>> log(x1(2)) - 0.5*(log(x1(1)) + log(x1(3)))
ans =
   0.265959817560572
>> log(x2(2)) - 0.5*(log(x2(1)) + log(x2(3)))
ans =
   0.856069527413664
>> log(x3(2)) - 0.5*(log(x3(1)) + log(x3(3)))
ans =
  -0.734025017605155

In order to use a convex programming method, you could do something like Difference of Convex Functions Programming. That would entail doing a first order (linear) expansion of the right-hand-side terms in the non-convex constraint about their current (or an initial) value. You can only use first order expansion because the quadratic term would go in the wrong direction relative to having an overall convex constraint. You will need to start the iteration with initial values (expansion points). Then update the expansion point on each subsequent iteration with the optimal value of the convex program just solved. There is no guarantee of convergence to anything, let alone to a local or global optimum.

Alternatively, you could throw it in a global optimizer, such as BARON, perhaps using a slightly positive lower bound of p so as to avoid difficulties at 0.

Answer 2

Let $z_i = \log p_i$ (i.e. $p_i = e^{z_i}$) and everything changes to linear constraints except the constraint $\sum e^{z_i} = 1$ which you can relax to $\sum e^{z_i} \leq 1$ since it will be tight at optimality (assuming $m_i$ positive).