What is quadratization?When to use indicator constraints versus big-M approaches in solving (mixed-)integer programsWhat are common abbreviations in Operations Research?Optimization terminology: “Exact” v. “Approximate”What is a solution?Polyhedra, Polyhedron, Polytopes and PolygonAre there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?Can an integer optimization problem be convex?Finding the linear functions defining a polyhedron through integer data?Theoretical results on performance of branch-and-boundVariable fixing based on a good feasible solution
How are side-channel attacks executed? What does an attacker need to execute a side channel attack?
Why is the air inside airliners so dry (low humidity)?
Is a turbocharged piston aircraft the same thing as turboprop?
c1-c2 regular expression in sed and grep
Cheat at Rock-Paper-Scissors-Lizard-Spock
How did composers "test" their music?
How can you castle legally in Chess960 when the castling rook is on the king's destination square?
Does the House Resolution about the Impeachment Inquiry change anything?
What spacing difference is acceptable with a contracted tile job?
Is it possible to save a (science) PhD in 10 months?
Body swap, then building it back to health
ASCII Pumpkin Carving
Do dead weight 'components' exist?
How would a creature with a higher body temperature interact with surroundings?
Potential Postdoc advisor giving exams (assignment) as part of hiring process
What is Trump's position on the whistle blower allegations? What does he mean by "witch hunt"?
A new combinatorial property for the character table of a finite group?
"The" for the first time only
Modification of a public property - LWC
How should I push back against ridiculous work time expectations?
How to get a large amount of cash abroad if a debit card stops working?
How does an all-female medieval country maintain itself?
Why was the Vulcan bomber used for the Falklands raid?
Does the Tavern Brawler feat grant proficiency when the character is not proficient otherwise?
What is quadratization?
When to use indicator constraints versus big-M approaches in solving (mixed-)integer programsWhat are common abbreviations in Operations Research?Optimization terminology: “Exact” v. “Approximate”What is a solution?Polyhedra, Polyhedron, Polytopes and PolygonAre there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?Can an integer optimization problem be convex?Finding the linear functions defining a polyhedron through integer data?Theoretical results on performance of branch-and-boundVariable fixing based on a good feasible solution
$begingroup$
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.
integer-programming quadratic-programming terminology
edited Jun 27 at 17:59
Discrete lizard
1,0102 silver badges21 bronze badges
asked Jun 27 at 6:01
user1271772user1271772
4461 silver badge13 bronze badges
$endgroup$
add a comment
|
$begingroup$
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.
integer-programming quadratic-programming terminology
edited Jun 27 at 17:59
Discrete lizard
1,0102 silver badges21 bronze badges
asked Jun 27 at 6:01
user1271772user1271772
4461 silver badge13 bronze badges
$endgroup$
3
$begingroup$
Can you add a reference to where the term "quadratize" is being used, for context?
$endgroup$
– Michael Feldmeier
Jun 27 at 6:15
$begingroup$
@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.
$endgroup$
– user1271772
Jun 29 at 18:38
add a comment
|
$begingroup$
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.
integer-programming quadratic-programming terminology
edited Jun 27 at 17:59
Discrete lizard
1,0102 silver badges21 bronze badges
asked Jun 27 at 6:01
user1271772user1271772
4461 silver badge13 bronze badges
$endgroup$
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.
integer-programming quadratic-programming terminology
integer-programming quadratic-programming terminology
edited Jun 27 at 17:59
Discrete lizard
1,0102 silver badges21 bronze badges
asked Jun 27 at 6:01
user1271772user1271772
4461 silver badge13 bronze badges
edited Jun 27 at 17:59
Discrete lizard
1,0102 silver badges21 bronze badges
asked Jun 27 at 6:01
user1271772user1271772
4461 silver badge13 bronze badges
edited Jun 27 at 17:59
Discrete lizard
1,0102 silver badges21 bronze badges
edited Jun 27 at 17:59
Discrete lizard
1,0102 silver badges21 bronze badges
edited Jun 27 at 17:59
Discrete lizard
1,0102 silver badges21 bronze badges
1,0102 silver badges21 bronze badges
asked Jun 27 at 6:01
user1271772user1271772
4461 silver badge13 bronze badges
asked Jun 27 at 6:01
user1271772user1271772
4461 silver badge13 bronze badges
asked Jun 27 at 6:01
user1271772user1271772
4461 silver badge13 bronze badges
4461 silver badge13 bronze badges
3
$begingroup$
Can you add a reference to where the term "quadratize" is being used, for context?
$endgroup$
– Michael Feldmeier
Jun 27 at 6:15
$begingroup$
@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.
$endgroup$
– user1271772
Jun 29 at 18:38
add a comment
|
3
$begingroup$
Can you add a reference to where the term "quadratize" is being used, for context?
$endgroup$
– Michael Feldmeier
Jun 27 at 6:15
$begingroup$
@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.
$endgroup$
– user1271772
Jun 29 at 18:38
3
3
$begingroup$
Can you add a reference to where the term "quadratize" is being used, for context?
$endgroup$
– Michael Feldmeier
Jun 27 at 6:15
$begingroup$
Can you add a reference to where the term "quadratize" is being used, for context?
$endgroup$
– Michael Feldmeier
Jun 27 at 6:15
$begingroup$
@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.
$endgroup$
– user1271772
Jun 29 at 18:38
$begingroup$
@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.
$endgroup$
– user1271772
Jun 29 at 18:38
add a comment
|
1 Answer
1
active
oldest
votes
$begingroup$
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)=minlimits_yin0,1^mg(x,y)quadforall xin0,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.
edited Jun 27 at 13:19
Marco Lübbecke
2,8459 silver badges36 bronze badges
answered Jun 27 at 7:02
TheSimpliFire♦TheSimpliFire
2,8381 gold badge7 silver badges42 bronze badges
$endgroup$
2
$begingroup$
Helpful edit, @MarcoLubbecke! Also nice original answer.
$endgroup$
– E. Tucker
Jun 27 at 13:34
$begingroup$
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.
$endgroup$
– user1271772
Jun 29 at 18:40
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f799%2fwhat-is-quadratization%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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)=minlimits_yin0,1^mg(x,y)quadforall xin0,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.
edited Jun 27 at 13:19
Marco Lübbecke
2,8459 silver badges36 bronze badges
answered Jun 27 at 7:02
TheSimpliFire♦TheSimpliFire
2,8381 gold badge7 silver badges42 bronze badges
$endgroup$
2
$begingroup$
Helpful edit, @MarcoLubbecke! Also nice original answer.
$endgroup$
– E. Tucker
Jun 27 at 13:34
$begingroup$
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.
$endgroup$
– user1271772
Jun 29 at 18:40
add a comment
|
$begingroup$
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)=minlimits_yin0,1^mg(x,y)quadforall xin0,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.
edited Jun 27 at 13:19
Marco Lübbecke
2,8459 silver badges36 bronze badges
answered Jun 27 at 7:02
TheSimpliFire♦TheSimpliFire
2,8381 gold badge7 silver badges42 bronze badges
$endgroup$
2
$begingroup$
Helpful edit, @MarcoLubbecke! Also nice original answer.
$endgroup$
– E. Tucker
Jun 27 at 13:34
$begingroup$
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.
$endgroup$
– user1271772
Jun 29 at 18:40
add a comment
|
$begingroup$
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)=minlimits_yin0,1^mg(x,y)quadforall xin0,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.
edited Jun 27 at 13:19
Marco Lübbecke
2,8459 silver badges36 bronze badges
answered Jun 27 at 7:02
TheSimpliFire♦TheSimpliFire
2,8381 gold badge7 silver badges42 bronze badges
$endgroup$
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)=minlimits_yin0,1^mg(x,y)quadforall xin0,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.
edited Jun 27 at 13:19
Marco Lübbecke
2,8459 silver badges36 bronze badges
answered Jun 27 at 7:02
TheSimpliFire♦TheSimpliFire
2,8381 gold badge7 silver badges42 bronze badges
edited Jun 27 at 13:19
Marco Lübbecke
2,8459 silver badges36 bronze badges
edited Jun 27 at 13:19
Marco Lübbecke
2,8459 silver badges36 bronze badges
edited Jun 27 at 13:19
Marco Lübbecke
2,8459 silver badges36 bronze badges
2,8459 silver badges36 bronze badges
answered Jun 27 at 7:02
TheSimpliFire♦TheSimpliFire
2,8381 gold badge7 silver badges42 bronze badges
answered Jun 27 at 7:02
TheSimpliFire♦TheSimpliFire
2,8381 gold badge7 silver badges42 bronze badges
answered Jun 27 at 7:02
TheSimpliFire♦TheSimpliFire
2,8381 gold badge7 silver badges42 bronze badges
2,8381 gold badge7 silver badges42 bronze badges
2
$begingroup$
Helpful edit, @MarcoLubbecke! Also nice original answer.
$endgroup$
– E. Tucker
Jun 27 at 13:34
$begingroup$
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.
$endgroup$
– user1271772
Jun 29 at 18:40
add a comment
|
2
$begingroup$
Helpful edit, @MarcoLubbecke! Also nice original answer.
$endgroup$
– E. Tucker
Jun 27 at 13:34
$begingroup$
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.
$endgroup$
– user1271772
Jun 29 at 18:40
2
2
$begingroup$
Helpful edit, @MarcoLubbecke! Also nice original answer.
$endgroup$
– E. Tucker
Jun 27 at 13:34
$begingroup$
Helpful edit, @MarcoLubbecke! Also nice original answer.
$endgroup$
– E. Tucker
Jun 27 at 13:34
$begingroup$
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.
$endgroup$
– user1271772
Jun 29 at 18:40
$begingroup$
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.
$endgroup$
– user1271772
Jun 29 at 18:40
add a comment
|
Thanks for contributing an answer to Operations Research Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f799%2fwhat-is-quadratization%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
Can you add a reference to where the term "quadratize" is being used, for context?
$endgroup$
– Michael Feldmeier
Jun 27 at 6:15
$begingroup$
@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.
$endgroup$
– user1271772
Jun 29 at 18:38