Problems {#subsec:simplex_screening}
----------------------------

Optimization over unit simplex ${\triangle}:= \{{\bm{x}}\in{\mathbb{R}}^n \ | \ x_i \ge 0,\quad \sum_{i=1}^{n} x_i = 1 \}$ is a important class of constrained problems , as it includes optimization over any finite polytope. In this case, the columns of $A$ describe the vertices, and ${\bm{x}}$ are barycentric coordinates representing the point $A{\bm{x}}$. Formally, $g({\bm{x}})$ is the indicator function of the unit simplex ${\mathcal{C}}= {\triangle}$ in this case.

The following two theorems provide screening rules for simplex constrained problems. We provide all proofs in Appendix \[app:simplex\_screening\].

\[thm:simplexcondition\] For general simplex constrained optimization $\min_{{\bm{x}}\in{\triangle}} f(A{\bm{x}})$, the optimality condition  gives rise to the following screening rule at the optimal point, for any $i \in [n]$ $$\label{eq:simplexcondition}
({\bm{a}}_i - A{\bm{x}}^\star)^\top{\bm{w}}^\star > 0 
\ \Rightarrow \ x_i^\star = 0 \ .$$

In the following Theorem \[thm:simplex\_smooth\] we now assume smoothness and strong convexity of function $f$ to provide screening rules for simplex problems, in terms of an arbitrary iterate ${\bm{x}}$, without knowing ${\bm{x}}^\star$.

\[thm:simplex\_smooth\] Let $f$ be $L$-smooth and $\mu$-strongly convex over the unit simplex ${\mathcal{C}}= {\triangle}$. Then for simplex constrained optimization $\min_{{\bm{x}}\in{\triangle}} f(A{\bm{x}})$ we have the following screening rule, for any $i \in [n]$ $$({\bm{a}}_i -A{\bm{x}})^\top\nabla f(A{\bm{x}}) > L\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}}{\left\lVert{\bm{a}}_i-A{\bm{x}}\right\rVert} 
\ \Rightarrow 