dwavesystems / dwavesystems/dimod

Use of "lagrange multiplier" terminology

Open
#1,009 0 comments 0 reactions 0 assignees View on GitHub
question
Dominant language
Python
Stars
143
Forks
91
Avg merge
1h 24m
Merged PRs (30d)
3

Description

The term Lagrange multiplier is used throughout the code, documentation, and API's. Suggest reviewing whether this is the most appropriate terminology. My understanding is that when we encode constraints in the BQM, we are using a penalty formulation, which is not the same as formulating the Lagrangian function (which is a function of both the decision variables and the Lagrange parameter, `lambda`). If so, "penalty strength" or simply "strength" may be more appropriate terminology for code and documentation.

Good overview of the differences here: https://math.stackexchange.com/questions/2585712/merit-function-vs-largrange-functions-vs-penalty-funcitons.

See also https://arxiv.org/ftp/arxiv/papers/1811/1811.11538.pdf, page 34:

> The general procedure of Transformation #1 [standard approach for encoding constraints] has similarities to the Lagrange Multiplier approach of classical optimization. The key difference is that our scalar penalties (P) are not “dual” variables to be determined by the optimization. Rather, they are parameters set a priori to encourage the search process to avoid candidate solutions that are infeasible.

The Lagrange multiplier usage currently appears in a variety of places in the dimod source, including in some public-facing API functions, e.g.:
https://github.com/dwavesystems/dimod/blob/96928a68637ec1d2af5e19e0678417b164ef237d/dimod/binary/binary_quadratic_model.py#L591-L593
https://github.com/dwavesystems/dimod/blob/96928a68637ec1d2af5e19e0678417b164ef237d/dimod/constrained.py#L1167-L1168
By contrast, there are also a couple of places where `strength` is used instead of `lagrange_multiplier`, e.g.:
https://github.com/dwavesystems/dimod/blob/96928a68637ec1d2af5e19e0678417b164ef237d/dimod/higherorder/utils.py#L100

Use of the Lagrange multiplier terminology is also prevalent in `dwave-networkx` (I'm happy to create a separate issue there as well, if desired), and I think some of the `dwave-examples` as well.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.