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
Convert seconds to minutes
What's the meaning of "Sollensaussagen"?
How do conventional missiles fly?
What is an equivalently powerful replacement spell for Yuan-Ti's Suggestion spell?
How can I prove that a state of equilibrium is unstable?
Mathematica command that allows it to read my intentions
Notepad++ delete until colon for every line with replace all
Avoiding the "not like other girls" trope?
Could neural networks be considered metaheuristics?
Were days ever written as ordinal numbers when writing day-month-year?
Does Dispel Magic work on Tiny Hut?
Why do I get negative height?
What historical events would have to change in order to make 19th century "steampunk" technology possible?
Did 'Cinema Songs' exist during Hiranyakshipu's time?
Why was the shrink from 8″ made only to 5.25″ and not smaller (4″ or less)
Obtaining database information and values in extended properties
Sums of two squares in arithmetic progressions
Do Iron Man suits sport waste management systems?
Finding the reason behind the value of the integral.
Placement of More Information/Help Icon button for Radio Buttons
Is there a hemisphere-neutral way of specifying a season?
Standard deduction V. mortgage interest deduction - is it basically only for the rich?
What are the G forces leaving Earth orbit?
Use of noexpand in the implementation of TextOrMath for eTeX
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
edited Mar 20 at 17:43
Rodrigo de Azevedo
13.1k41960
asked Sep 19 '17 at 3:31
hklelhklel
194110
$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
edited Mar 20 at 17:43
Rodrigo de Azevedo
13.1k41960
asked Sep 19 '17 at 3:31
hklelhklel
194110
$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
edited Mar 20 at 17:43
Rodrigo de Azevedo
13.1k41960
asked Sep 19 '17 at 3:31
hklelhklel
194110
$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
asked Sep 19 '17 at 3:31
hklelhklel
194110
edited Mar 20 at 17:43
Rodrigo de Azevedo
13.1k41960
asked Sep 19 '17 at 3:31
hklelhklel
194110
edited Mar 20 at 17:43
Rodrigo de Azevedo
13.1k41960
edited Mar 20 at 17:43
Rodrigo de Azevedo
13.1k41960
edited Mar 20 at 17:43
Rodrigo de Azevedo
13.1k41960
13.1k41960
asked Sep 19 '17 at 3:31
hklelhklel
194110
asked Sep 19 '17 at 3:31
hklelhklel
194110
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.$$
answered Sep 19 '17 at 3:53
HugocitoHugocito
1,84411320
$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.$$
answered Sep 19 '17 at 3:53
HugocitoHugocito
1,84411320
$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.$$
answered Sep 19 '17 at 3:53
HugocitoHugocito
1,84411320
$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.$$
answered Sep 19 '17 at 3:53
HugocitoHugocito
1,84411320
$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
answered Sep 19 '17 at 3:53
HugocitoHugocito
1,84411320
answered Sep 19 '17 at 3:53
HugocitoHugocito
1,84411320
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
