1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'm curious, because I see this a lot: it seems to be common for people to think that if they can't find a convex reformulation of a problem, that they just haven't found the right trick. But that is definitely incorrect thinking. As Mark points out, the problem simply isn't convex. And as with nearly all non-convex problems, no amount of transformation or reformulation will change that. Exceptions are rare. But again, I see people ask this a lot: "how can I transform my problem into a convex one?" That's just not how convexity works. $\endgroup$ – Michael Grant Mar 21 '18 at 1:28
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I know the constraint is not convex, but I think there should be a way to transform it into a convex constraint. $\endgroup$ – quiet Mar 20 '18 at 21:17
  • $\begingroup$ The constraint set, i.e., the feasible region of all constraints taken together, is not convex. That is what my example showed. Therefore, there is NO reformulation of that constraint set which will be convex. You may think think there should be a way to transform it into a convex constraint, but there is not.. $\endgroup$ – Mark L. Stone Mar 20 '18 at 21:50
  • 3
    $\begingroup$ It's actually possible in some cases to transform a non-convex feasible region into a convex feasible region by a nonlinear change of variables, but I don't believe it is possible in this case. $\endgroup$ – Brian Borchers Mar 21 '18 at 4:50
  • $\begingroup$ @ Brian Borchers Yes i agree with you. I overstated in the 3rd sentence in my comment. $\endgroup$ – Mark L. Stone Mar 21 '18 at 11:32
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Yes, this is better than my solution. I didn't consider restriction on $m_i$ allowing for relaxing the constraint. $\endgroup$ – Mark L. Stone Mar 21 '18 at 13:54
  • 1
    $\begingroup$ Pretty sure the problem is unbounded if some $m_i$ is negative $\endgroup$ – Johan Löfberg Mar 21 '18 at 14:08

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.