# Convex optimization on the unit hypercube with gradients and a bounded minimum

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?

• Since you are minimizing only over the unit hyper-cube, have you considered Coordinate descent? May 24 at 19:45
• 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. May 24 at 20:04
• Can you be more detailed about your objective? May 24 at 21:15
• @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. May 24 at 22:24
• @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 May 24 at 22:25