Likelihood convexification

Question

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

Answer 1

It is not the case that you can only minimize convex functions unless you start out close to the optimum, nor that high dimensionality dooms you to defeat. Convexity is nice for technical reasons, and some optimization algorithms rely on it to guarantee convergence, but the less restrictive conditions of a) a unique minimum, b) no saddle points, and c) continuity are jointly all you really need - and even this collection can be relaxed, depending upon the optimization algorithm.

Consider the following function, which I'm making up for illustrative purposes:

$f(x) = \log(1+\Sigma_{i=1}^N |x_i|)$

This is clearly not convex. We'll run it through R's conjugate gradient (CG) algorithm with $N = 100$ and some random starting points well away from the true minimum:

> func <- function(x) log(1+sum(abs(x)))
> # Starting values between 10 and 100 (true optimum values = 0)
> start <- runif(100, 10, 100)
> t1 <- now()
> res <- optim(start, func, method = "CG", control=list(abstol=1e-5, maxit=10000))
> now() - t1  # Runtime on my 3-year-old laptop
Time difference of 3.011732 secs
> sum(abs(res$par))
[1] 9.755393e-09

The sum of the absolute value of the resulting parameters is very close to 0, indicating that CG did well in this case. Some other algorithms that may apply are Nelder-Mead and simulated annealing, or even steepest descent. If your dimensionality is really high, methods which build up an approximation to the Hessian, like BFGS, may well be too slow.

Naturally, given the lack of information we have about the your likelihood function and its dimensionality, your mileage may vary widely. As Kjetl said in comments, at this level of abstraction, not much definitive can be said.