# DBCP: Disciplined Biconvex Programming
DBCP is an extension of [CVXPY](https://github.com/cvxpy/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](https://haozhu10015.github.io/papers/dbcp.html).
## Installation
DBCP has the following dependencies:
- Python >= 3.12
- [NumPy](https://numpy.org/doc/stable/index.html) >= 2.3.3
- [CVXPY](https://www.cvxpy.org/) >= 1.7.3
### Using pip
You can install the package using pip:
```shell
pip install dbcp
```
### Development setup
We manage dependencies through [uv](https://docs.astral.sh/uv).
Once you have installed uv you can perform the following
commands to set up a development environment:
1. Clone the repository:
```shell
git clone https://github.com/nrgrp/dbcp.git
cd dbcp
```
2. Create a virtual environment and install dependencies:
```shell
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](./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:
```python
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:
```python
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:
```python
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 slack, 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 slack is zero)
to the original problem.
- `converge_infeasible`: The ACS procedure converged successfully,
but the final solution is still infeasible with nonzero total slack.
- `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 slack.
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:
```python
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](./examples) directory.
To view and reproduce the examples, executing
```shell
make marimo
```
in the repository folder will install
and start the [marimo](https://marimo.io/) environment.
## Citation
If you find DBCP useful in your research, please consider citing our paper:
```bibtex
@article{zhu2025dbcp,
title={Disciplined Biconvex Programming},
author={Zhu, H. and Boedecker, J.},
journal={arXiv Preprint arXiv:2511.01813},
year={2025},
}
```
Raw data
{
"_id": null,
"home_page": null,
"name": "dbcp",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.12",
"maintainer_email": null,
"keywords": "biconvex optimization, convex optimization, disciplined biconvex programming, disciplined convex programming",
"author": "Joschka Boedecker",
"author_email": "Hao Zhu <zhuh@cs.uni-freiburg.de>",
"download_url": "https://files.pythonhosted.org/packages/fb/f7/e341fa7effe6370242cf245b77aeb40dd5b3515f2758f5957789841e3166/dbcp-0.2.0.tar.gz",
"platform": null,
"description": "# DBCP: Disciplined Biconvex Programming\n\nDBCP is an extension of [CVXPY](https://github.com/cvxpy/cvxpy)\nfor (approximately) solving *biconvex optimization problems*\nin the form\n\n$$\n\\begin{array}{ll}\n \\text{minimize} & f_0(x, y)\\\\\n \\text{subject to} & f_i(x, y) \\leq 0,\\quad i = 1, \\ldots, m\\\\\n & h_i(x, y) = 0,\\quad i = 1, \\ldots, p,\n\\end{array}\n$$\n\nwhere $x \\in X$, $y \\in Y$ are the optimization variables.\nThe functions $f_0, \\ldots, f_m$ are biconvex, meaning that for fixed $y$,\nthe functions $f_i(\\cdot, y)$ are convex,\nand for fixed $x$, the functions $f_i(x, \\cdot)$ are convex.\nThe functions $h_1, \\ldots, h_p$ are biaffine in a similar sense.\nIn the most general case, biconvex optimization problems are very hard\nto solve, but heuristic methods such as *alternating convex search* (ACS)\ncan often find good solutions in practice.\n\nMore theoretical and technical aspects about\nbiconvex optimization problems can be found in our [accompanying paper](https://haozhu10015.github.io/papers/dbcp.html).\n\n## Installation\n\nDBCP has the following dependencies:\n\n- Python >= 3.12\n- [NumPy](https://numpy.org/doc/stable/index.html) >= 2.3.3\n- [CVXPY](https://www.cvxpy.org/) >= 1.7.3\n\n### Using pip\n\nYou can install the package using pip:\n\n```shell\npip install dbcp\n```\n\n### Development setup\n\nWe manage dependencies through [uv](https://docs.astral.sh/uv).\nOnce you have installed uv you can perform the following\ncommands to set up a development environment:\n\n1. Clone the repository:\n\n ```shell\n git clone https://github.com/nrgrp/dbcp.git\n cd dbcp\n ```\n\n2. Create a virtual environment and install dependencies:\n\n ```shell\n make install\n ```\n\nThis will:\n\n- Create a Python 3.12 virtual environment.\n- Install all dependencies from pyproject.toml.\n\n## Usage\n\nHere we provide a basic overview of how to use DBCP;\nfor more details, please refer to our paper\nand the [examples](./examples).\n\n### DBCP syntax rule for multiplications\n\nDBCP is based on CVXPY and inherits its syntax rules,\nwith the following extension for variable multiplications:\n\n1. A valid DBCP convex product expression between\n variables should be one of the form:\n\n - *affine* \\* *affine*\n - *affine-nonneg* \\* *convex*\n - *affine-nonpos* \\* *concave*\n - *convex-nonneg* \\* *convex-nonneg*\n - *concave-nonpos* \\* *concave-nonpos*\n\n2. There exists no loop in the variable interaction graph of\n the overall expression, where the edge between two variables\n indicates that they appear in different sides in a\n product expression as described in the above rule.\n\n### Specifying biconvex problems\n\nDBCP provides the `BiconvexProblem` and `BiconvexRelaxProblem`\nclasses to specify biconvex problems.\nRoughly speaking, the difference between these two classes is that\n`BiconvexProblem` implements a solver for directly solving\nthe original biconvex problem, while\n`BiconvexRelaxProblem` is used for solving a relaxed version\nof the problem with additional slack variables added to the constraints,\nso the latter allows solving with infeasible starting points.\n\nAs an example, to create a `BiconvexProblem` instance,\none can use the following syntax:\n\n```python\nprob = BiconvexProblem(obj, [x_var, y_var], constraints)\n```\n\nThe argument `obj` is a DBCP-compliant biconvex expression\nrepresenting the objective function, `x_var` and `y_var`\nare lists of the biconvex optimization variables,\nand `constraints` is a list of DBCP-compliant biconvex constraints.\nThe arguments `x_var` and `y_var` define the variable partition\nfor the biconvex problem, such that each group will be fixed\nwhen optimizing over the other group during the ACS procedure.\n\n### Verification of biconvexity\n\nAfter creating a `BiconvexProblem` or `BiconvexRelaxProblem` instance,\none can call its `is_dbcp` method to verify whether the problem\nis DBCP-compliant:\n\n```python\nprob.is_dbcp()\n```\n\nwhich returns `True` if the problem is DBCP-compliant, and `False` otherwise.\n\n### Solving a biconvex problem\n\nAfter creating a `BiconvexProblem` instance,\none can call its `solve` method to solve the problem:\n\n```python\nprob.solve()\n```\n\nThe most important optional arguments of the\n`BiconvexProblem.solve` method are as follows:\n\n- `lbd`: The regularization parameter of the proximal term.\n- `max_iters`: The maximum number of ACS iterations.\n- `gap_tolerance`: The tolerance for the gap between the subproblems\n when stopping the ACS procedure.\n\nThe `BiconvexRelaxProblem.solve` method has an additional\noptional argument `nu` to specify the penalty parameter\nfor the total slack, i.e.,\nviolation of the biconvex constraints.\n\n### Problem status\n\nAfter solving a biconvex problem using the `solve` method,\none can check the problem status using the `status` attribute.\n\nThe possible status values for `BiconvexProblem` are as follows:\n\n- `converge`: The ACS procedure converged successfully, i.e.,\n the final gap between the subproblems is within the specified tolerance.\n- `converge_inaccurate`: The maximum number of iterations was reached,\n but the final gap between the subproblems is still\n larger than the specified tolerance.\n\nIn the second case, one may want to call the `solve` method again.\nThis will continue the ACS procedure from the last iteration, until\neither convergence is achieved or the maximum number of iterations\nis reached.\n\nThe possible status values for `BiconvexRelaxProblem` are as follows:\n\n- `converge`: The ACS procedure converged successfully\n with a feasible solution (i.e., the total slack is zero)\n to the original problem.\n- `converge_infeasible`: The ACS procedure converged successfully,\n but the final solution is still infeasible with nonzero total slack.\n- `converge_inaccurate`: The maximum number of iterations was reached\n with a feasible final point,\n but the final gap between the subproblems is still\n larger than the specified tolerance.\n- `converge_inaccurate_infeasible`: The maximum number of iterations was reached,\n but the final gap between the subproblems is still\n larger than the specified tolerance,\n and the final solution is still infeasible with nonzero total slack.\n\nWhen 'infeasible' appears in the status,\none may want to increase the penalty parameter `nu`\nand call the `solve` method again.\n\n## Examples\n\n### Basic example\n\nSuppose we are given a matrix $A \\in \\mathbf{R}^{m \\times n}$.\nConsider the following nonnegative matrix factorization problem:\n\n$$\n\\begin{array}{ll}\n \\text{minimize} & {\\|XY + Z - A\\|}_F\\\\\n \\text{subject to} & X_{ij} \\geq 0,\\quad i = 1, \\ldots, m,\n \\quad j = 1, \\ldots, k\\\\\n & Y_{ij} \\geq 0,\\quad i = 1, \\ldots, k,\\quad j = 1, \\ldots, n\\\\\n & {\\|Z\\|}_F \\leq 1,\n\\end{array}\n$$\n\nwith variables $X \\in \\mathbf{R}^{m \\times k}$,\n$Y \\in \\mathbf{R}^{k \\times n}$,\nand $Z \\in \\mathbf{R}^{m \\times n}$.\n\nTo specify and solve this problem using DBCP,\none may use the following code:\n\n```python\nimport cvxpy as cp\nimport dbcp\n\nX = cp.Variable((m, k), nonneg=True)\nY = cp.Variable((k, n), nonneg=True)\nZ = cp.Variable((m, n))\n\nobj = cp.Minimize(cp.norm(X @ Y + Z - A, 'fro'))\nconstraints = [cp.norm(Z, 'fro') <= 1]\nprob = dbcp.BiconvexProblem(obj, [[X], [Y]], constraints)\n\nprob.solve()\n```\n\n### Other examples\n\nWe provide several other examples\nin the [examples](./examples) directory.\nTo view and reproduce the examples, executing\n\n```shell\nmake marimo\n```\n\nin the repository folder will install\nand start the [marimo](https://marimo.io/) environment.\n\n## Citation\n\nIf you find DBCP useful in your research, please consider citing our paper:\n\n```bibtex\n@article{zhu2025dbcp,\n title={Disciplined Biconvex Programming},\n author={Zhu, H. and Boedecker, J.},\n journal={arXiv Preprint arXiv:2511.01813},\n year={2025},\n}\n```\n",
"bugtrack_url": null,
"license": null,
"summary": "A CVXPY extension for disciplined biconvex programming.",
"version": "0.2.0",
"project_urls": {
"repository": "https://github.com/nrgrp/dbcp"
},
"split_keywords": [
"biconvex optimization",
" convex optimization",
" disciplined biconvex programming",
" disciplined convex programming"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "36491421fdff04f4c5c06d1384d6e3ba0dead960ed2a8e4a93700bf7531a8139",
"md5": "8d9880c678baa71cf3848e227059512d",
"sha256": "bbc2aafe3ebb8cd7959b0009ea2b62a337fde2b15c95e2daa3d5e5ab1e6851bd"
},
"downloads": -1,
"filename": "dbcp-0.2.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "8d9880c678baa71cf3848e227059512d",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.12",
"size": 10596,
"upload_time": "2025-11-10T12:37:33",
"upload_time_iso_8601": "2025-11-10T12:37:33.956820Z",
"url": "https://files.pythonhosted.org/packages/36/49/1421fdff04f4c5c06d1384d6e3ba0dead960ed2a8e4a93700bf7531a8139/dbcp-0.2.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "fbf7e341fa7effe6370242cf245b77aeb40dd5b3515f2758f5957789841e3166",
"md5": "1a37c0e6e3071393431b83808f2c8e9e",
"sha256": "69340b19dda036ef6da68048a4b17c1c1c016f46721b30d11c8779299edc2ab7"
},
"downloads": -1,
"filename": "dbcp-0.2.0.tar.gz",
"has_sig": false,
"md5_digest": "1a37c0e6e3071393431b83808f2c8e9e",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.12",
"size": 46941,
"upload_time": "2025-11-10T12:37:35",
"upload_time_iso_8601": "2025-11-10T12:37:35.519793Z",
"url": "https://files.pythonhosted.org/packages/fb/f7/e341fa7effe6370242cf245b77aeb40dd5b3515f2758f5957789841e3166/dbcp-0.2.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-11-10 12:37:35",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "nrgrp",
"github_project": "dbcp",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "dbcp"
}
JSON
