2
$\begingroup$

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.
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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$ – Justin Solomon Nov 13 '16 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$ – Justin Solomon Nov 14 '16 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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