2
$\begingroup$

I'd like to find the minimum of a smooth, continuous function inside the unit hypercube (the dimensionality of which could go into the hundreds or even thousands). The function is convex (Hessian $\geq 0$ everywhere) within the unit hypercube but not outside of it. Additionally, I know that the minimum of the function is always positive.

I can evaluate both the function and its gradient relatively cheaply; second derivatives are quite a bit more expensive.

Frank-Wolfe works, and is easy to do as I can always go in the direction of the vertex closest to the negative gradient, but the line search part is really quite slow. It also doesn't seem to make particularly good use of the convex structure or the bound on the minimum.

Are there any other approaches I should research given my problem?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Since you are minimizing only over the unit hyper-cube, have you considered Coordinate descent? $\endgroup$
    – batwing
    Commented May 24, 2021 at 19:45
  • 1
    $\begingroup$ Since the line search seems to be an issue, have you considered loosening the convergence criteria at the outset and gradually tightening them? In other words, compute gradient, do sloppy line search (get a better point but not necessarily best in that direction), recompute gradient, do a slightly less sloppy line search, ...? You might be trading more gradient descent iterations for fewer line search iterations; it's an empirical question whether that is a net win. $\endgroup$
    – prubin ♦
    Commented May 24, 2021 at 20:04
  • 1
    $\begingroup$ Can you be more detailed about your objective? $\endgroup$
    – worldsmithhelper
    Commented May 24, 2021 at 21:15
  • $\begingroup$ @worldsmithhelper sorry, sure! It's a probabilistic model over many variables (thus the unit hypercube) and the objective function is the sum of KL-divergences from some external target distributions (thus the zero bound). It just so happens, fortunately, that it's relatively easy to evaluate the gradient of the final expression, and that it's a convex surface. Ordinarily this kind of problem would fall under MAP estimation, loopy belief propagation, that kind of thing – I'm just interested in this particular situation. $\endgroup$
    – sk29910
    Commented May 24, 2021 at 22:24
  • $\begingroup$ @prubin Yup, already played around with that, thanks! It could be me, but I haven't found a sweet spot yet and I don't know if there is one, sadly $\endgroup$
    – sk29910
    Commented May 24, 2021 at 22:25

3 Answers 3

Reset to default
3
$\begingroup$

From the looks of it (simple feasible set, convex objective, gradient available), Frank-Wolfe indeed makes a lot of sense here. I can point out that there exist many variants of the algorithm, and that several are implemented in this recent Julia package. This can give you a quick way to experiments various algorithmic configurations.

If you do decide to look into other methodologies, since your problem is convex, then I would recommend giving conic optimization a try. Conic optimization solvers employ robust interior-point algorithms with strong convergence guarantees; it may or may not be faster than FW depending on your problem. The Mosek modeling cookbook provides a lot of modeling tips (you mention KL divergence so I linked to the corresponding section of the cookbook). You might also find tools such as CVX (Matlab), cvxpy (Python) or Convex.jl (Julia) useful for doing the modeling. They will automatically reformulate the problem into conic form before passing it to a conic solver.

Improve this answer
$\endgroup$
2
$\begingroup$

When you have only box constraints I don't think Frank Wofle is very efficient. Frank Wolfe can handle more complex constraints. You should try a quasi newton algorithm like l-bfgs-b or a truncated newton conjugate gradient algorithm with projection.

Improve this answer
$\endgroup$
2
$\begingroup$

I hesitate to suggest it, since gradient methods tend to be faster than non-gradient methods, but the Nelder-Mead "simplex" algorithm is easy to code and might be worth a try.

Improve this answer
$\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.