Convex piecewise linear functions - partitioned vs max representation
up vote
1
down vote
favorite
I know that convex piecewise linear function $f$ can be defined in two closely related ways -
There exist $Q subseteq P(X)$ s.t. $bigcup Q = X$ and on every $A in Q$ the function is linear (Example).
There exist a set ${(a_1,b_1),ldots,(a_m,b_m)}$ s.t. $f(x) = max_{iin[m]} a_i^T x + b_i$ (Example).
It makes sense that if $Q$ is a partition of $X$ it should be that $|Q| = m$ but I can't seem to prove it. Is my guess correct?
linear-algebra analysis convex-geometry
asked Dec 4 at 9:24
Meni
234
add a comment |
up vote
1
down vote
favorite
I know that convex piecewise linear function $f$ can be defined in two closely related ways -
There exist $Q subseteq P(X)$ s.t. $bigcup Q = X$ and on every $A in Q$ the function is linear (Example).
There exist a set ${(a_1,b_1),ldots,(a_m,b_m)}$ s.t. $f(x) = max_{iin[m]} a_i^T x + b_i$ (Example).
It makes sense that if $Q$ is a partition of $X$ it should be that $|Q| = m$ but I can't seem to prove it. Is my guess correct?
linear-algebra analysis convex-geometry
asked Dec 4 at 9:24
Meni
234
The $i$-th set of the partition is the one where the $i$-th function realizes the maximum. You might want to specify how you want to handle special cases such as when two functions are equal or when some function is redundant, but generally you are right.
– Michal Adamaszek
Dec 4 at 10:06
I think the redundancy can be treated in two ways - 1. Change the equality with inequality 2. Specify that $f|_{A}$ is not the same for every two distinct subsets (in the sense of their extension to the whole space)
– Meni
Dec 4 at 10:12
Is it that straightforward? The proof I know just shows that the epigraph is a polyhedron and as such can be represented as a max of affine functions but I can't seem to find the quantification. Maybe because the text wanted to avoid dealing with the cases you mentioned.
– Meni
Dec 6 at 6:33
The first 'definition' does not guarantee convexity.
– LinAlg
Dec 7 at 14:58
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I know that convex piecewise linear function $f$ can be defined in two closely related ways -
There exist $Q subseteq P(X)$ s.t. $bigcup Q = X$ and on every $A in Q$ the function is linear (Example).
There exist a set ${(a_1,b_1),ldots,(a_m,b_m)}$ s.t. $f(x) = max_{iin[m]} a_i^T x + b_i$ (Example).
It makes sense that if $Q$ is a partition of $X$ it should be that $|Q| = m$ but I can't seem to prove it. Is my guess correct?
linear-algebra analysis convex-geometry
asked Dec 4 at 9:24
Meni
234
I know that convex piecewise linear function $f$ can be defined in two closely related ways -
There exist $Q subseteq P(X)$ s.t. $bigcup Q = X$ and on every $A in Q$ the function is linear (Example).
There exist a set ${(a_1,b_1),ldots,(a_m,b_m)}$ s.t. $f(x) = max_{iin[m]} a_i^T x + b_i$ (Example).
It makes sense that if $Q$ is a partition of $X$ it should be that $|Q| = m$ but I can't seem to prove it. Is my guess correct?
linear-algebra analysis convex-geometry
linear-algebra analysis convex-geometry
asked Dec 4 at 9:24
Meni
234
asked Dec 4 at 9:24
Meni
234
asked Dec 4 at 9:24
Meni
234
asked Dec 4 at 9:24
Meni
234
asked Dec 4 at 9:24
Meni
234
234
The $i$-th set of the partition is the one where the $i$-th function realizes the maximum. You might want to specify how you want to handle special cases such as when two functions are equal or when some function is redundant, but generally you are right.
– Michal Adamaszek
Dec 4 at 10:06
I think the redundancy can be treated in two ways - 1. Change the equality with inequality 2. Specify that $f|_{A}$ is not the same for every two distinct subsets (in the sense of their extension to the whole space)
– Meni
Dec 4 at 10:12
Is it that straightforward? The proof I know just shows that the epigraph is a polyhedron and as such can be represented as a max of affine functions but I can't seem to find the quantification. Maybe because the text wanted to avoid dealing with the cases you mentioned.
– Meni
Dec 6 at 6:33
The first 'definition' does not guarantee convexity.
– LinAlg
Dec 7 at 14:58
add a comment |
The $i$-th set of the partition is the one where the $i$-th function realizes the maximum. You might want to specify how you want to handle special cases such as when two functions are equal or when some function is redundant, but generally you are right.
– Michal Adamaszek
Dec 4 at 10:06
I think the redundancy can be treated in two ways - 1. Change the equality with inequality 2. Specify that $f|_{A}$ is not the same for every two distinct subsets (in the sense of their extension to the whole space)
– Meni
Dec 4 at 10:12
Is it that straightforward? The proof I know just shows that the epigraph is a polyhedron and as such can be represented as a max of affine functions but I can't seem to find the quantification. Maybe because the text wanted to avoid dealing with the cases you mentioned.
– Meni
Dec 6 at 6:33
The first 'definition' does not guarantee convexity.
– LinAlg
Dec 7 at 14:58
The $i$-th set of the partition is the one where the $i$-th function realizes the maximum. You might want to specify how you want to handle special cases such as when two functions are equal or when some function is redundant, but generally you are right.
– Michal Adamaszek
Dec 4 at 10:06
The $i$-th set of the partition is the one where the $i$-th function realizes the maximum. You might want to specify how you want to handle special cases such as when two functions are equal or when some function is redundant, but generally you are right.
– Michal Adamaszek
Dec 4 at 10:06
I think the redundancy can be treated in two ways - 1. Change the equality with inequality 2. Specify that $f|_{A}$ is not the same for every two distinct subsets (in the sense of their extension to the whole space)
– Meni
Dec 4 at 10:12
I think the redundancy can be treated in two ways - 1. Change the equality with inequality 2. Specify that $f|_{A}$ is not the same for every two distinct subsets (in the sense of their extension to the whole space)
– Meni
Dec 4 at 10:12
Is it that straightforward? The proof I know just shows that the epigraph is a polyhedron and as such can be represented as a max of affine functions but I can't seem to find the quantification. Maybe because the text wanted to avoid dealing with the cases you mentioned.
– Meni
Dec 6 at 6:33
Is it that straightforward? The proof I know just shows that the epigraph is a polyhedron and as such can be represented as a max of affine functions but I can't seem to find the quantification. Maybe because the text wanted to avoid dealing with the cases you mentioned.
– Meni
Dec 6 at 6:33
The first 'definition' does not guarantee convexity.
– LinAlg
Dec 7 at 14:58
The first 'definition' does not guarantee convexity.
– LinAlg
Dec 7 at 14:58
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3025339%2fconvex-piecewise-linear-functions-partitioned-vs-max-representation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fmath.stackexchange.com%2fquestions%2f3025339%2fconvex-piecewise-linear-functions-partitioned-vs-max-representation%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
The $i$-th set of the partition is the one where the $i$-th function realizes the maximum. You might want to specify how you want to handle special cases such as when two functions are equal or when some function is redundant, but generally you are right.
– Michal Adamaszek
Dec 4 at 10:06
I think the redundancy can be treated in two ways - 1. Change the equality with inequality 2. Specify that $f|_{A}$ is not the same for every two distinct subsets (in the sense of their extension to the whole space)
– Meni
Dec 4 at 10:12
Is it that straightforward? The proof I know just shows that the epigraph is a polyhedron and as such can be represented as a max of affine functions but I can't seem to find the quantification. Maybe because the text wanted to avoid dealing with the cases you mentioned.
– Meni
Dec 6 at 6:33
The first 'definition' does not guarantee convexity.
– LinAlg
Dec 7 at 14:58