Randomized Subspace Gradient Method for Constrained Optimization

We propose randomized subspace gradient methods for high-dimensional constrained optimization. Whereas there are related studies on unconstrained optimization problems, there are relatively few for constrained optimization problems because of the difficulty of handling constraints. Our algorithms project gradient vectors onto a subspace that is a random projection of the subspace spanned by the gradients of active constraints. We determine the worst case iteration complexity under linear and nonlinear settings and theoretically confirm that our algorithms can take a larger step size than their deterministic counterpart. From the advantages of taking longer steps and randomized subspace gradients, we show that our algorithms can be especially time-efficient when gradients are expensive to obtain. Furthermore, they perform well in cases in which gradients could not be obtained directly, and instead, gradients are obtained using directional derivatives.

Funding: This work was partially supported by JSPS Grant-in-Aid for Scientific Research(B) [JP23H03351] and JST CREST [Grant JPMJCR24Q2].