2
$\begingroup$

I am doing constrained vector optimization using a non-convex non-linear likelihood function. My problem is of the following form:

$$\begin{align*}\hat Q &= \underset{\vec Q}{\arg\min} -\log \mathcal{L}(\vec Q) \\ &s.t. \; Q_i > 0 \text{ for all } i=1...|\vec Q|\end{align*}$$

with $\mathcal{L}$ being the non-convex function in question.

My problem is that $\vec Q$ is very high dimensional, so no matter how many restarts I use, I never start in the neighbourhood of the optimal solution and thus never converge to the global minimum.

My idea is to convexify the function so that I can get into the neighbourhood of the solution, and then run the non-convex solver to try to find the global minimum. Is this a viable strategy? And if so, is there a good silver-bullet for convexification? If not, do you have any suggestions for me?

(P.S. I can provide the likelihood function if it is helpful, but it is extremely complex.)

(P.P.S. Is this the right stack exchange for this question?)

Improve this question
$\endgroup$
5
  • $\begingroup$ The problem you describe is quite general and the difficulties you mentioned have been shared by many people in the statistics community. Without further details, it is hard to give a meaningful answer. I just want to point out that you probably want to convexify the negative log likelihood. (Minimizing a convex function could be easy. Maximizing a convex function is difficult, as you are essentially maximizing over the boundary) $\endgroup$
    – passerby51
    Commented Feb 17, 2015 at 20:59
  • $\begingroup$ By the way, you can ask your question in stats.stackexchange.com, but I am not sure which one is better for this particular type of question. $\endgroup$
    – passerby51
    Commented Feb 17, 2015 at 21:02
  • $\begingroup$ Thanks @passerby51. (In practice I actually am minimizing the negative log likelihood, I just didn't know it would make a difference for the problem statement. I'll edit to reflect that though.) $\endgroup$
    – rhombidodecahedron
    Commented Feb 17, 2015 at 23:15
  • $\begingroup$ No problem. I doubt without more details you could get a useful response. Maybe you could try to simplify your likelihood and provide a version which captures the problem and not too complex? $\endgroup$
    – passerby51
    Commented Feb 18, 2015 at 1:52
  • $\begingroup$ What is the dimensionality of the problem? It may be possible to solve this using an off the shelf (semi)rigirorous global optimization solver, such as BARON, or BMIBNB under YALMIP. Among other things, they iteratively produce lower-bounding convexifications, and find upper bounds with feasible solutions, then branch and bound the whole thing until the gap between lower bound from lower-bounding convexifications and upper bound is below a specified tolerance. The solvers can likely do that better than you can. $\endgroup$
    – Mark L. Stone
    Commented Dec 23, 2017 at 18:09

0

Reset to default

You must log in to answer this question.