计算科学 - 最小化凸集相交的线性目标 - 吾爱随笔录

假设我希望解决以下优化问题：

\begin{aligned} min_{μ \in R^{n}} & μ^{⊤} c \\ subject to & μ \in C_{1} \cap C_{2} \cap \dots \cap C_{k}, \end{aligned}

$\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}$ 其中每个是一个凸集。此外，我可以访问投影运算符 是否有围绕可以找到的优化算法？

C_{i} \subseteq R^{n}

$C_i\subseteq\mathbb{R}^n$

p_{i} (x) := {\begin{aligned} \arg min_{y} & ‖ y - x ‖_{2} \\ subject to & y \in C_{i} . \end{aligned}

$p_i(x):=\left\{ \begin{array}{rl} \arg\min_y & \|y-x\|_2\\ \textrm{subject to} & y\in C_i. \end{array} \right.$ $p_i(\cdot)$ $\mu$

笔记：

集合 $k$ 的数量可能很大。当我尝试将标准 ADMM 技巧应用于此问题时，我最终需要 $O(nk)$ 空间，这太多了。
如果我将正则化器 $\varepsilon \|\mu\|_2^2$ 添加到问题中，那么它看起来像投影，我可以使用像Dykstra's algorithm这样的循环方法。但我真的很想在没有正则化的情况下解决这个问题。