Show that $max$ function on $mathbb R^n$ is convexShow strict convexity of expectation of the max of a linear functionThe mapping of a cost vector to the set of solutions of the respective LP is concaveProof that a coordinate-wise convex function is convex?If $(nabla f(x)-nabla f(y))cdot(x-y)geq m(x-y)cdot(x-y)$, why is $f$ convex?convexity of matrix “soft-max” (log trace of matrix exponential)function induced by optimizationShow that a funcction is convex using epigraphsIs this function strongly convex? or could I find a value space to make this function strongly convex?Why log-of-sum-of-exponentials $f(x)=logleft(sumlimits_i=1^n e^ x_iright)$ is a convex function for $x in R^n$Proving a function is convex if its epigraph is convex.Convex function's monotonicity?Prove convexity of set with triangular inequality
What historical events would have to change in order to make 19th century "steampunk" technology possible?
Can I hook these wires up to find the connection to a dead outlet?
Mathematica command that allows it to read my intentions
How to compactly explain secondary and tertiary characters without resorting to stereotypes?
Can compressed videos be decoded back to their uncompresed original format?
Different meanings of こわい
Where would I need my direct neural interface to be implanted?
In the UK, is it possible to get a referendum by a court decision?
Machine learning testing data
What are the G forces leaving Earth orbit?
how do we prove that a sum of two periods is still a period?
My ex-girlfriend uses my Apple ID to log in to her iPad. Do I have to give her my Apple ID password to reset it?
How to Prove P(a) → ∀x(P(x) ∨ ¬(x = a)) using Natural Deduction
files created then deleted at every second in tmp directory
How does a dynamic QR code work?
What Exploit Are These User Agents Trying to Use?
How seriously should I take size and weight limits of hand luggage?
Can someone clarify Hamming's notion of important problems in relation to modern academia?
Is it possible to map the firing of neurons in the human brain so as to stimulate artificial memories in someone else?
How badly should I try to prevent a user from XSSing themselves?
Rotate ASCII Art by 45 Degrees
How to show a landlord what we have in savings?
Was the Stack Exchange "Happy April Fools" page fitting with the '90's code?
How obscure is the use of 令 in 令和?
Show that $max$ function on $mathbb R^n$ is convex
Show strict convexity of expectation of the max of a linear functionThe mapping of a cost vector to the set of solutions of the respective LP is concaveProof that a coordinate-wise convex function is convex?If $(nabla f(x)-nabla f(y))cdot(x-y)geq m(x-y)cdot(x-y)$, why is $f$ convex?convexity of matrix “soft-max” (log trace of matrix exponential)function induced by optimizationShow that a funcction is convex using epigraphsIs this function strongly convex? or could I find a value space to make this function strongly convex?Why log-of-sum-of-exponentials $f(x)=logleft(sumlimits_i=1^n e^ x_iright)$ is a convex function for $x in R^n$Proving a function is convex if its epigraph is convex.Convex function's monotonicity?Prove convexity of set with triangular inequality
$begingroup$
I am reading the book Convex Optimization, and I don't understand why a $max$ function is convex.
The function is defined as:
$$f(x) = max(x_1, x_2, dots, x_n)$$
The book offers the proof shown below:
for $0 leq theta leq 1$
$$beginaligned f(theta x + (1 - theta)y) &= max_i left( theta x_i + (1 - theta)y_i right)\ & leq theta max_i x_i + (1 - theta)max_i y_i\ &= theta f(x) + (1 - theta)f(y) endaligned$$
However, I don't understand why the following inequality holds.
$$max_i (theta x_i + (1 - theta)y_i) leq theta max_i x_i + (1 - theta)max_i y_i$$
convex-analysis
$endgroup$
add a comment |
$begingroup$
I am reading the book Convex Optimization, and I don't understand why a $max$ function is convex.
The function is defined as:
$$f(x) = max(x_1, x_2, dots, x_n)$$
The book offers the proof shown below:
for $0 leq theta leq 1$
$$beginaligned f(theta x + (1 - theta)y) &= max_i left( theta x_i + (1 - theta)y_i right)\ & leq theta max_i x_i + (1 - theta)max_i y_i\ &= theta f(x) + (1 - theta)f(y) endaligned$$
However, I don't understand why the following inequality holds.
$$max_i (theta x_i + (1 - theta)y_i) leq theta max_i x_i + (1 - theta)max_i y_i$$
convex-analysis
$endgroup$
add a comment |
$begingroup$
I am reading the book Convex Optimization, and I don't understand why a $max$ function is convex.
The function is defined as:
$$f(x) = max(x_1, x_2, dots, x_n)$$
The book offers the proof shown below:
for $0 leq theta leq 1$
$$beginaligned f(theta x + (1 - theta)y) &= max_i left( theta x_i + (1 - theta)y_i right)\ & leq theta max_i x_i + (1 - theta)max_i y_i\ &= theta f(x) + (1 - theta)f(y) endaligned$$
However, I don't understand why the following inequality holds.
$$max_i (theta x_i + (1 - theta)y_i) leq theta max_i x_i + (1 - theta)max_i y_i$$
convex-analysis
$endgroup$
I am reading the book Convex Optimization, and I don't understand why a $max$ function is convex.
The function is defined as:
$$f(x) = max(x_1, x_2, dots, x_n)$$
The book offers the proof shown below:
for $0 leq theta leq 1$
$$beginaligned f(theta x + (1 - theta)y) &= max_i left( theta x_i + (1 - theta)y_i right)\ & leq theta max_i x_i + (1 - theta)max_i y_i\ &= theta f(x) + (1 - theta)f(y) endaligned$$
However, I don't understand why the following inequality holds.
$$max_i (theta x_i + (1 - theta)y_i) leq theta max_i x_i + (1 - theta)max_i y_i$$
convex-analysis
convex-analysis
edited Mar 20 at 17:43
Rodrigo de Azevedo
13.1k41960
13.1k41960
asked Sep 19 '17 at 3:31
hklelhklel
194110
194110
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Fix $kin 1,ldots,n$. We have
$$theta x_k + (1-theta)y_k leq theta max_i x_i + (1-theta)max_i y_i$$
because $x_k leq max_i x_i$, $y_k leq max_i y_i$, $theta geq 0$ and $1-theta geq 0$.
Since the statement above is true for any $k$ we have:
$$max_k [theta x_k + (1-theta)y_k]leq theta max_i x_i + (1-theta)max_i y_i.$$
$endgroup$
add a 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%2f2435464%2fshow-that-max-function-on-mathbb-rn-is-convex%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$
Fix $kin 1,ldots,n$. We have
$$theta x_k + (1-theta)y_k leq theta max_i x_i + (1-theta)max_i y_i$$
because $x_k leq max_i x_i$, $y_k leq max_i y_i$, $theta geq 0$ and $1-theta geq 0$.
Since the statement above is true for any $k$ we have:
$$max_k [theta x_k + (1-theta)y_k]leq theta max_i x_i + (1-theta)max_i y_i.$$
$endgroup$
add a comment |
$begingroup$
Fix $kin 1,ldots,n$. We have
$$theta x_k + (1-theta)y_k leq theta max_i x_i + (1-theta)max_i y_i$$
because $x_k leq max_i x_i$, $y_k leq max_i y_i$, $theta geq 0$ and $1-theta geq 0$.
Since the statement above is true for any $k$ we have:
$$max_k [theta x_k + (1-theta)y_k]leq theta max_i x_i + (1-theta)max_i y_i.$$
$endgroup$
add a comment |
$begingroup$
Fix $kin 1,ldots,n$. We have
$$theta x_k + (1-theta)y_k leq theta max_i x_i + (1-theta)max_i y_i$$
because $x_k leq max_i x_i$, $y_k leq max_i y_i$, $theta geq 0$ and $1-theta geq 0$.
Since the statement above is true for any $k$ we have:
$$max_k [theta x_k + (1-theta)y_k]leq theta max_i x_i + (1-theta)max_i y_i.$$
$endgroup$
Fix $kin 1,ldots,n$. We have
$$theta x_k + (1-theta)y_k leq theta max_i x_i + (1-theta)max_i y_i$$
because $x_k leq max_i x_i$, $y_k leq max_i y_i$, $theta geq 0$ and $1-theta geq 0$.
Since the statement above is true for any $k$ we have:
$$max_k [theta x_k + (1-theta)y_k]leq theta max_i x_i + (1-theta)max_i y_i.$$
answered Sep 19 '17 at 3:53
HugocitoHugocito
1,84411320
1,84411320
add a comment |
add a 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.
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%2f2435464%2fshow-that-max-function-on-mathbb-rn-is-convex%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