In the context of discrete optimization, what exactly does it mean to "quadratize" a function?

The term seems to be used mainly by operations researchers, in my experience.

• Can you add a reference to where the term "quadratize" is being used, for context? Jun 27, 2019 at 6:15
• @MichaelFeldmeier: if I give a reference, the definition will probably be in the reference (or at least implied in the reference). Different references have different meanings for "quadratization" so I wonder if there's some consensus. Jun 29, 2019 at 18:38

One definition of quadratization (perhaps there is more) is provided in the paper by Boros, 2018.

In non-mathematical terms, quadratization is defined as

a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.

Rewriting this in functional notation,

Given a pseudo-Boolean function $$f(x)$$ on $$\{0,1\}^n$$, we say that $$g(x,y)$$ is a quadratization of $$f$$ if $$g(x,y)$$ is a quadratic polynomial depending on $$x$$ and on $$m$$ auxiliary variables $$y_1,\cdots,y_m$$, such that $$f(x)=\min\limits_{y\in\{0,1\}^m}g(x,y)\quad\forall x\in\{0,1\}^n.$$

Note that a pseudo-Boolean function is one that maps from $$\{0,1\}^n$$ to $$\Bbb R$$ which "assigns a real value to each tuple of $$n$$ binary variables $$x_1,\cdots,x_n$$".

One addition where the name comes from: in the same way as we speak of linearization (approximating a non-linear function or region by one or many linear functions) quadratization means approximating a non-linear function by quadratic ones.

Reference

[1] Boros, E., Crama, Y., Rodríguez-Heck, E. (2018). Quadratizations of symmetric pseudo-Boolean functions: sub-linear bounds on the number of auxiliary variables. ISAIM.

• Helpful edit, @MarcoLubbecke! Also nice original answer. Jun 27, 2019 at 13:34
• I know that definition, but it requires that the quadratic function exactly equals the original function when minimized over the auxiliary variables. Many quadratizations only require the "ground state" or "minimum" to be preserved. Jun 29, 2019 at 18:40