# Minimizing linear objective on intersection of convex sets

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.

## 1 Answer

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.

• Thanks! This paper seems to justify an algorithm I was hoping would work :-) . I'll implement it and see how well it works. – Justin Solomon Nov 13 '16 at 21:55
• Just implemented and it works great! If this ends up published some day, of course I'll gladly acknowledge your help. Thanks so much! – Justin Solomon Nov 14 '16 at 18:49