4.27. The Binary Indicator

This example shows how to encode binary-valued decisions with an indicator UDF. The model is

\[\min\limits_x \; \tfrac{1}{2}\|x-y\|_2^2 + \delta_{\{0,1\}^n}(x),\]

where \(\delta_{\{0,1\}^n}\) is the indicator of the binary cube.

This is a discrete nonconvex constraint. The solver acts as a practical local method and does not guarantee that the output is a globally optimal binary solution.

The value returned by UDFBase.eval() is the indicator of the binary cube:

\[\begin{split}f(x) = \delta_{\{0,1\}^n}(x) = \begin{cases} 0, & x_i \in \{0,1\} \text{ for all } i, \\ +\infty, & \text{otherwise}. \end{cases}\end{split}\]

So eval only checks whether each coordinate is numerically close to \(0\) or \(1\):

def eval(self, arglist):
    x = np.asarray(arglist[0], dtype=float)
    is_binary = np.logical_or(np.abs(x) <= 1e-9, np.abs(x - 1.0) <= 1e-9)
    return 0.0 if np.all(is_binary) else float("inf")

The proximal operator returned by UDFBase.argmin() acts coordinatewise by projection onto \(\{0,1\}\):

\[\begin{split}\bigl(\operatorname{prox}_{\delta_{\{0,1\}^n}}(v)\bigr)_i = \begin{cases} 0, & v_i < \tfrac{1}{2}, \\ 1, & v_i \ge \tfrac{1}{2}. \end{cases}\end{split}\]

So the code is just a threshold at \(0.5\):

def argmin(self, lamb, arglist):
    v = np.asarray(arglist[0], dtype=float)
    prox = np.where(v >= 0.5, 1.0, 0.0)
    return [prox.tolist()]

The UDFBase.arguments() method tells ADMM that this indicator depends on one symbolic vector:

def arguments(self):
    return [self.arg]

Complete runnable example:

import numpy as np
import admm

class BinaryIndicator(admm.UDFBase):
    def __init__(self, arg):
        self.arg = arg

    def arguments(self):
        return [self.arg]

    def eval(self, arglist):
        x = np.asarray(arglist[0], dtype=float)
        is_binary = np.logical_or(np.abs(x) <= 1e-9, np.abs(x - 1.0) <= 1e-9)
        return 0.0 if np.all(is_binary) else float("inf")

    def argmin(self, lamb, arglist):
        v = np.asarray(arglist[0], dtype=float)
        prox = np.where(v >= 0.5, 1.0, 0.0)
        return [prox.tolist()]

y = np.array([0.2, 0.8, 1.4, -0.3])

model = admm.Model()
x = admm.Var("x", len(y))
model.setObjective(0.5 * admm.sum(admm.square(x - y)) + BinaryIndicator(x))
model.optimize()

print(" * x: ", np.asarray(x.X))  # Expected: ≈ [0, 1, 1, 0]
print(" * model.ObjVal: ", model.ObjVal)  # Expected: ≈ 0.165

This example is available as a standalone script in the examples/ folder of the ADMM repository:

python examples/udf_binary.py

In this concrete example, the threshold rule applies coordinatewise:

\[0.2 \mapsto 0, \qquad 0.8 \mapsto 1, \qquad 1.4 \mapsto 1, \qquad -0.3 \mapsto 0.\]

Hence the projection onto the binary cube is

\[x^\star = [0,\; 1,\; 1,\; 0].\]

Because \(x^\star \in \{0,1\}^4\), the indicator term vanishes:

\[\delta_{\{0,1\}^4}(x^\star) = 0.\]

Each coordinate is independently rounded onto \(\{0,1\}\).