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$?


  • 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 1


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


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.