Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints

Abstract

In this work, we consider convex optimization problems with smooth objective function and nonsmooth functional constraints. We propose a new stochastic gradient algorithm, called Stochastic Halfspace Approximation Method (SHAM), to solve this problem, where at each iteration we first take a gradient step for the objective function and then we perform a projection step onto one halfspace approximation of a randomly chosen constraint. We propose various strategies to create this stochastic halfspace approximation and we provide a unified convergence analysis that yields new convergence rates for SHAM algorithm in both optimality and feasibility criteria evaluated at some average point. In particular, we derive convergence rates of order $\mathcal{O}(1/\sqrt{k})$, when the objective function is only convex, and $\mathcal{O}(1/k)$ when the objective function is strongly convex. The efficiency of SHAM is illustrated through detailed numerical simulations.