Mixing
Is the following function concave? Where does it attain its minimum?Its maximum?
Consider the function
$f: {1 , ldots, m} times Delta^{m} rightarrow mathbb{R}$ where
begin{equation}
Delta^{m}:={lambda in mathbb{R}^{m} | sum_{i=1}^{m} lambda_i = 1 , lambda_j geq 0 text{ for } j=1, ldots m }
end{equation}
begin{equation}
f(j,lambda)=langle y^{(j)}, sum _{i=1}^{m} lambda_i x^{(i)}-z rangle
end{equation}
For some $y^{s} in mathbb{R}^{n} text{ for } s=1, ldots, m, z in mathbb{R}^{n}$ and $x^{(i)} in mathbb{R}^{n} text{ for } i=1, ldots m . $
Question: Is the function $F : Delta^{m} mapsto mathbb{R}^{m}$
begin{equation}
F(lambda) = underset{j=1, ldots, m }{min} f(j,lambda)
end{equation}
concave? Where does it attain its minimum (as a function of $lambda$ of course)? Please consider first my attempt before answering, and tell me where I am wrong (if I am). Additional question: where does it attain its maximum?
Attempt: I know that the pointwise minimum of a set of concave function is again concave. So it would be enough to show that $f(j,lambda)$ is concave, to then conclude that the minimum is attained at some vertex $v_i=(0, ldots, 1, ldots, 0)$ where $1$ is in the $i^{text{th}}$ position. My argument for concavity is:
begin{gather}
f(j, alpha(lambda^{(1)}) + (1-alpha)(lambda^{(2)}))=langle y^{(j)}, alpha sum _{i=1}^{m} lambda_i^{(1)} x^{(i)}+(1-alpha)sum _{i=1}^{m} lambda_i ^{(2)}x^{(i)}-(1-alpha)z-alpha z rangle \
=(1-alpha) langle y^{(j)}, sum _{i=1}^{m} lambda_i^{(1)} x^{(i)}-z rangle + alpha langle y^{(j)}, sum _{i=1}^{m} lambda_i^{(2)} x^{(i)}-z rangle \
= alpha f(j, lambda^{(1)}) + (1-alpha)f(j,lambda^{(2)}),
end{gather}
where $alpha in [0,1]$, $lambda^{(1)}, lambda^{(2)} in Delta^{m}$.
optimization convex-optimization polyhedra
asked Nov 21 '18 at 10:10
sigmatau
1,7551924
add a comment |
Consider the function
$f: {1 , ldots, m} times Delta^{m} rightarrow mathbb{R}$ where
begin{equation}
Delta^{m}:={lambda in mathbb{R}^{m} | sum_{i=1}^{m} lambda_i = 1 , lambda_j geq 0 text{ for } j=1, ldots m }
end{equation}
begin{equation}
f(j,lambda)=langle y^{(j)}, sum _{i=1}^{m} lambda_i x^{(i)}-z rangle
end{equation}
For some $y^{s} in mathbb{R}^{n} text{ for } s=1, ldots, m, z in mathbb{R}^{n}$ and $x^{(i)} in mathbb{R}^{n} text{ for } i=1, ldots m . $
Question: Is the function $F : Delta^{m} mapsto mathbb{R}^{m}$
begin{equation}
F(lambda) = underset{j=1, ldots, m }{min} f(j,lambda)
end{equation}
concave? Where does it attain its minimum (as a function of $lambda$ of course)? Please consider first my attempt before answering, and tell me where I am wrong (if I am). Additional question: where does it attain its maximum?
Attempt: I know that the pointwise minimum of a set of concave function is again concave. So it would be enough to show that $f(j,lambda)$ is concave, to then conclude that the minimum is attained at some vertex $v_i=(0, ldots, 1, ldots, 0)$ where $1$ is in the $i^{text{th}}$ position. My argument for concavity is:
begin{gather}
f(j, alpha(lambda^{(1)}) + (1-alpha)(lambda^{(2)}))=langle y^{(j)}, alpha sum _{i=1}^{m} lambda_i^{(1)} x^{(i)}+(1-alpha)sum _{i=1}^{m} lambda_i ^{(2)}x^{(i)}-(1-alpha)z-alpha z rangle \
=(1-alpha) langle y^{(j)}, sum _{i=1}^{m} lambda_i^{(1)} x^{(i)}-z rangle + alpha langle y^{(j)}, sum _{i=1}^{m} lambda_i^{(2)} x^{(i)}-z rangle \
= alpha f(j, lambda^{(1)}) + (1-alpha)f(j,lambda^{(2)}),
end{gather}
where $alpha in [0,1]$, $lambda^{(1)}, lambda^{(2)} in Delta^{m}$.
optimization convex-optimization polyhedra
asked Nov 21 '18 at 10:10
sigmatau
1,7551924
Hello - your overall argument and the detailed argument for each $f(j, cdot)$ are all sound. Note that by setting $X$ to be the matrix with column $x^{(j)}$ and then $w_j = (y^{(j)})^TX, c_j = langle y^{j},zrangle$ you can write $f(j,lambda) = w_j lambda - c_j$. Thus these functions are affine. That's what you argument is showing. The minimum of $F$ may then be found with linear programming.
– Hans Engler
Nov 21 '18 at 13:57
add a comment |
Consider the function
$f: {1 , ldots, m} times Delta^{m} rightarrow mathbb{R}$ where
begin{equation}
Delta^{m}:={lambda in mathbb{R}^{m} | sum_{i=1}^{m} lambda_i = 1 , lambda_j geq 0 text{ for } j=1, ldots m }
end{equation}
begin{equation}
f(j,lambda)=langle y^{(j)}, sum _{i=1}^{m} lambda_i x^{(i)}-z rangle
end{equation}
For some $y^{s} in mathbb{R}^{n} text{ for } s=1, ldots, m, z in mathbb{R}^{n}$ and $x^{(i)} in mathbb{R}^{n} text{ for } i=1, ldots m . $
Question: Is the function $F : Delta^{m} mapsto mathbb{R}^{m}$
begin{equation}
F(lambda) = underset{j=1, ldots, m }{min} f(j,lambda)
end{equation}
concave? Where does it attain its minimum (as a function of $lambda$ of course)? Please consider first my attempt before answering, and tell me where I am wrong (if I am). Additional question: where does it attain its maximum?
Attempt: I know that the pointwise minimum of a set of concave function is again concave. So it would be enough to show that $f(j,lambda)$ is concave, to then conclude that the minimum is attained at some vertex $v_i=(0, ldots, 1, ldots, 0)$ where $1$ is in the $i^{text{th}}$ position. My argument for concavity is:
begin{gather}
f(j, alpha(lambda^{(1)}) + (1-alpha)(lambda^{(2)}))=langle y^{(j)}, alpha sum _{i=1}^{m} lambda_i^{(1)} x^{(i)}+(1-alpha)sum _{i=1}^{m} lambda_i ^{(2)}x^{(i)}-(1-alpha)z-alpha z rangle \
=(1-alpha) langle y^{(j)}, sum _{i=1}^{m} lambda_i^{(1)} x^{(i)}-z rangle + alpha langle y^{(j)}, sum _{i=1}^{m} lambda_i^{(2)} x^{(i)}-z rangle \
= alpha f(j, lambda^{(1)}) + (1-alpha)f(j,lambda^{(2)}),
end{gather}
where $alpha in [0,1]$, $lambda^{(1)}, lambda^{(2)} in Delta^{m}$.
optimization convex-optimization polyhedra
asked Nov 21 '18 at 10:10
sigmatau
1,7551924
Consider the function
$f: {1 , ldots, m} times Delta^{m} rightarrow mathbb{R}$ where
begin{equation}
Delta^{m}:={lambda in mathbb{R}^{m} | sum_{i=1}^{m} lambda_i = 1 , lambda_j geq 0 text{ for } j=1, ldots m }
end{equation}
begin{equation}
f(j,lambda)=langle y^{(j)}, sum _{i=1}^{m} lambda_i x^{(i)}-z rangle
end{equation}
For some $y^{s} in mathbb{R}^{n} text{ for } s=1, ldots, m, z in mathbb{R}^{n}$ and $x^{(i)} in mathbb{R}^{n} text{ for } i=1, ldots m . $
Question: Is the function $F : Delta^{m} mapsto mathbb{R}^{m}$
begin{equation}
F(lambda) = underset{j=1, ldots, m }{min} f(j,lambda)
end{equation}
concave? Where does it attain its minimum (as a function of $lambda$ of course)? Please consider first my attempt before answering, and tell me where I am wrong (if I am). Additional question: where does it attain its maximum?
Attempt: I know that the pointwise minimum of a set of concave function is again concave. So it would be enough to show that $f(j,lambda)$ is concave, to then conclude that the minimum is attained at some vertex $v_i=(0, ldots, 1, ldots, 0)$ where $1$ is in the $i^{text{th}}$ position. My argument for concavity is:
begin{gather}
f(j, alpha(lambda^{(1)}) + (1-alpha)(lambda^{(2)}))=langle y^{(j)}, alpha sum _{i=1}^{m} lambda_i^{(1)} x^{(i)}+(1-alpha)sum _{i=1}^{m} lambda_i ^{(2)}x^{(i)}-(1-alpha)z-alpha z rangle \
=(1-alpha) langle y^{(j)}, sum _{i=1}^{m} lambda_i^{(1)} x^{(i)}-z rangle + alpha langle y^{(j)}, sum _{i=1}^{m} lambda_i^{(2)} x^{(i)}-z rangle \
= alpha f(j, lambda^{(1)}) + (1-alpha)f(j,lambda^{(2)}),
end{gather}
where $alpha in [0,1]$, $lambda^{(1)}, lambda^{(2)} in Delta^{m}$.
optimization convex-optimization polyhedra
optimization convex-optimization polyhedra
asked Nov 21 '18 at 10:10
sigmatau
1,7551924
asked Nov 21 '18 at 10:10
sigmatau
1,7551924
edited Nov 21 '18 at 13:35
asked Nov 21 '18 at 10:10
sigmatau
1,7551924
asked Nov 21 '18 at 10:10
sigmatau
1,7551924
asked Nov 21 '18 at 10:10
sigmatau
1,7551924
1,7551924
Hello - your overall argument and the detailed argument for each $f(j, cdot)$ are all sound. Note that by setting $X$ to be the matrix with column $x^{(j)}$ and then $w_j = (y^{(j)})^TX, c_j = langle y^{j},zrangle$ you can write $f(j,lambda) = w_j lambda - c_j$. Thus these functions are affine. That's what you argument is showing. The minimum of $F$ may then be found with linear programming.
– Hans Engler
Nov 21 '18 at 13:57
add a comment |
Hello - your overall argument and the detailed argument for each $f(j, cdot)$ are all sound. Note that by setting $X$ to be the matrix with column $x^{(j)}$ and then $w_j = (y^{(j)})^TX, c_j = langle y^{j},zrangle$ you can write $f(j,lambda) = w_j lambda - c_j$. Thus these functions are affine. That's what you argument is showing. The minimum of $F$ may then be found with linear programming.
– Hans Engler
Nov 21 '18 at 13:57
Hello - your overall argument and the detailed argument for each $f(j, cdot)$ are all sound. Note that by setting $X$ to be the matrix with column $x^{(j)}$ and then $w_j = (y^{(j)})^TX, c_j = langle y^{j},zrangle$ you can write $f(j,lambda) = w_j lambda - c_j$. Thus these functions are affine. That's what you argument is showing. The minimum of $F$ may then be found with linear programming.
– Hans Engler
Nov 21 '18 at 13:57
Hello - your overall argument and the detailed argument for each $f(j, cdot)$ are all sound. Note that by setting $X$ to be the matrix with column $x^{(j)}$ and then $w_j = (y^{(j)})^TX, c_j = langle y^{j},zrangle$ you can write $f(j,lambda) = w_j lambda - c_j$. Thus these functions are affine. That's what you argument is showing. The minimum of $F$ may then be found with linear programming.
– Hans Engler
Nov 21 '18 at 13:57
add a comment |
1 Answer
1
active
oldest
votes
$g(lambda) = f(j,lambda)$ is concave in $lambda$, and the minimum of concave functions is concave.
By the maximum principle, a concave function is minimized at an extreme point of the domain, which is the argument for your choice $v_i$.
answered Nov 21 '18 at 17:19
LinAlg
8,4761521
What about the maximum?Is it true that a conave function attains its maximum at a vertex? If so, could you point me to some references?
– sigmatau
Nov 21 '18 at 19:04
A concave function can attain its maximum anywhere in the domain (interior and boundary). Linear optimization is your friend.
– LinAlg
Nov 21 '18 at 19:27
you have an idea how to find the maximum of $F(lambda)$?
– sigmatau
Nov 21 '18 at 19:34
@sigmatau do you have matlab?
– LinAlg
Nov 21 '18 at 20:10
1
If you formulate it as a linear optimization problem ($max_{lambda,t} {t : t leq f(j,lambda) forall j}$), there is complexity theory from interior point methods.
– LinAlg
Nov 21 '18 at 21:44
|
show 1 more comment
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',
autoActivateHeartbeat: false,
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%2f3007515%2fis-the-following-function-concave-where-does-it-attain-its-minimumits-maximum%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
$g(lambda) = f(j,lambda)$ is concave in $lambda$, and the minimum of concave functions is concave.
By the maximum principle, a concave function is minimized at an extreme point of the domain, which is the argument for your choice $v_i$.
answered Nov 21 '18 at 17:19
LinAlg
8,4761521
What about the maximum?Is it true that a conave function attains its maximum at a vertex? If so, could you point me to some references?
– sigmatau
Nov 21 '18 at 19:04
A concave function can attain its maximum anywhere in the domain (interior and boundary). Linear optimization is your friend.
– LinAlg
Nov 21 '18 at 19:27
you have an idea how to find the maximum of $F(lambda)$?
– sigmatau
Nov 21 '18 at 19:34
@sigmatau do you have matlab?
– LinAlg
Nov 21 '18 at 20:10
1
If you formulate it as a linear optimization problem ($max_{lambda,t} {t : t leq f(j,lambda) forall j}$), there is complexity theory from interior point methods.
– LinAlg
Nov 21 '18 at 21:44
|
show 1 more comment
$g(lambda) = f(j,lambda)$ is concave in $lambda$, and the minimum of concave functions is concave.
By the maximum principle, a concave function is minimized at an extreme point of the domain, which is the argument for your choice $v_i$.
answered Nov 21 '18 at 17:19
LinAlg
8,4761521
What about the maximum?Is it true that a conave function attains its maximum at a vertex? If so, could you point me to some references?
– sigmatau
Nov 21 '18 at 19:04
A concave function can attain its maximum anywhere in the domain (interior and boundary). Linear optimization is your friend.
– LinAlg
Nov 21 '18 at 19:27
you have an idea how to find the maximum of $F(lambda)$?
– sigmatau
Nov 21 '18 at 19:34
@sigmatau do you have matlab?
– LinAlg
Nov 21 '18 at 20:10
1
If you formulate it as a linear optimization problem ($max_{lambda,t} {t : t leq f(j,lambda) forall j}$), there is complexity theory from interior point methods.
– LinAlg
Nov 21 '18 at 21:44
|
show 1 more comment
$g(lambda) = f(j,lambda)$ is concave in $lambda$, and the minimum of concave functions is concave.
By the maximum principle, a concave function is minimized at an extreme point of the domain, which is the argument for your choice $v_i$.
answered Nov 21 '18 at 17:19
LinAlg
8,4761521
$g(lambda) = f(j,lambda)$ is concave in $lambda$, and the minimum of concave functions is concave.
By the maximum principle, a concave function is minimized at an extreme point of the domain, which is the argument for your choice $v_i$.
answered Nov 21 '18 at 17:19
LinAlg
8,4761521
answered Nov 21 '18 at 17:19
LinAlg
8,4761521
answered Nov 21 '18 at 17:19
LinAlg
8,4761521
answered Nov 21 '18 at 17:19
LinAlg
8,4761521
8,4761521
What about the maximum?Is it true that a conave function attains its maximum at a vertex? If so, could you point me to some references?
– sigmatau
Nov 21 '18 at 19:04
A concave function can attain its maximum anywhere in the domain (interior and boundary). Linear optimization is your friend.
– LinAlg
Nov 21 '18 at 19:27
you have an idea how to find the maximum of $F(lambda)$?
– sigmatau
Nov 21 '18 at 19:34
@sigmatau do you have matlab?
– LinAlg
Nov 21 '18 at 20:10
1
If you formulate it as a linear optimization problem ($max_{lambda,t} {t : t leq f(j,lambda) forall j}$), there is complexity theory from interior point methods.
– LinAlg
Nov 21 '18 at 21:44
|
show 1 more comment
What about the maximum?Is it true that a conave function attains its maximum at a vertex? If so, could you point me to some references?
– sigmatau
Nov 21 '18 at 19:04
A concave function can attain its maximum anywhere in the domain (interior and boundary). Linear optimization is your friend.
– LinAlg
Nov 21 '18 at 19:27
you have an idea how to find the maximum of $F(lambda)$?
– sigmatau
Nov 21 '18 at 19:34
@sigmatau do you have matlab?
– LinAlg
Nov 21 '18 at 20:10
1
If you formulate it as a linear optimization problem ($max_{lambda,t} {t : t leq f(j,lambda) forall j}$), there is complexity theory from interior point methods.
– LinAlg
Nov 21 '18 at 21:44
What about the maximum?Is it true that a conave function attains its maximum at a vertex? If so, could you point me to some references?
– sigmatau
Nov 21 '18 at 19:04
What about the maximum?Is it true that a conave function attains its maximum at a vertex? If so, could you point me to some references?
– sigmatau
Nov 21 '18 at 19:04
A concave function can attain its maximum anywhere in the domain (interior and boundary). Linear optimization is your friend.
– LinAlg
Nov 21 '18 at 19:27
A concave function can attain its maximum anywhere in the domain (interior and boundary). Linear optimization is your friend.
– LinAlg
Nov 21 '18 at 19:27
you have an idea how to find the maximum of $F(lambda)$?
– sigmatau
Nov 21 '18 at 19:34
you have an idea how to find the maximum of $F(lambda)$?
– sigmatau
Nov 21 '18 at 19:34
@sigmatau do you have matlab?
– LinAlg
Nov 21 '18 at 20:10
@sigmatau do you have matlab?
– LinAlg
Nov 21 '18 at 20:10
1
1
If you formulate it as a linear optimization problem ($max_{lambda,t} {t : t leq f(j,lambda) forall j}$), there is complexity theory from interior point methods.
– LinAlg
Nov 21 '18 at 21:44
If you formulate it as a linear optimization problem ($max_{lambda,t} {t : t leq f(j,lambda) forall j}$), there is complexity theory from interior point methods.
– LinAlg
Nov 21 '18 at 21:44
|
show 1 more comment
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%2f3007515%2fis-the-following-function-concave-where-does-it-attain-its-minimumits-maximum%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
Hello - your overall argument and the detailed argument for each $f(j, cdot)$ are all sound. Note that by setting $X$ to be the matrix with column $x^{(j)}$ and then $w_j = (y^{(j)})^TX, c_j = langle y^{j},zrangle$ you can write $f(j,lambda) = w_j lambda - c_j$. Thus these functions are affine. That's what you argument is showing. The minimum of $F$ may then be found with linear programming.
– Hans Engler
Nov 21 '18 at 13:57