Mixing
Rewrite $ min_{qin Q_0} sum_{x=1}^X |m_x(q)| $ with linear objective function
$begingroup$
I have the following optimization problem
$$
min_{qin Q_0} sum_{x=1}^X |m_x(q_{1})|
$$
where
$qequiv (q_1,q_2)$ is a vector that should satisfy a bunch of non-linear constraints collected in $Q_0$.
$m_x(q_1)$ is linear in $q_1$ $forall x=1,...,X$.
Specifically: some components of $q_2$ are required to be binary, other are allowed to vary in $[l_b, l_u]$; all the elements of $q_1$ are allowed to vary in $[l_b, l_u]$; apart from such support restrictions, $Q_0$ contains inequalities of the type e.g.,
$$
overbrace{q_{1,j}}^{in [l_b,l_u]}-overbrace{q_{1,k}}^{in [l_b,l_u]}geq overbrace{q_{2,h}}^{text{binary}}
$$
where $q_{1,j}$ is the $j$th element of $q_1$.
In other words, what I want to highlight (sorry for the non-formal, maybe wrong terminology) is that all the inequalities in $Q_0$ would have been linear if all the elements in $q_2$ were allowed to freely vary in $[l_b, l_u]$.
Question: I have been advised that the problem above can be rewritten as having a linear objective function, because it is equivalent to
$$
begin{aligned}
&min_{q, {mu^{+}(x), mu^{-}(x)}_{forall x =1,...,X}} sum_{x=1}^X (mu^{+}(x)+mu^{-}(x))\
& qin Q_0\
& mu^{+}(x)geq 0 text{ }forall x=1,...,X\
& mu^{+}(x)geq 0text{ }forall x=1,...,X\
& m_x(q)=mu^{+}(x)-mu^{-}(x)text{ }forall x=1,...,X\
end{aligned}
$$
Is this correct? If yes, could you skectch a proof? If not, why?
My impression is that the reformulation of the problem works when $Q_0$ contains constraints that are linear in $q$ (e.g., p.294 of Boyd and
Vandenberghe, 2004). When $Q_0$ has non-linear constraints (as in my case) I have doubts.
optimization convex-optimization linear-programming nonlinear-optimization non-convex-optimization
asked Jan 19 at 16:22
STFSTF
431422
$endgroup$
add a comment |
$begingroup$
I have the following optimization problem
$$
min_{qin Q_0} sum_{x=1}^X |m_x(q_{1})|
$$
where
$qequiv (q_1,q_2)$ is a vector that should satisfy a bunch of non-linear constraints collected in $Q_0$.
$m_x(q_1)$ is linear in $q_1$ $forall x=1,...,X$.
Specifically: some components of $q_2$ are required to be binary, other are allowed to vary in $[l_b, l_u]$; all the elements of $q_1$ are allowed to vary in $[l_b, l_u]$; apart from such support restrictions, $Q_0$ contains inequalities of the type e.g.,
$$
overbrace{q_{1,j}}^{in [l_b,l_u]}-overbrace{q_{1,k}}^{in [l_b,l_u]}geq overbrace{q_{2,h}}^{text{binary}}
$$
where $q_{1,j}$ is the $j$th element of $q_1$.
In other words, what I want to highlight (sorry for the non-formal, maybe wrong terminology) is that all the inequalities in $Q_0$ would have been linear if all the elements in $q_2$ were allowed to freely vary in $[l_b, l_u]$.
Question: I have been advised that the problem above can be rewritten as having a linear objective function, because it is equivalent to
$$
begin{aligned}
&min_{q, {mu^{+}(x), mu^{-}(x)}_{forall x =1,...,X}} sum_{x=1}^X (mu^{+}(x)+mu^{-}(x))\
& qin Q_0\
& mu^{+}(x)geq 0 text{ }forall x=1,...,X\
& mu^{+}(x)geq 0text{ }forall x=1,...,X\
& m_x(q)=mu^{+}(x)-mu^{-}(x)text{ }forall x=1,...,X\
end{aligned}
$$
Is this correct? If yes, could you skectch a proof? If not, why?
My impression is that the reformulation of the problem works when $Q_0$ contains constraints that are linear in $q$ (e.g., p.294 of Boyd and
Vandenberghe, 2004). When $Q_0$ has non-linear constraints (as in my case) I have doubts.
optimization convex-optimization linear-programming nonlinear-optimization non-convex-optimization
asked Jan 19 at 16:22
STFSTF
431422
$endgroup$
1
$begingroup$
you are right, $Q_0$ has to be linear
$endgroup$
– LinAlg
Jan 19 at 23:11
$begingroup$
Thanks. Is there any hope to get a linear objective function when $Q_0$ is non-linear? Maybe with other types of reformulations?
$endgroup$
– STF
Jan 20 at 9:17
1
$begingroup$
yes, sometimes such as when $Q_0$ is piecewise linear and convex
$endgroup$
– LinAlg
Jan 20 at 18:34
$begingroup$
@LinAlg Thanks. I have added details on my problem which may allow to provide a more detailed answer. Maybe.
$endgroup$
– STF
Jan 20 at 19:15
1
$begingroup$
Binary variables will never be linear.
$endgroup$
– LinAlg
Jan 20 at 19:23
add a comment |
$begingroup$
I have the following optimization problem
$$
min_{qin Q_0} sum_{x=1}^X |m_x(q_{1})|
$$
where
$qequiv (q_1,q_2)$ is a vector that should satisfy a bunch of non-linear constraints collected in $Q_0$.
$m_x(q_1)$ is linear in $q_1$ $forall x=1,...,X$.
Specifically: some components of $q_2$ are required to be binary, other are allowed to vary in $[l_b, l_u]$; all the elements of $q_1$ are allowed to vary in $[l_b, l_u]$; apart from such support restrictions, $Q_0$ contains inequalities of the type e.g.,
$$
overbrace{q_{1,j}}^{in [l_b,l_u]}-overbrace{q_{1,k}}^{in [l_b,l_u]}geq overbrace{q_{2,h}}^{text{binary}}
$$
where $q_{1,j}$ is the $j$th element of $q_1$.
In other words, what I want to highlight (sorry for the non-formal, maybe wrong terminology) is that all the inequalities in $Q_0$ would have been linear if all the elements in $q_2$ were allowed to freely vary in $[l_b, l_u]$.
Question: I have been advised that the problem above can be rewritten as having a linear objective function, because it is equivalent to
$$
begin{aligned}
&min_{q, {mu^{+}(x), mu^{-}(x)}_{forall x =1,...,X}} sum_{x=1}^X (mu^{+}(x)+mu^{-}(x))\
& qin Q_0\
& mu^{+}(x)geq 0 text{ }forall x=1,...,X\
& mu^{+}(x)geq 0text{ }forall x=1,...,X\
& m_x(q)=mu^{+}(x)-mu^{-}(x)text{ }forall x=1,...,X\
end{aligned}
$$
Is this correct? If yes, could you skectch a proof? If not, why?
My impression is that the reformulation of the problem works when $Q_0$ contains constraints that are linear in $q$ (e.g., p.294 of Boyd and
Vandenberghe, 2004). When $Q_0$ has non-linear constraints (as in my case) I have doubts.
optimization convex-optimization linear-programming nonlinear-optimization non-convex-optimization
asked Jan 19 at 16:22
STFSTF
431422
$endgroup$
I have the following optimization problem
$$
min_{qin Q_0} sum_{x=1}^X |m_x(q_{1})|
$$
where
$qequiv (q_1,q_2)$ is a vector that should satisfy a bunch of non-linear constraints collected in $Q_0$.
$m_x(q_1)$ is linear in $q_1$ $forall x=1,...,X$.
Specifically: some components of $q_2$ are required to be binary, other are allowed to vary in $[l_b, l_u]$; all the elements of $q_1$ are allowed to vary in $[l_b, l_u]$; apart from such support restrictions, $Q_0$ contains inequalities of the type e.g.,
$$
overbrace{q_{1,j}}^{in [l_b,l_u]}-overbrace{q_{1,k}}^{in [l_b,l_u]}geq overbrace{q_{2,h}}^{text{binary}}
$$
where $q_{1,j}$ is the $j$th element of $q_1$.
In other words, what I want to highlight (sorry for the non-formal, maybe wrong terminology) is that all the inequalities in $Q_0$ would have been linear if all the elements in $q_2$ were allowed to freely vary in $[l_b, l_u]$.
Question: I have been advised that the problem above can be rewritten as having a linear objective function, because it is equivalent to
$$
begin{aligned}
&min_{q, {mu^{+}(x), mu^{-}(x)}_{forall x =1,...,X}} sum_{x=1}^X (mu^{+}(x)+mu^{-}(x))\
& qin Q_0\
& mu^{+}(x)geq 0 text{ }forall x=1,...,X\
& mu^{+}(x)geq 0text{ }forall x=1,...,X\
& m_x(q)=mu^{+}(x)-mu^{-}(x)text{ }forall x=1,...,X\
end{aligned}
$$
Is this correct? If yes, could you skectch a proof? If not, why?
My impression is that the reformulation of the problem works when $Q_0$ contains constraints that are linear in $q$ (e.g., p.294 of Boyd and
Vandenberghe, 2004). When $Q_0$ has non-linear constraints (as in my case) I have doubts.
optimization convex-optimization linear-programming nonlinear-optimization non-convex-optimization
optimization convex-optimization linear-programming nonlinear-optimization non-convex-optimization
asked Jan 19 at 16:22
STFSTF
431422
asked Jan 19 at 16:22
STFSTF
431422
edited Jan 20 at 19:14
STF
asked Jan 19 at 16:22
STFSTF
431422
asked Jan 19 at 16:22
STFSTF
431422
asked Jan 19 at 16:22
STFSTF
431422
431422
1
$begingroup$
you are right, $Q_0$ has to be linear
$endgroup$
– LinAlg
Jan 19 at 23:11
$begingroup$
Thanks. Is there any hope to get a linear objective function when $Q_0$ is non-linear? Maybe with other types of reformulations?
$endgroup$
– STF
Jan 20 at 9:17
1
$begingroup$
yes, sometimes such as when $Q_0$ is piecewise linear and convex
$endgroup$
– LinAlg
Jan 20 at 18:34
$begingroup$
@LinAlg Thanks. I have added details on my problem which may allow to provide a more detailed answer. Maybe.
$endgroup$
– STF
Jan 20 at 19:15
1
$begingroup$
Binary variables will never be linear.
$endgroup$
– LinAlg
Jan 20 at 19:23
add a comment |
1
$begingroup$
you are right, $Q_0$ has to be linear
$endgroup$
– LinAlg
Jan 19 at 23:11
$begingroup$
Thanks. Is there any hope to get a linear objective function when $Q_0$ is non-linear? Maybe with other types of reformulations?
$endgroup$
– STF
Jan 20 at 9:17
1
$begingroup$
yes, sometimes such as when $Q_0$ is piecewise linear and convex
$endgroup$
– LinAlg
Jan 20 at 18:34
$begingroup$
@LinAlg Thanks. I have added details on my problem which may allow to provide a more detailed answer. Maybe.
$endgroup$
– STF
Jan 20 at 19:15
1
$begingroup$
Binary variables will never be linear.
$endgroup$
– LinAlg
Jan 20 at 19:23
1
1
$begingroup$
you are right, $Q_0$ has to be linear
$endgroup$
– LinAlg
Jan 19 at 23:11
$begingroup$
you are right, $Q_0$ has to be linear
$endgroup$
– LinAlg
Jan 19 at 23:11
$begingroup$
Thanks. Is there any hope to get a linear objective function when $Q_0$ is non-linear? Maybe with other types of reformulations?
$endgroup$
– STF
Jan 20 at 9:17
$begingroup$
Thanks. Is there any hope to get a linear objective function when $Q_0$ is non-linear? Maybe with other types of reformulations?
$endgroup$
– STF
Jan 20 at 9:17
1
1
$begingroup$
yes, sometimes such as when $Q_0$ is piecewise linear and convex
$endgroup$
– LinAlg
Jan 20 at 18:34
$begingroup$
yes, sometimes such as when $Q_0$ is piecewise linear and convex
$endgroup$
– LinAlg
Jan 20 at 18:34
$begingroup$
@LinAlg Thanks. I have added details on my problem which may allow to provide a more detailed answer. Maybe.
$endgroup$
– STF
Jan 20 at 19:15
$begingroup$
@LinAlg Thanks. I have added details on my problem which may allow to provide a more detailed answer. Maybe.
$endgroup$
– STF
Jan 20 at 19:15
1
1
$begingroup$
Binary variables will never be linear.
$endgroup$
– LinAlg
Jan 20 at 19:23
$begingroup$
Binary variables will never be linear.
$endgroup$
– LinAlg
Jan 20 at 19:23
add a comment |
0
active
oldest
votes
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%2f3079527%2frewrite-min-q-in-q-0-sum-x-1x-m-xq-with-linear-objective-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3079527%2frewrite-min-q-in-q-0-sum-x-1x-m-xq-with-linear-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$
you are right, $Q_0$ has to be linear
$endgroup$
– LinAlg
Jan 19 at 23:11
$begingroup$
Thanks. Is there any hope to get a linear objective function when $Q_0$ is non-linear? Maybe with other types of reformulations?
$endgroup$
– STF
Jan 20 at 9:17
1
$begingroup$
yes, sometimes such as when $Q_0$ is piecewise linear and convex
$endgroup$
– LinAlg
Jan 20 at 18:34
$begingroup$
@LinAlg Thanks. I have added details on my problem which may allow to provide a more detailed answer. Maybe.
$endgroup$
– STF
Jan 20 at 19:15
1
$begingroup$
Binary variables will never be linear.
$endgroup$
– LinAlg
Jan 20 at 19:23