3
$\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.)

$\endgroup$
5
  • 2
    $\begingroup$ I doubt that much can be sdaid at this level of abstraction, so you need to give more details. $\endgroup$ Nov 25, 2015 at 18:57
  • 6
    $\begingroup$ If you could find a way to make a function convex (while preserving essential properties such as the location of its global maximum), then--because finding its global maximum would then be straightforward--you would have performed a feat even more difficult than optimizing it. Doesn't that make it obvious there cannot possibly be a "silver bullet"? $\endgroup$
    – whuber
    Nov 25, 2015 at 19:34
  • $\begingroup$ I would like to see the function (and probably the data needed to run it). $\endgroup$ Nov 25, 2015 at 20:00
  • $\begingroup$ Roughly how high dimensional is it? "Very" differs from person to person, after all. $\endgroup$
    – jbowman
    Nov 25, 2015 at 20:18
  • $\begingroup$ rhombidodecahedron: you say you find a lot of different local minima of your objective function, but have you checked whether all local-minima are close to one another in space ? whether their likelihoods are very different ? Even if L doesn't have a reason to be nice, it might not be that horrible $\endgroup$ Nov 26, 2015 at 13:40

1 Answer 1

3
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.