I am trying to build a gradient descent algorithm for a convex function over a convex region in high dimension with no closed form. All I can do is:
- Check whether a point is in the region
- Evaluate the function at a point,
...both fairly intensive operations.
Is there an easy way to run this maximization? The problem I am running into is that often the max is on the set's boundary, so running a gradient-descent algorithm eventually goes outside the bounds, and I don't know any means of 'projecting onto the boundary' because I don't know what it looks like other than being convex
Steepest descent as is works only for unconditional problems in general. The (minus) gradient direction points at the steepest direction of the function with no respect for the constraints. That's why you come to the boundary, and the algorithm wants to continue further since there are smaller values of the function outside. This point of the boundary is very likely not even close to the optimal point. To send information to the algorithm (i.e. gradient) about the constraints one can use penalty/barrier function methods. Penalty normally gives outer (infeasible) approximations of the optimum while barrier needs (relative) interior to be non-empty. Using barrier functions you will always get feasible approximations. Though one has to stop using steepest descent, as it is very sensitive to ill-conditioned problems (which is typical for penalty/barrier methods). It is better to use some kind of quasi-newton or conjugate directions algorithms together with a line search.