Mixing
How to maximize a piecewise linear convex function $f: mathbbR^nto mathbbR$?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
How to maximize a piecewise linear convex function $f: mathbbR^nto mathbbR$? I can see that there are many references for minimizing a piecewise linear convex function but not maximizing such a function. Is this problem so trivial or it is so hard (i.e., NP-hard)? I appreciate it if you could also give a reference/hint for maximizing such functions.
optimization convex-optimization linear-programming nonlinear-optimization piecewise-continuity
asked Aug 6 at 4:06
Opt
446110
add a comment |Â
up vote
0
down vote
favorite
How to maximize a piecewise linear convex function $f: mathbbR^nto mathbbR$? I can see that there are many references for minimizing a piecewise linear convex function but not maximizing such a function. Is this problem so trivial or it is so hard (i.e., NP-hard)? I appreciate it if you could also give a reference/hint for maximizing such functions.
optimization convex-optimization linear-programming nonlinear-optimization piecewise-continuity
asked Aug 6 at 4:06
Opt
446110
2
If the problem is no longer convex we use binary or SOS2 variables to model piecewise linear functions. This is used a lot in practice. Multi-dimensional functions that are not separable are difficult however.
– Erwin Kalvelagen
Aug 6 at 12:16
1
Maximizing a convex function over a convex set is NP-hard in general (and I believe the same holds, even for piecewise linear convex functions)
– David M.
Aug 8 at 2:22
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
How to maximize a piecewise linear convex function $f: mathbbR^nto mathbbR$? I can see that there are many references for minimizing a piecewise linear convex function but not maximizing such a function. Is this problem so trivial or it is so hard (i.e., NP-hard)? I appreciate it if you could also give a reference/hint for maximizing such functions.
optimization convex-optimization linear-programming nonlinear-optimization piecewise-continuity
asked Aug 6 at 4:06
Opt
446110
How to maximize a piecewise linear convex function $f: mathbbR^nto mathbbR$? I can see that there are many references for minimizing a piecewise linear convex function but not maximizing such a function. Is this problem so trivial or it is so hard (i.e., NP-hard)? I appreciate it if you could also give a reference/hint for maximizing such functions.
optimization convex-optimization linear-programming nonlinear-optimization piecewise-continuity
asked Aug 6 at 4:06
Opt
446110
edited Aug 6 at 4:11
asked Aug 6 at 4:06
Opt
446110
asked Aug 6 at 4:06
Opt
446110
asked Aug 6 at 4:06
Opt
446110
446110
2
If the problem is no longer convex we use binary or SOS2 variables to model piecewise linear functions. This is used a lot in practice. Multi-dimensional functions that are not separable are difficult however.
– Erwin Kalvelagen
Aug 6 at 12:16
1
Maximizing a convex function over a convex set is NP-hard in general (and I believe the same holds, even for piecewise linear convex functions)
– David M.
Aug 8 at 2:22
add a comment |Â
2
If the problem is no longer convex we use binary or SOS2 variables to model piecewise linear functions. This is used a lot in practice. Multi-dimensional functions that are not separable are difficult however.
– Erwin Kalvelagen
Aug 6 at 12:16
1
Maximizing a convex function over a convex set is NP-hard in general (and I believe the same holds, even for piecewise linear convex functions)
– David M.
Aug 8 at 2:22
2
2
If the problem is no longer convex we use binary or SOS2 variables to model piecewise linear functions. This is used a lot in practice. Multi-dimensional functions that are not separable are difficult however.
– Erwin Kalvelagen
Aug 6 at 12:16
If the problem is no longer convex we use binary or SOS2 variables to model piecewise linear functions. This is used a lot in practice. Multi-dimensional functions that are not separable are difficult however.
– Erwin Kalvelagen
Aug 6 at 12:16
1
1
Maximizing a convex function over a convex set is NP-hard in general (and I believe the same holds, even for piecewise linear convex functions)
– David M.
Aug 8 at 2:22
Maximizing a convex function over a convex set is NP-hard in general (and I believe the same holds, even for piecewise linear convex functions)
– David M.
Aug 8 at 2:22
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
Suppose your function is constant everywhere, then everywhere is a maximum.
Suppose it is not a constant and suppose it attains maximum value at $x_0$ with value $M$. Then consider $ x: f(x) < M$, which is a convex set that do not include $x_0$ but $x_0$ is a limit point for the set. If the set is empty, then we have a constant function. Suppose not, it means $x_0$ must be a boundary point, but your domain is unbounded. The maximum doesn't exist.
If your domain is bounded and the function is not constant, check the boundary to look for the maximum value.
answered Aug 6 at 4:29
Siong Thye Goh
78k134997
add a comment |Â
up vote
1
down vote
Convexity implies the epigraph is a convex set. A function with a maximum would imply that small deviations from the maximum would be lower than or equal to the maximum. Taking two points on either side of the maximum. If one of them is not equal to the maximum then the line connecting the two points on either side of the maximum will be less than the maximum so at the point where the maximum is obtained the line would be outside the epigraph contradicting convexity. The only other possibility is that all values are the same, which is to say the function is constant. This class of functions is certainly easy to maximize, so the problem is trivial.
answered Aug 6 at 4:32
CyclotomicField
1,3311211
add a comment |Â
up vote
0
down vote
If your problem is to maximize a convex function with no constraints, then the solution is trivially $+infty$, unless the function is constant everywhere, in which case the solution is the constant value.
answered Aug 6 at 22:59
Jonathan Tuck
113
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Suppose your function is constant everywhere, then everywhere is a maximum.
Suppose it is not a constant and suppose it attains maximum value at $x_0$ with value $M$. Then consider $ x: f(x) < M$, which is a convex set that do not include $x_0$ but $x_0$ is a limit point for the set. If the set is empty, then we have a constant function. Suppose not, it means $x_0$ must be a boundary point, but your domain is unbounded. The maximum doesn't exist.
If your domain is bounded and the function is not constant, check the boundary to look for the maximum value.
answered Aug 6 at 4:29
Siong Thye Goh
78k134997
add a comment |Â
up vote
3
down vote
accepted
Suppose your function is constant everywhere, then everywhere is a maximum.
Suppose it is not a constant and suppose it attains maximum value at $x_0$ with value $M$. Then consider $ x: f(x) < M$, which is a convex set that do not include $x_0$ but $x_0$ is a limit point for the set. If the set is empty, then we have a constant function. Suppose not, it means $x_0$ must be a boundary point, but your domain is unbounded. The maximum doesn't exist.
If your domain is bounded and the function is not constant, check the boundary to look for the maximum value.
answered Aug 6 at 4:29
Siong Thye Goh
78k134997
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Suppose your function is constant everywhere, then everywhere is a maximum.
Suppose it is not a constant and suppose it attains maximum value at $x_0$ with value $M$. Then consider $ x: f(x) < M$, which is a convex set that do not include $x_0$ but $x_0$ is a limit point for the set. If the set is empty, then we have a constant function. Suppose not, it means $x_0$ must be a boundary point, but your domain is unbounded. The maximum doesn't exist.
If your domain is bounded and the function is not constant, check the boundary to look for the maximum value.
answered Aug 6 at 4:29
Siong Thye Goh
78k134997
Suppose your function is constant everywhere, then everywhere is a maximum.
Suppose it is not a constant and suppose it attains maximum value at $x_0$ with value $M$. Then consider $ x: f(x) < M$, which is a convex set that do not include $x_0$ but $x_0$ is a limit point for the set. If the set is empty, then we have a constant function. Suppose not, it means $x_0$ must be a boundary point, but your domain is unbounded. The maximum doesn't exist.
If your domain is bounded and the function is not constant, check the boundary to look for the maximum value.
answered Aug 6 at 4:29
Siong Thye Goh
78k134997
answered Aug 6 at 4:29
Siong Thye Goh
78k134997
answered Aug 6 at 4:29
Siong Thye Goh
78k134997
answered Aug 6 at 4:29
Siong Thye Goh
78k134997
78k134997
add a comment |Â
add a comment |Â
up vote
1
down vote
Convexity implies the epigraph is a convex set. A function with a maximum would imply that small deviations from the maximum would be lower than or equal to the maximum. Taking two points on either side of the maximum. If one of them is not equal to the maximum then the line connecting the two points on either side of the maximum will be less than the maximum so at the point where the maximum is obtained the line would be outside the epigraph contradicting convexity. The only other possibility is that all values are the same, which is to say the function is constant. This class of functions is certainly easy to maximize, so the problem is trivial.
answered Aug 6 at 4:32
CyclotomicField
1,3311211
add a comment |Â
up vote
1
down vote
Convexity implies the epigraph is a convex set. A function with a maximum would imply that small deviations from the maximum would be lower than or equal to the maximum. Taking two points on either side of the maximum. If one of them is not equal to the maximum then the line connecting the two points on either side of the maximum will be less than the maximum so at the point where the maximum is obtained the line would be outside the epigraph contradicting convexity. The only other possibility is that all values are the same, which is to say the function is constant. This class of functions is certainly easy to maximize, so the problem is trivial.
answered Aug 6 at 4:32
CyclotomicField
1,3311211
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Convexity implies the epigraph is a convex set. A function with a maximum would imply that small deviations from the maximum would be lower than or equal to the maximum. Taking two points on either side of the maximum. If one of them is not equal to the maximum then the line connecting the two points on either side of the maximum will be less than the maximum so at the point where the maximum is obtained the line would be outside the epigraph contradicting convexity. The only other possibility is that all values are the same, which is to say the function is constant. This class of functions is certainly easy to maximize, so the problem is trivial.
answered Aug 6 at 4:32
CyclotomicField
1,3311211
Convexity implies the epigraph is a convex set. A function with a maximum would imply that small deviations from the maximum would be lower than or equal to the maximum. Taking two points on either side of the maximum. If one of them is not equal to the maximum then the line connecting the two points on either side of the maximum will be less than the maximum so at the point where the maximum is obtained the line would be outside the epigraph contradicting convexity. The only other possibility is that all values are the same, which is to say the function is constant. This class of functions is certainly easy to maximize, so the problem is trivial.
answered Aug 6 at 4:32
CyclotomicField
1,3311211
answered Aug 6 at 4:32
CyclotomicField
1,3311211
answered Aug 6 at 4:32
CyclotomicField
1,3311211
answered Aug 6 at 4:32
CyclotomicField
1,3311211
1,3311211
add a comment |Â
add a comment |Â
up vote
0
down vote
If your problem is to maximize a convex function with no constraints, then the solution is trivially $+infty$, unless the function is constant everywhere, in which case the solution is the constant value.
answered Aug 6 at 22:59
Jonathan Tuck
113
add a comment |Â
up vote
0
down vote
If your problem is to maximize a convex function with no constraints, then the solution is trivially $+infty$, unless the function is constant everywhere, in which case the solution is the constant value.
answered Aug 6 at 22:59
Jonathan Tuck
113
add a comment |Â
up vote
0
down vote
up vote
0
down vote
If your problem is to maximize a convex function with no constraints, then the solution is trivially $+infty$, unless the function is constant everywhere, in which case the solution is the constant value.
answered Aug 6 at 22:59
Jonathan Tuck
113
If your problem is to maximize a convex function with no constraints, then the solution is trivially $+infty$, unless the function is constant everywhere, in which case the solution is the constant value.
answered Aug 6 at 22:59
Jonathan Tuck
113
answered Aug 6 at 22:59
Jonathan Tuck
113
answered Aug 6 at 22:59
Jonathan Tuck
113
answered Aug 6 at 22:59
Jonathan Tuck
113
113
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873574%2fhow-to-maximize-a-piecewise-linear-convex-function-f-mathbbrn-to-mathbbr%23new-answer', 'question_page');
);
Post as a guest
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
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
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
2
If the problem is no longer convex we use binary or SOS2 variables to model piecewise linear functions. This is used a lot in practice. Multi-dimensional functions that are not separable are difficult however.
– Erwin Kalvelagen
Aug 6 at 12:16
1
Maximizing a convex function over a convex set is NP-hard in general (and I believe the same holds, even for piecewise linear convex functions)
– David M.
Aug 8 at 2:22