What is quadratization?

Question

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.

Answer 1

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.}