Mixing
Convex optimization with non-convex objective function
$begingroup$
Consider the following optimization problem:
$$ min_x quad x^3 quad text{s.t.} quad xgeq0 $$
We know that the objective function $x^3$ is not a convex function for $xinRe$. But we know that it is convex for $xinRe^+$
So my question is:
Can we define the above problem, a convex optimization problem?
To make it general:
Is it necessary for the objective function to be convex over its domain? or is it sufficient for the objective function to be convex only over the feasible set, in order to classify the problem as a convex optimization problem?
I have searched a lot for this question and everywhere,both on the textbooks and internet, the answer is that the objective function "MUST" be convex. But I think that we can consider these problems as convex.
convex-optimization
asked Nov 20 '16 at 7:47
Mohammadreza BarazeshMohammadreza Barazesh
163
$endgroup$
add a comment |
$begingroup$
Consider the following optimization problem:
$$ min_x quad x^3 quad text{s.t.} quad xgeq0 $$
We know that the objective function $x^3$ is not a convex function for $xinRe$. But we know that it is convex for $xinRe^+$
So my question is:
Can we define the above problem, a convex optimization problem?
To make it general:
Is it necessary for the objective function to be convex over its domain? or is it sufficient for the objective function to be convex only over the feasible set, in order to classify the problem as a convex optimization problem?
I have searched a lot for this question and everywhere,both on the textbooks and internet, the answer is that the objective function "MUST" be convex. But I think that we can consider these problems as convex.
convex-optimization
asked Nov 20 '16 at 7:47
Mohammadreza BarazeshMohammadreza Barazesh
163
$endgroup$
1
$begingroup$
The problem is certainly convex as you can redefine the objective to by $+infty$ when $x$ is not in the feasible set. However, some algorithms may require the objective to be convex everywhere.
$endgroup$
– copper.hat
Nov 20 '16 at 8:24
$begingroup$
@copper.hat in this instance I'd prefer rewriting that objective as $max{x,0}^3$, so you get monotonicity as well as convexity.
$endgroup$
– Michael Grant
Nov 25 '16 at 19:59
$begingroup$
@MichaelGrant: Yes, that would be a better approach here.
$endgroup$
– copper.hat
Nov 26 '16 at 2:31
add a comment |
$begingroup$
Consider the following optimization problem:
$$ min_x quad x^3 quad text{s.t.} quad xgeq0 $$
We know that the objective function $x^3$ is not a convex function for $xinRe$. But we know that it is convex for $xinRe^+$
So my question is:
Can we define the above problem, a convex optimization problem?
To make it general:
Is it necessary for the objective function to be convex over its domain? or is it sufficient for the objective function to be convex only over the feasible set, in order to classify the problem as a convex optimization problem?
I have searched a lot for this question and everywhere,both on the textbooks and internet, the answer is that the objective function "MUST" be convex. But I think that we can consider these problems as convex.
convex-optimization
asked Nov 20 '16 at 7:47
Mohammadreza BarazeshMohammadreza Barazesh
163
$endgroup$
Consider the following optimization problem:
$$ min_x quad x^3 quad text{s.t.} quad xgeq0 $$
We know that the objective function $x^3$ is not a convex function for $xinRe$. But we know that it is convex for $xinRe^+$
So my question is:
Can we define the above problem, a convex optimization problem?
To make it general:
Is it necessary for the objective function to be convex over its domain? or is it sufficient for the objective function to be convex only over the feasible set, in order to classify the problem as a convex optimization problem?
I have searched a lot for this question and everywhere,both on the textbooks and internet, the answer is that the objective function "MUST" be convex. But I think that we can consider these problems as convex.
convex-optimization
convex-optimization
asked Nov 20 '16 at 7:47
Mohammadreza BarazeshMohammadreza Barazesh
163
asked Nov 20 '16 at 7:47
Mohammadreza BarazeshMohammadreza Barazesh
163
asked Nov 20 '16 at 7:47
Mohammadreza BarazeshMohammadreza Barazesh
163
asked Nov 20 '16 at 7:47
Mohammadreza BarazeshMohammadreza Barazesh
163
asked Nov 20 '16 at 7:47
Mohammadreza BarazeshMohammadreza Barazesh
163
163
1
$begingroup$
The problem is certainly convex as you can redefine the objective to by $+infty$ when $x$ is not in the feasible set. However, some algorithms may require the objective to be convex everywhere.
$endgroup$
– copper.hat
Nov 20 '16 at 8:24
$begingroup$
@copper.hat in this instance I'd prefer rewriting that objective as $max{x,0}^3$, so you get monotonicity as well as convexity.
$endgroup$
– Michael Grant
Nov 25 '16 at 19:59
$begingroup$
@MichaelGrant: Yes, that would be a better approach here.
$endgroup$
– copper.hat
Nov 26 '16 at 2:31
add a comment |
1
$begingroup$
The problem is certainly convex as you can redefine the objective to by $+infty$ when $x$ is not in the feasible set. However, some algorithms may require the objective to be convex everywhere.
$endgroup$
– copper.hat
Nov 20 '16 at 8:24
$begingroup$
@copper.hat in this instance I'd prefer rewriting that objective as $max{x,0}^3$, so you get monotonicity as well as convexity.
$endgroup$
– Michael Grant
Nov 25 '16 at 19:59
$begingroup$
@MichaelGrant: Yes, that would be a better approach here.
$endgroup$
– copper.hat
Nov 26 '16 at 2:31
1
1
$begingroup$
The problem is certainly convex as you can redefine the objective to by $+infty$ when $x$ is not in the feasible set. However, some algorithms may require the objective to be convex everywhere.
$endgroup$
– copper.hat
Nov 20 '16 at 8:24
$begingroup$
The problem is certainly convex as you can redefine the objective to by $+infty$ when $x$ is not in the feasible set. However, some algorithms may require the objective to be convex everywhere.
$endgroup$
– copper.hat
Nov 20 '16 at 8:24
$begingroup$
@copper.hat in this instance I'd prefer rewriting that objective as $max{x,0}^3$, so you get monotonicity as well as convexity.
$endgroup$
– Michael Grant
Nov 25 '16 at 19:59
$begingroup$
@copper.hat in this instance I'd prefer rewriting that objective as $max{x,0}^3$, so you get monotonicity as well as convexity.
$endgroup$
– Michael Grant
Nov 25 '16 at 19:59
$begingroup$
@MichaelGrant: Yes, that would be a better approach here.
$endgroup$
– copper.hat
Nov 26 '16 at 2:31
$begingroup$
@MichaelGrant: Yes, that would be a better approach here.
$endgroup$
– copper.hat
Nov 26 '16 at 2:31
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Few optimization algorithms only require the objective/constraint functions to be convex merely over the feasible set. Feasible interior point solvers (IPMs) are a good example. Most solvers however (like infeasible IPMs and SQPs), which btw are more efficient than feasible IPMs since they do not require a feasible starting point and can take longer Newton steps, require your functions to be convex everywhere (and finite valued, so "tricking" the solver by taking the value $+infty$ outside the feasible region does not help).
However, most solvers satisfy box constraints (like $xgeq 0$) in all iterations, so the problem you pose will be solved by most convex optimization solvers.
answered Nov 20 '16 at 11:16
LinAlgLinAlg
10k1521
$endgroup$
$begingroup$
Thanks for your help. But I just used that example to demonstrate what I mean. My real question is about the general case, e.g. when the other constraints like $g(x) leq 0$ limit the feasible set to an area in which the objective function is convex. What happens if I use one of the "infeasible solvers" to solve such problems?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 12:23
$begingroup$
Such solvers may not converge to a feasible point. If they do, and if the convergence is from outside the feasible region to the boundary, that point may not be optimal.
$endgroup$
– LinAlg
Nov 20 '16 at 12:59
$begingroup$
I am confused. Assuming that the objective function is convex over the feasible set, is it possible for a point to be inside the feasible set, satisfy first and second order conditions and still not be the optimal solution?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 14:08
$begingroup$
A point that satisfies first and second order conditions but is not optimal could be on the boundary (but not in the interior).
$endgroup$
– LinAlg
Nov 20 '16 at 14:35
1
$begingroup$
@MichaelGrant As opposed to feasible or primal IPMs. Also E.D. Andersen (MOSEK) in this chapter: "The computationally most attractive IPM is an infeasible-primal-dual algorithm Indeed it has been implemented in all commercial software packages".
$endgroup$
– LinAlg
Nov 25 '16 at 23:41
|
show 5 more comments
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%2f2022295%2fconvex-optimization-with-non-convex-objective-function%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$
Few optimization algorithms only require the objective/constraint functions to be convex merely over the feasible set. Feasible interior point solvers (IPMs) are a good example. Most solvers however (like infeasible IPMs and SQPs), which btw are more efficient than feasible IPMs since they do not require a feasible starting point and can take longer Newton steps, require your functions to be convex everywhere (and finite valued, so "tricking" the solver by taking the value $+infty$ outside the feasible region does not help).
However, most solvers satisfy box constraints (like $xgeq 0$) in all iterations, so the problem you pose will be solved by most convex optimization solvers.
answered Nov 20 '16 at 11:16
LinAlgLinAlg
10k1521
$endgroup$
$begingroup$
Thanks for your help. But I just used that example to demonstrate what I mean. My real question is about the general case, e.g. when the other constraints like $g(x) leq 0$ limit the feasible set to an area in which the objective function is convex. What happens if I use one of the "infeasible solvers" to solve such problems?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 12:23
$begingroup$
Such solvers may not converge to a feasible point. If they do, and if the convergence is from outside the feasible region to the boundary, that point may not be optimal.
$endgroup$
– LinAlg
Nov 20 '16 at 12:59
$begingroup$
I am confused. Assuming that the objective function is convex over the feasible set, is it possible for a point to be inside the feasible set, satisfy first and second order conditions and still not be the optimal solution?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 14:08
$begingroup$
A point that satisfies first and second order conditions but is not optimal could be on the boundary (but not in the interior).
$endgroup$
– LinAlg
Nov 20 '16 at 14:35
1
$begingroup$
@MichaelGrant As opposed to feasible or primal IPMs. Also E.D. Andersen (MOSEK) in this chapter: "The computationally most attractive IPM is an infeasible-primal-dual algorithm Indeed it has been implemented in all commercial software packages".
$endgroup$
– LinAlg
Nov 25 '16 at 23:41
|
show 5 more comments
$begingroup$
Few optimization algorithms only require the objective/constraint functions to be convex merely over the feasible set. Feasible interior point solvers (IPMs) are a good example. Most solvers however (like infeasible IPMs and SQPs), which btw are more efficient than feasible IPMs since they do not require a feasible starting point and can take longer Newton steps, require your functions to be convex everywhere (and finite valued, so "tricking" the solver by taking the value $+infty$ outside the feasible region does not help).
However, most solvers satisfy box constraints (like $xgeq 0$) in all iterations, so the problem you pose will be solved by most convex optimization solvers.
answered Nov 20 '16 at 11:16
LinAlgLinAlg
10k1521
$endgroup$
$begingroup$
Thanks for your help. But I just used that example to demonstrate what I mean. My real question is about the general case, e.g. when the other constraints like $g(x) leq 0$ limit the feasible set to an area in which the objective function is convex. What happens if I use one of the "infeasible solvers" to solve such problems?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 12:23
$begingroup$
Such solvers may not converge to a feasible point. If they do, and if the convergence is from outside the feasible region to the boundary, that point may not be optimal.
$endgroup$
– LinAlg
Nov 20 '16 at 12:59
$begingroup$
I am confused. Assuming that the objective function is convex over the feasible set, is it possible for a point to be inside the feasible set, satisfy first and second order conditions and still not be the optimal solution?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 14:08
$begingroup$
A point that satisfies first and second order conditions but is not optimal could be on the boundary (but not in the interior).
$endgroup$
– LinAlg
Nov 20 '16 at 14:35
1
$begingroup$
@MichaelGrant As opposed to feasible or primal IPMs. Also E.D. Andersen (MOSEK) in this chapter: "The computationally most attractive IPM is an infeasible-primal-dual algorithm Indeed it has been implemented in all commercial software packages".
$endgroup$
– LinAlg
Nov 25 '16 at 23:41
|
show 5 more comments
$begingroup$
Few optimization algorithms only require the objective/constraint functions to be convex merely over the feasible set. Feasible interior point solvers (IPMs) are a good example. Most solvers however (like infeasible IPMs and SQPs), which btw are more efficient than feasible IPMs since they do not require a feasible starting point and can take longer Newton steps, require your functions to be convex everywhere (and finite valued, so "tricking" the solver by taking the value $+infty$ outside the feasible region does not help).
However, most solvers satisfy box constraints (like $xgeq 0$) in all iterations, so the problem you pose will be solved by most convex optimization solvers.
answered Nov 20 '16 at 11:16
LinAlgLinAlg
10k1521
$endgroup$
Few optimization algorithms only require the objective/constraint functions to be convex merely over the feasible set. Feasible interior point solvers (IPMs) are a good example. Most solvers however (like infeasible IPMs and SQPs), which btw are more efficient than feasible IPMs since they do not require a feasible starting point and can take longer Newton steps, require your functions to be convex everywhere (and finite valued, so "tricking" the solver by taking the value $+infty$ outside the feasible region does not help).
However, most solvers satisfy box constraints (like $xgeq 0$) in all iterations, so the problem you pose will be solved by most convex optimization solvers.
answered Nov 20 '16 at 11:16
LinAlgLinAlg
10k1521
answered Nov 20 '16 at 11:16
LinAlgLinAlg
10k1521
answered Nov 20 '16 at 11:16
LinAlgLinAlg
10k1521
answered Nov 20 '16 at 11:16
LinAlgLinAlg
10k1521
10k1521
$begingroup$
Thanks for your help. But I just used that example to demonstrate what I mean. My real question is about the general case, e.g. when the other constraints like $g(x) leq 0$ limit the feasible set to an area in which the objective function is convex. What happens if I use one of the "infeasible solvers" to solve such problems?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 12:23
$begingroup$
Such solvers may not converge to a feasible point. If they do, and if the convergence is from outside the feasible region to the boundary, that point may not be optimal.
$endgroup$
– LinAlg
Nov 20 '16 at 12:59
$begingroup$
I am confused. Assuming that the objective function is convex over the feasible set, is it possible for a point to be inside the feasible set, satisfy first and second order conditions and still not be the optimal solution?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 14:08
$begingroup$
A point that satisfies first and second order conditions but is not optimal could be on the boundary (but not in the interior).
$endgroup$
– LinAlg
Nov 20 '16 at 14:35
1
$begingroup$
@MichaelGrant As opposed to feasible or primal IPMs. Also E.D. Andersen (MOSEK) in this chapter: "The computationally most attractive IPM is an infeasible-primal-dual algorithm Indeed it has been implemented in all commercial software packages".
$endgroup$
– LinAlg
Nov 25 '16 at 23:41
|
show 5 more comments
$begingroup$
Thanks for your help. But I just used that example to demonstrate what I mean. My real question is about the general case, e.g. when the other constraints like $g(x) leq 0$ limit the feasible set to an area in which the objective function is convex. What happens if I use one of the "infeasible solvers" to solve such problems?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 12:23
$begingroup$
Such solvers may not converge to a feasible point. If they do, and if the convergence is from outside the feasible region to the boundary, that point may not be optimal.
$endgroup$
– LinAlg
Nov 20 '16 at 12:59
$begingroup$
I am confused. Assuming that the objective function is convex over the feasible set, is it possible for a point to be inside the feasible set, satisfy first and second order conditions and still not be the optimal solution?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 14:08
$begingroup$
A point that satisfies first and second order conditions but is not optimal could be on the boundary (but not in the interior).
$endgroup$
– LinAlg
Nov 20 '16 at 14:35
1
$begingroup$
@MichaelGrant As opposed to feasible or primal IPMs. Also E.D. Andersen (MOSEK) in this chapter: "The computationally most attractive IPM is an infeasible-primal-dual algorithm Indeed it has been implemented in all commercial software packages".
$endgroup$
– LinAlg
Nov 25 '16 at 23:41
$begingroup$
Thanks for your help. But I just used that example to demonstrate what I mean. My real question is about the general case, e.g. when the other constraints like $g(x) leq 0$ limit the feasible set to an area in which the objective function is convex. What happens if I use one of the "infeasible solvers" to solve such problems?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 12:23
$begingroup$
Thanks for your help. But I just used that example to demonstrate what I mean. My real question is about the general case, e.g. when the other constraints like $g(x) leq 0$ limit the feasible set to an area in which the objective function is convex. What happens if I use one of the "infeasible solvers" to solve such problems?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 12:23
$begingroup$
Such solvers may not converge to a feasible point. If they do, and if the convergence is from outside the feasible region to the boundary, that point may not be optimal.
$endgroup$
– LinAlg
Nov 20 '16 at 12:59
$begingroup$
Such solvers may not converge to a feasible point. If they do, and if the convergence is from outside the feasible region to the boundary, that point may not be optimal.
$endgroup$
– LinAlg
Nov 20 '16 at 12:59
$begingroup$
I am confused. Assuming that the objective function is convex over the feasible set, is it possible for a point to be inside the feasible set, satisfy first and second order conditions and still not be the optimal solution?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 14:08
$begingroup$
I am confused. Assuming that the objective function is convex over the feasible set, is it possible for a point to be inside the feasible set, satisfy first and second order conditions and still not be the optimal solution?
$endgroup$
– Mohammadreza Barazesh
Nov 20 '16 at 14:08
$begingroup$
A point that satisfies first and second order conditions but is not optimal could be on the boundary (but not in the interior).
$endgroup$
– LinAlg
Nov 20 '16 at 14:35
$begingroup$
A point that satisfies first and second order conditions but is not optimal could be on the boundary (but not in the interior).
$endgroup$
– LinAlg
Nov 20 '16 at 14:35
1
1
$begingroup$
@MichaelGrant As opposed to feasible or primal IPMs. Also E.D. Andersen (MOSEK) in this chapter: "The computationally most attractive IPM is an infeasible-primal-dual algorithm Indeed it has been implemented in all commercial software packages".
$endgroup$
– LinAlg
Nov 25 '16 at 23:41
$begingroup$
@MichaelGrant As opposed to feasible or primal IPMs. Also E.D. Andersen (MOSEK) in this chapter: "The computationally most attractive IPM is an infeasible-primal-dual algorithm Indeed it has been implemented in all commercial software packages".
$endgroup$
– LinAlg
Nov 25 '16 at 23:41
|
show 5 more comments
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%2f2022295%2fconvex-optimization-with-non-convex-objective-function%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
1
$begingroup$
The problem is certainly convex as you can redefine the objective to by $+infty$ when $x$ is not in the feasible set. However, some algorithms may require the objective to be convex everywhere.
$endgroup$
– copper.hat
Nov 20 '16 at 8:24
$begingroup$
@copper.hat in this instance I'd prefer rewriting that objective as $max{x,0}^3$, so you get monotonicity as well as convexity.
$endgroup$
– Michael Grant
Nov 25 '16 at 19:59
$begingroup$
@MichaelGrant: Yes, that would be a better approach here.
$endgroup$
– copper.hat
Nov 26 '16 at 2:31