dbcp 0.1.0

A CVXPY extension for disciplined biconvex programming.

DBCP: Disciplined Biconvex Programming

DBCP is an extension of CVXPY for (approximately) solving biconvex optimization problems in the form

$$ \begin{array}{ll} \text{minimize} & f_0(x, y)\ \text{subject to} & f_i(x, y) \leq 0,\quad i = 1, \ldots, m\ & h_i(x, y) = 0,\quad i = 1, \ldots, p, \end{array} $$

where $x \in X$, $y \in Y$ are the optimization variables. The functions $f_0, \ldots, f_m$ are biconvex, meaning that for fixed $y$, the functions $f_i(\cdot, y)$ are convex, and for fixed $x$, the functions $f_i(x, \cdot)$ are convex. The functions $h_1, \ldots, h_p$ are biaffine in a similar sense. In the most general case, biconvex optimization problems are very hard to solve, but heuristic methods such as alternating convex search (ACS) can often find good solutions in practice.

More theoretical and technical aspects about biconvex optimization problems can be found in our accompanying paper.

Installation

DBCP has the following dependencies:

• Python >= 3.12
• NumPy >= 2.3.3
• CVXPY >= 1.7.3

Using pip

You can install the package using pip:

pip install dbcp

Development setup

We manage dependencies through uv. Once you have installed uv you can perform the following commands to set up a development environment:

1. Clone the repository:

   git clone https://github.com/nrgrp/dbcp.git
   cd dbcp
   

2. Create a virtual environment and install dependencies:

   make install
   

This will:

• Create a Python 3.12 virtual environment.
• Install all dependencies from pyproject.toml.

Usage

Here we provide a basic overview of how to use DBCP; for more details, please refer to our paper and the examples.

DBCP syntax rule for multiplications

DBCP is based on CVXPY and inherits its syntax rules, with the following extension for variable multiplications:

1. A valid DBCP convex product expression between variables should be one of the form:

   • affine * affine
   • affine-nonneg * convex
   • affine-nonpos * concave
   • convex-nonneg * convex-nonneg
   • concave-nonpos * concave-nonpos

2. There exists no loop in the variable interaction graph of the overall expression, where the edge between two variables indicates that they appear in different sides in a product expression as described in the above rule.

Specifying biconvex problems

DBCP provides the BiconvexProblem and BiconvexRelaxProblem classes to specify biconvex problems. Roughly speaking, the difference between these two classes is that BiconvexProblem implements a solver for directly solving the original biconvex problem, while BiconvexRelaxProblem is used for solving a relaxed version of the problem with additional slack variables added to the constraints, so the latter allows solving with infeasible starting points.

As an example, to create a BiconvexProblem instance, one can use the following syntax:

prob = BiconvexProblem(obj, [x_var, y_var], constraints)

The argument obj is a DBCP-compliant biconvex expression representing the objective function, x_var and y_var are lists of the biconvex optimization variables, and constraints is a list of DBCP-compliant biconvex constraints. The arguments x_var and y_var define the variable partition for the biconvex problem, such that each group will be fixed when optimizing over the other group during the ACS procedure.

Verification of biconvexity

After creating a BiconvexProblem or BiconvexRelaxProblem instance, one can call its is_dbcp method to verify whether the problem is DBCP-compliant:

prob.is_dbcp()

which returns True if the problem is DBCP-compliant, and False otherwise.

Solving a biconvex problem

After creating a BiconvexProblem instance, one can call its solve method to solve the problem:

prob.solve()

The most important optional arguments of the BiconvexProblem.solve method are as follows:

• lbd: The regularization parameter of the proximal term.
• max_iters: The maximum number of ACS iterations.
• gap_tolerance: The tolerance for the gap between the subproblems when stopping the ACS procedure.

The BiconvexRelaxProblem.solve method has an additional optional argument nu to specify the penalty parameter for the total slackness, i.e., violation of the biconvex constraints.

Problem status

After solving a biconvex problem using the solve method, one can check the problem status using the status attribute.

The possible status values for BiconvexProblem are as follows:

• converge: The ACS procedure converged successfully, i.e., the final gap between the subproblems is within the specified tolerance.
• converge_inaccurate: The maximum number of iterations was reached, but the final gap between the subproblems is still larger than the specified tolerance.

In the second case, one may want to call the solve method again. This will continue the ACS procedure from the last iteration, until either convergence is achieved or the maximum number of iterations is reached.

The possible status values for BiconvexRelaxProblem are as follows:

• converge: The ACS procedure converged successfully with a feasible solution (i.e., the total slackness is zero) to the original problem.
• converge_infeasible: The ACS procedure converged successfully, but the final solution is still infeasible with nonzero total slackness.
• converge_inaccurate: The maximum number of iterations was reached with a feasible final point, but the final gap between the subproblems is still larger than the specified tolerance.
• converge_inaccurate_infeasible: The maximum number of iterations was reached, but the final gap between the subproblems is still larger than the specified tolerance, and the final solution is still infeasible with nonzero total slackness.

When 'infeasible' appears in the status, one may want to increase the penalty parameter nu and call the solve method again.

Examples

Basic example

Suppose we are given a matrix $A \in \mathbf{R}^{m \times n}$. Consider the following nonnegative matrix factorization problem:

$$ \begin{array}{ll} \text{minimize} & {|XY + Z - A|}F\ \text{subject to} & X{ij} \geq 0,\quad i = 1, \ldots, m, \quad j = 1, \ldots, k\ & Y_{ij} \geq 0,\quad i = 1, \ldots, k,\quad j = 1, \ldots, n\ & {|Z|}_F \leq 1, \end{array} $$

with variables $X \in \mathbf{R}^{m \times k}$, $Y \in \mathbf{R}^{k \times n}$, and $Z \in \mathbf{R}^{m \times n}$.

To specify and solve this problem using DBCP, one may use the following code:

import cvxpy as cp
import dbcp

X = cp.Variable((m, k), nonneg=True)
Y = cp.Variable((k, n), nonneg=True)
Z = cp.Variable((m, n))

obj = cp.Minimize(cp.norm(X @ Y + Z - A, 'fro'))
constraints = [cp.norm(Z, 'fro') <= 1]
prob = dbcp.BiconvexProblem(obj, [[X], [Y]], constraints)

prob.solve()

Other examples

We provide several other examples in the examples directory. To view and reproduce the examples, executing

make marimo

in the repository folder will install and start the marimo environment.