Mixing
What is the correct change of variables to yield convexity in this nonlinear optimization problem?
$begingroup$
$$
text{min. } x/y \
text{s.t. } 2leq x leq 3 \
x^2+y/zleq sqrt{y} \
x/y=z^2 \
x,y,zgeq 0
$$
To transform this problem into a nonlinear convex optimization problem, both the objective function and constraints must be convex.
If we simply let $x/y=z^2$ in the objective function as given by the constraint, the objective function becomes convex.
Letting new variable $q=1/y$ gives $z^2-xq=0$ for the third constraint, which is convex (provable by definition & the inequality of arithmetic & geometric means).
However this gives the ugly $x^2+1/zq leq 1/sqrt{q}$ for the second constraint.
A different approach of substituting the third constraint, $x=yz^2$, into the second constraint, gives $zx^2+x/z^2leq sqrt{x}$, no closer to convexity.
Is there a different substitution involving $y$ that gives convex constraints 2 and 3?
convex-optimization transformation nonlinear-optimization geometric-programming
edited Jan 29 at 9:13
Rodrigo de Azevedo
13k41960
asked Nov 11 '14 at 23:30
Brendan MurphyBrendan Murphy
83
$endgroup$
add a comment |
$begingroup$
$$
text{min. } x/y \
text{s.t. } 2leq x leq 3 \
x^2+y/zleq sqrt{y} \
x/y=z^2 \
x,y,zgeq 0
$$
To transform this problem into a nonlinear convex optimization problem, both the objective function and constraints must be convex.
If we simply let $x/y=z^2$ in the objective function as given by the constraint, the objective function becomes convex.
Letting new variable $q=1/y$ gives $z^2-xq=0$ for the third constraint, which is convex (provable by definition & the inequality of arithmetic & geometric means).
However this gives the ugly $x^2+1/zq leq 1/sqrt{q}$ for the second constraint.
A different approach of substituting the third constraint, $x=yz^2$, into the second constraint, gives $zx^2+x/z^2leq sqrt{x}$, no closer to convexity.
Is there a different substitution involving $y$ that gives convex constraints 2 and 3?
convex-optimization transformation nonlinear-optimization geometric-programming
edited Jan 29 at 9:13
Rodrigo de Azevedo
13k41960
asked Nov 11 '14 at 23:30
Brendan MurphyBrendan Murphy
83
$endgroup$
add a comment |
$begingroup$
$$
text{min. } x/y \
text{s.t. } 2leq x leq 3 \
x^2+y/zleq sqrt{y} \
x/y=z^2 \
x,y,zgeq 0
$$
To transform this problem into a nonlinear convex optimization problem, both the objective function and constraints must be convex.
If we simply let $x/y=z^2$ in the objective function as given by the constraint, the objective function becomes convex.
Letting new variable $q=1/y$ gives $z^2-xq=0$ for the third constraint, which is convex (provable by definition & the inequality of arithmetic & geometric means).
However this gives the ugly $x^2+1/zq leq 1/sqrt{q}$ for the second constraint.
A different approach of substituting the third constraint, $x=yz^2$, into the second constraint, gives $zx^2+x/z^2leq sqrt{x}$, no closer to convexity.
Is there a different substitution involving $y$ that gives convex constraints 2 and 3?
convex-optimization transformation nonlinear-optimization geometric-programming
edited Jan 29 at 9:13
Rodrigo de Azevedo
13k41960
asked Nov 11 '14 at 23:30
Brendan MurphyBrendan Murphy
83
$endgroup$
$$
text{min. } x/y \
text{s.t. } 2leq x leq 3 \
x^2+y/zleq sqrt{y} \
x/y=z^2 \
x,y,zgeq 0
$$
To transform this problem into a nonlinear convex optimization problem, both the objective function and constraints must be convex.
If we simply let $x/y=z^2$ in the objective function as given by the constraint, the objective function becomes convex.
Letting new variable $q=1/y$ gives $z^2-xq=0$ for the third constraint, which is convex (provable by definition & the inequality of arithmetic & geometric means).
However this gives the ugly $x^2+1/zq leq 1/sqrt{q}$ for the second constraint.
A different approach of substituting the third constraint, $x=yz^2$, into the second constraint, gives $zx^2+x/z^2leq sqrt{x}$, no closer to convexity.
Is there a different substitution involving $y$ that gives convex constraints 2 and 3?
convex-optimization transformation nonlinear-optimization geometric-programming
convex-optimization transformation nonlinear-optimization geometric-programming
edited Jan 29 at 9:13
Rodrigo de Azevedo
13k41960
asked Nov 11 '14 at 23:30
Brendan MurphyBrendan Murphy
83
edited Jan 29 at 9:13
Rodrigo de Azevedo
13k41960
asked Nov 11 '14 at 23:30
Brendan MurphyBrendan Murphy
83
edited Jan 29 at 9:13
Rodrigo de Azevedo
13k41960
edited Jan 29 at 9:13
Rodrigo de Azevedo
13k41960
edited Jan 29 at 9:13
Rodrigo de Azevedo
13k41960
13k41960
asked Nov 11 '14 at 23:30
Brendan MurphyBrendan Murphy
83
asked Nov 11 '14 at 23:30
Brendan MurphyBrendan Murphy
83
asked Nov 11 '14 at 23:30
Brendan MurphyBrendan Murphy
83
83
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You're in luck: this is a geometric program. Therefore, the change of variables $$xrightarrow e^{u}, ~~ yrightarrow e^{v}, ~~ zrightarrow e^{w}$$
will get us close, and a few logarithms will get us the rest of the way there. Substitution yields
begin{array}{ll}
text{minimize} & e^{u-v} \
text{subject to} & 2 leq e^u leq 3 \
& e^{2u} + e^{v-w} leq e^{v/2} \
& e^{u-v}=e^{2w} end{array}
Now let's take some logarithms:
begin{array}{ll}
text{minimize} & u-v \
text{subject to} & log 2 leq u leq log 3 \
& log left( e^{2u} + e^{v-w} right) leq v/2 \
& u-v=2w end{array}
And there you have it: a convex optimization problem. The "log-sum-exp" expression is indeed a smooth convex function; you'll have to take that on faith or prove it to yourself. Recovering $x,y,z$ once you have solved for $u,v,w$ just requires three exponentials.
Some notes:
We could skip a few of the logarithms and still have a convex problem: the objective, the $e^uleq 3$ constraint, the nonlinear inequality. But in practice we keep those logarithms in there; the problems are better behaved numerically that way. (I have no theoretical support for this; someone else might, though). The other logarithms must be taken, however.
Strictly speaking, the convex version of this model is equivalent only if we assume strict positivity on $x,y,z$. Yes, you can handle the case of zero variables with more technical machinery; but fortunately we don't need that here. After all, $xgeq 2$ is guaranteed from the constraints; and $y$ cannot be zero unless the entire problem is infeasible, because of the $x/y$ objective. And therefore, from the $x/y=z^2$ constraint, we know that $z$ is nonzero as well.
If we wish we can eliminate $z$ and $w$ altogether, by taking advantage of the equality constraint, to yield
begin{array}{lllll}
text{minimize} & x/y & &
text{minimize} & u-v \
text{subject to} & 2 leq x leq 3 & &
text{subject to} & log 2 leq u leq log 3 \
& x^2 + y^{3/2} x^{-1/2} leq y^{1/2} &&
& log left( e^{2u} + e^{(3v-u)/2} right) leq v/2 \
end{array}
I cannot emphasize the following enough, but I am going to try:
Under no circumstances should one assume that a nonconvex problem can be made
convex if only you can find the right change of variables.
The title of this question suggests the author is making this assumption. Perhaps that's because this problem was assigned as a homework or test question, in which case it was known in advance by the question designer to be a geometric program. But geometric programs are the exception, not the rule. I'm unaware of any other general, non-manufactured class of nonconvex problems that can be made convex with just a change of variables.
answered Nov 12 '14 at 1:56
Michael GrantMichael Grant
15.1k12045
$endgroup$
add a comment |
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%2f1017667%2fwhat-is-the-correct-change-of-variables-to-yield-convexity-in-this-nonlinear-opt%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$
You're in luck: this is a geometric program. Therefore, the change of variables $$xrightarrow e^{u}, ~~ yrightarrow e^{v}, ~~ zrightarrow e^{w}$$
will get us close, and a few logarithms will get us the rest of the way there. Substitution yields
begin{array}{ll}
text{minimize} & e^{u-v} \
text{subject to} & 2 leq e^u leq 3 \
& e^{2u} + e^{v-w} leq e^{v/2} \
& e^{u-v}=e^{2w} end{array}
Now let's take some logarithms:
begin{array}{ll}
text{minimize} & u-v \
text{subject to} & log 2 leq u leq log 3 \
& log left( e^{2u} + e^{v-w} right) leq v/2 \
& u-v=2w end{array}
And there you have it: a convex optimization problem. The "log-sum-exp" expression is indeed a smooth convex function; you'll have to take that on faith or prove it to yourself. Recovering $x,y,z$ once you have solved for $u,v,w$ just requires three exponentials.
Some notes:
We could skip a few of the logarithms and still have a convex problem: the objective, the $e^uleq 3$ constraint, the nonlinear inequality. But in practice we keep those logarithms in there; the problems are better behaved numerically that way. (I have no theoretical support for this; someone else might, though). The other logarithms must be taken, however.
Strictly speaking, the convex version of this model is equivalent only if we assume strict positivity on $x,y,z$. Yes, you can handle the case of zero variables with more technical machinery; but fortunately we don't need that here. After all, $xgeq 2$ is guaranteed from the constraints; and $y$ cannot be zero unless the entire problem is infeasible, because of the $x/y$ objective. And therefore, from the $x/y=z^2$ constraint, we know that $z$ is nonzero as well.
If we wish we can eliminate $z$ and $w$ altogether, by taking advantage of the equality constraint, to yield
begin{array}{lllll}
text{minimize} & x/y & &
text{minimize} & u-v \
text{subject to} & 2 leq x leq 3 & &
text{subject to} & log 2 leq u leq log 3 \
& x^2 + y^{3/2} x^{-1/2} leq y^{1/2} &&
& log left( e^{2u} + e^{(3v-u)/2} right) leq v/2 \
end{array}
I cannot emphasize the following enough, but I am going to try:
Under no circumstances should one assume that a nonconvex problem can be made
convex if only you can find the right change of variables.
The title of this question suggests the author is making this assumption. Perhaps that's because this problem was assigned as a homework or test question, in which case it was known in advance by the question designer to be a geometric program. But geometric programs are the exception, not the rule. I'm unaware of any other general, non-manufactured class of nonconvex problems that can be made convex with just a change of variables.
answered Nov 12 '14 at 1:56
Michael GrantMichael Grant
15.1k12045
$endgroup$
add a comment |
$begingroup$
You're in luck: this is a geometric program. Therefore, the change of variables $$xrightarrow e^{u}, ~~ yrightarrow e^{v}, ~~ zrightarrow e^{w}$$
will get us close, and a few logarithms will get us the rest of the way there. Substitution yields
begin{array}{ll}
text{minimize} & e^{u-v} \
text{subject to} & 2 leq e^u leq 3 \
& e^{2u} + e^{v-w} leq e^{v/2} \
& e^{u-v}=e^{2w} end{array}
Now let's take some logarithms:
begin{array}{ll}
text{minimize} & u-v \
text{subject to} & log 2 leq u leq log 3 \
& log left( e^{2u} + e^{v-w} right) leq v/2 \
& u-v=2w end{array}
And there you have it: a convex optimization problem. The "log-sum-exp" expression is indeed a smooth convex function; you'll have to take that on faith or prove it to yourself. Recovering $x,y,z$ once you have solved for $u,v,w$ just requires three exponentials.
Some notes:
We could skip a few of the logarithms and still have a convex problem: the objective, the $e^uleq 3$ constraint, the nonlinear inequality. But in practice we keep those logarithms in there; the problems are better behaved numerically that way. (I have no theoretical support for this; someone else might, though). The other logarithms must be taken, however.
Strictly speaking, the convex version of this model is equivalent only if we assume strict positivity on $x,y,z$. Yes, you can handle the case of zero variables with more technical machinery; but fortunately we don't need that here. After all, $xgeq 2$ is guaranteed from the constraints; and $y$ cannot be zero unless the entire problem is infeasible, because of the $x/y$ objective. And therefore, from the $x/y=z^2$ constraint, we know that $z$ is nonzero as well.
If we wish we can eliminate $z$ and $w$ altogether, by taking advantage of the equality constraint, to yield
begin{array}{lllll}
text{minimize} & x/y & &
text{minimize} & u-v \
text{subject to} & 2 leq x leq 3 & &
text{subject to} & log 2 leq u leq log 3 \
& x^2 + y^{3/2} x^{-1/2} leq y^{1/2} &&
& log left( e^{2u} + e^{(3v-u)/2} right) leq v/2 \
end{array}
I cannot emphasize the following enough, but I am going to try:
Under no circumstances should one assume that a nonconvex problem can be made
convex if only you can find the right change of variables.
The title of this question suggests the author is making this assumption. Perhaps that's because this problem was assigned as a homework or test question, in which case it was known in advance by the question designer to be a geometric program. But geometric programs are the exception, not the rule. I'm unaware of any other general, non-manufactured class of nonconvex problems that can be made convex with just a change of variables.
answered Nov 12 '14 at 1:56
Michael GrantMichael Grant
15.1k12045
$endgroup$
add a comment |
$begingroup$
You're in luck: this is a geometric program. Therefore, the change of variables $$xrightarrow e^{u}, ~~ yrightarrow e^{v}, ~~ zrightarrow e^{w}$$
will get us close, and a few logarithms will get us the rest of the way there. Substitution yields
begin{array}{ll}
text{minimize} & e^{u-v} \
text{subject to} & 2 leq e^u leq 3 \
& e^{2u} + e^{v-w} leq e^{v/2} \
& e^{u-v}=e^{2w} end{array}
Now let's take some logarithms:
begin{array}{ll}
text{minimize} & u-v \
text{subject to} & log 2 leq u leq log 3 \
& log left( e^{2u} + e^{v-w} right) leq v/2 \
& u-v=2w end{array}
And there you have it: a convex optimization problem. The "log-sum-exp" expression is indeed a smooth convex function; you'll have to take that on faith or prove it to yourself. Recovering $x,y,z$ once you have solved for $u,v,w$ just requires three exponentials.
Some notes:
We could skip a few of the logarithms and still have a convex problem: the objective, the $e^uleq 3$ constraint, the nonlinear inequality. But in practice we keep those logarithms in there; the problems are better behaved numerically that way. (I have no theoretical support for this; someone else might, though). The other logarithms must be taken, however.
Strictly speaking, the convex version of this model is equivalent only if we assume strict positivity on $x,y,z$. Yes, you can handle the case of zero variables with more technical machinery; but fortunately we don't need that here. After all, $xgeq 2$ is guaranteed from the constraints; and $y$ cannot be zero unless the entire problem is infeasible, because of the $x/y$ objective. And therefore, from the $x/y=z^2$ constraint, we know that $z$ is nonzero as well.
If we wish we can eliminate $z$ and $w$ altogether, by taking advantage of the equality constraint, to yield
begin{array}{lllll}
text{minimize} & x/y & &
text{minimize} & u-v \
text{subject to} & 2 leq x leq 3 & &
text{subject to} & log 2 leq u leq log 3 \
& x^2 + y^{3/2} x^{-1/2} leq y^{1/2} &&
& log left( e^{2u} + e^{(3v-u)/2} right) leq v/2 \
end{array}
I cannot emphasize the following enough, but I am going to try:
Under no circumstances should one assume that a nonconvex problem can be made
convex if only you can find the right change of variables.
The title of this question suggests the author is making this assumption. Perhaps that's because this problem was assigned as a homework or test question, in which case it was known in advance by the question designer to be a geometric program. But geometric programs are the exception, not the rule. I'm unaware of any other general, non-manufactured class of nonconvex problems that can be made convex with just a change of variables.
answered Nov 12 '14 at 1:56
Michael GrantMichael Grant
15.1k12045
$endgroup$
You're in luck: this is a geometric program. Therefore, the change of variables $$xrightarrow e^{u}, ~~ yrightarrow e^{v}, ~~ zrightarrow e^{w}$$
will get us close, and a few logarithms will get us the rest of the way there. Substitution yields
begin{array}{ll}
text{minimize} & e^{u-v} \
text{subject to} & 2 leq e^u leq 3 \
& e^{2u} + e^{v-w} leq e^{v/2} \
& e^{u-v}=e^{2w} end{array}
Now let's take some logarithms:
begin{array}{ll}
text{minimize} & u-v \
text{subject to} & log 2 leq u leq log 3 \
& log left( e^{2u} + e^{v-w} right) leq v/2 \
& u-v=2w end{array}
And there you have it: a convex optimization problem. The "log-sum-exp" expression is indeed a smooth convex function; you'll have to take that on faith or prove it to yourself. Recovering $x,y,z$ once you have solved for $u,v,w$ just requires three exponentials.
Some notes:
We could skip a few of the logarithms and still have a convex problem: the objective, the $e^uleq 3$ constraint, the nonlinear inequality. But in practice we keep those logarithms in there; the problems are better behaved numerically that way. (I have no theoretical support for this; someone else might, though). The other logarithms must be taken, however.
Strictly speaking, the convex version of this model is equivalent only if we assume strict positivity on $x,y,z$. Yes, you can handle the case of zero variables with more technical machinery; but fortunately we don't need that here. After all, $xgeq 2$ is guaranteed from the constraints; and $y$ cannot be zero unless the entire problem is infeasible, because of the $x/y$ objective. And therefore, from the $x/y=z^2$ constraint, we know that $z$ is nonzero as well.
If we wish we can eliminate $z$ and $w$ altogether, by taking advantage of the equality constraint, to yield
begin{array}{lllll}
text{minimize} & x/y & &
text{minimize} & u-v \
text{subject to} & 2 leq x leq 3 & &
text{subject to} & log 2 leq u leq log 3 \
& x^2 + y^{3/2} x^{-1/2} leq y^{1/2} &&
& log left( e^{2u} + e^{(3v-u)/2} right) leq v/2 \
end{array}
I cannot emphasize the following enough, but I am going to try:
Under no circumstances should one assume that a nonconvex problem can be made
convex if only you can find the right change of variables.
The title of this question suggests the author is making this assumption. Perhaps that's because this problem was assigned as a homework or test question, in which case it was known in advance by the question designer to be a geometric program. But geometric programs are the exception, not the rule. I'm unaware of any other general, non-manufactured class of nonconvex problems that can be made convex with just a change of variables.
answered Nov 12 '14 at 1:56
Michael GrantMichael Grant
15.1k12045
edited Nov 12 '14 at 2:27
answered Nov 12 '14 at 1:56
Michael GrantMichael Grant
15.1k12045
answered Nov 12 '14 at 1:56
Michael GrantMichael Grant
15.1k12045
answered Nov 12 '14 at 1:56
Michael GrantMichael Grant
15.1k12045
15.1k12045
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%2f1017667%2fwhat-is-the-correct-change-of-variables-to-yield-convexity-in-this-nonlinear-opt%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
