5.4.6. Positive L1-ball

For a given scalar \(\xi\ge0\), the positive L1-ball is a linear constraint defined as

\[ \mathcal{C}_{L_1^+} = \big\{ {\bf w} \in \mathbb{R}^{N} \;|\; {\bf w} \ge 0,\; \|{\bf w}\|_1 \le \xi \big\}, \]

where \(\|{\bf w}\|_1 = |w_1|+\dots+|w_N|\) is the L1-norm. The condition \(\xi \ge 0\) is required for this subset to be nonempty. The figure below shows how this constraint looks like in \(\mathbb{R}^{2}\) or in \(\mathbb{R}^{3}\).

Positive L1-ball in 2D

Positive L1-ball in 3D

5.4.6.1. Constrained optimization

Optimizing a function \(J({\bf w})\) subject to the positive L1-ball can be expressed as

\[\begin{split} \operatorname*{minimize}_{\textbf{w}\in\mathbb{R}^N}\; J({\bf w}) \quad{\rm s.t.}\quad \begin{cases} {\bf w} \ge 0 \\ \|{\bf w}\|_1 \le \xi. \end{cases}\end{split}\]

The figure below visualizes such an optimization problem in \(\mathbb{R}^{2}\).

5.4.6.2. Orthogonal projection

The projection of a point \({\bf u}\in\mathbb{R}^{N}\) onto the positive L1-ball is the (unique) solution to the following problem

\[\begin{split} \operatorname*{minimize}_{{\bf w}\in\mathbb{R}^N}\; \|{\bf w}-{\bf u}\|^2 \quad{\rm s.t.}\quad \begin{cases} {\bf w} \ge 0 \\ \|{\bf w}\|_1 \le \xi. \end{cases} \end{split}\]

The solution is computed as follows.

Projection onto the positive L1-ball

\[\begin{split} \mathcal{P}_{\mathcal{C}_{L_1^+}}({\bf u}) = \mathcal{P}_{\mathcal{C}_{L_1}}\big(\max\{{\bf u},{\bf 0}\}\big) %\begin{cases} %\max\{{\bf u},{\bf 0}\} & \mathrm{if} \; {\bf 1}^\top \max\{{\bf u},{\bf 0}\} \leq \xi \\ %\mathcal{P}_{\mathcal{C}_{\rm simplex}}\big(\max\{{\bf u},{\bf 0}\}\big) & \mathrm{otherwise}. %\end{cases} \end{split}\]

Note: \(\mathcal{C}_{L_1}\) denotes the standard L1-ball.

5.4.6.3. Implementation

The python implementation is given below.

def project_l1plus(u, bound):
    return project_l1ball(np.maximum(0, u), bound)

Here is an example of use.

u = np.array([-1, 2, -5, 3, 2])

p = project_l1plus(u, bound=5)