Minimizing linear objective on intersection of convex sets

Question

Suppose I wish to solve the following optimization problem: $$ \begin{array}{rl} \min_{\mu\in\mathbb{R}^n} &\mu^\top c\\ \textrm{subject to} & \mu\in C_1\cap C_2\cap\cdots\cap C_k, \end{array} $$ where each $C_i\subseteq\mathbb{R}^n$ is a convex set. Furthermore, I have access to projection operators $$ p_i(x):=\left\{ \begin{array}{rl} \arg\min_y & \|y-x\|_2\\ \textrm{subject to} & y\in C_i. \end{array} \right. $$ Is there an optimization algorithm that wraps around the $p_i(\cdot)$'s that can find $\mu$?

---

Notes:

• The number of sets $k$ is potentially large. When I tried to apply standard ADMM tricks to this problem, I ended up needing $O(nk)$ space, which is too much.
• If I add a regularizer $\varepsilon \|\mu\|_2^2$ to the problem, then it looks like projection and I can use a cyclic method like Dykstra's algorithm. But I really would like to solve this problem without regularization.

Answer 1

See this recent paper on an extension of stochastic gradient descent that could be used on your problem:

https://arxiv.org/abs/1511.03760

You could also apply Dykstra's algorithm (or any other algorithm that does alternating projections on convex sets) by setting a target value for $\mu^{T}c \leq \gamma $ and reducing it once feasibility has been achieved.