Optimizing a sum of functions
$begingroup$
I'm not an expert in optimization, but I am currently working on a problem where I need to maximize/minimize a function of the form,
begin{equation*}
g(alpha_0, alpha_1) = displaystyle sum_{i=1}^N c_i f(alpha_0 + alpha_1 d_i) \
a leq f(alpha_0 + alpha_1 d_i) leq b ~ forall , i = 1,2,...,N
end{equation*}
where $c,,din mathbb{R}^N$ and $a,,b in mathbb{R}$ are all fixed constants.
In this problem, I have some flexibility in the choice of $f(cdot)$. I know that this reduces to a linear optimization problem when $f(cdot)$ is linear, but I'm wondering if there are other classes of functions for which this is solvable? Or methods of function approximation that would allow me to get close to the optimum?
One function that is of particular interest to me is,
begin{equation*}
f(alpha_0 + alpha_1 d_i) = 1 + exp(alpha_0 + alpha_1 d_i)
end{equation*}
This is a convex function by itself, but $c_i f(alpha_0 + alpha_1 d_i)$ could be convex or concave depending on the sign of $c_i$, so my understanding is that this is not solvable.
Directing me to relevant literature/textbooks would be especially appreciated! Thank you.
optimization nonlinear-optimization non-convex-optimization
asked Jan 21 at 23:44
confusedstatisticianconfusedstatistician
1
$endgroup$
add a comment |
$begingroup$
I'm not an expert in optimization, but I am currently working on a problem where I need to maximize/minimize a function of the form,
begin{equation*}
g(alpha_0, alpha_1) = displaystyle sum_{i=1}^N c_i f(alpha_0 + alpha_1 d_i) \
a leq f(alpha_0 + alpha_1 d_i) leq b ~ forall , i = 1,2,...,N
end{equation*}
where $c,,din mathbb{R}^N$ and $a,,b in mathbb{R}$ are all fixed constants.
In this problem, I have some flexibility in the choice of $f(cdot)$. I know that this reduces to a linear optimization problem when $f(cdot)$ is linear, but I'm wondering if there are other classes of functions for which this is solvable? Or methods of function approximation that would allow me to get close to the optimum?
One function that is of particular interest to me is,
begin{equation*}
f(alpha_0 + alpha_1 d_i) = 1 + exp(alpha_0 + alpha_1 d_i)
end{equation*}
This is a convex function by itself, but $c_i f(alpha_0 + alpha_1 d_i)$ could be convex or concave depending on the sign of $c_i$, so my understanding is that this is not solvable.
Directing me to relevant literature/textbooks would be especially appreciated! Thank you.
optimization nonlinear-optimization non-convex-optimization
asked Jan 21 at 23:44
confusedstatisticianconfusedstatistician
1
$endgroup$
add a comment |
$begingroup$
I'm not an expert in optimization, but I am currently working on a problem where I need to maximize/minimize a function of the form,
begin{equation*}
g(alpha_0, alpha_1) = displaystyle sum_{i=1}^N c_i f(alpha_0 + alpha_1 d_i) \
a leq f(alpha_0 + alpha_1 d_i) leq b ~ forall , i = 1,2,...,N
end{equation*}
where $c,,din mathbb{R}^N$ and $a,,b in mathbb{R}$ are all fixed constants.
In this problem, I have some flexibility in the choice of $f(cdot)$. I know that this reduces to a linear optimization problem when $f(cdot)$ is linear, but I'm wondering if there are other classes of functions for which this is solvable? Or methods of function approximation that would allow me to get close to the optimum?
One function that is of particular interest to me is,
begin{equation*}
f(alpha_0 + alpha_1 d_i) = 1 + exp(alpha_0 + alpha_1 d_i)
end{equation*}
This is a convex function by itself, but $c_i f(alpha_0 + alpha_1 d_i)$ could be convex or concave depending on the sign of $c_i$, so my understanding is that this is not solvable.
Directing me to relevant literature/textbooks would be especially appreciated! Thank you.
optimization nonlinear-optimization non-convex-optimization
asked Jan 21 at 23:44
confusedstatisticianconfusedstatistician
1
$endgroup$
I'm not an expert in optimization, but I am currently working on a problem where I need to maximize/minimize a function of the form,
begin{equation*}
g(alpha_0, alpha_1) = displaystyle sum_{i=1}^N c_i f(alpha_0 + alpha_1 d_i) \
a leq f(alpha_0 + alpha_1 d_i) leq b ~ forall , i = 1,2,...,N
end{equation*}
where $c,,din mathbb{R}^N$ and $a,,b in mathbb{R}$ are all fixed constants.
In this problem, I have some flexibility in the choice of $f(cdot)$. I know that this reduces to a linear optimization problem when $f(cdot)$ is linear, but I'm wondering if there are other classes of functions for which this is solvable? Or methods of function approximation that would allow me to get close to the optimum?
One function that is of particular interest to me is,
begin{equation*}
f(alpha_0 + alpha_1 d_i) = 1 + exp(alpha_0 + alpha_1 d_i)
end{equation*}
This is a convex function by itself, but $c_i f(alpha_0 + alpha_1 d_i)$ could be convex or concave depending on the sign of $c_i$, so my understanding is that this is not solvable.
Directing me to relevant literature/textbooks would be especially appreciated! Thank you.
optimization nonlinear-optimization non-convex-optimization
optimization nonlinear-optimization non-convex-optimization
asked Jan 21 at 23:44
confusedstatisticianconfusedstatistician
1
asked Jan 21 at 23:44
confusedstatisticianconfusedstatistician
1
asked Jan 21 at 23:44
confusedstatisticianconfusedstatistician
1
asked Jan 21 at 23:44
confusedstatisticianconfusedstatistician
1
asked Jan 21 at 23:44
confusedstatisticianconfusedstatistician
1
1
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
First, the constraints are effectively linear as $f$ is monotonically increasing, you've just written them in a bad form.
Since you only have two variables, and nice nonlinearties, even a global solver will solve this problem rather quickly if $N$ is modest. In the code below, I throw it to the simple spatial branch-and-bound global solver in YALMIP (disclaimer, developed by me), and it is solved in a couple of seconds for $N=50$
N = 50;
d = randn(N,1);
c = randn(N,1);
a = 2;
b = 10;
sdpvar alpha0 alpha1
g = sum(c.*(1 + exp(alpha0 + alpha1*d)));
Model = [log(a-1) <= alpha0 + alpha1*d <= log(b-1)];
optimize(Model,g,sdpsettings('solver','bmibnb'))
Also, for all the examples I tried, a local solver found the global solution too.
answered Jan 23 at 18:31
Johan LöfbergJohan Löfberg
5,3001811
$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%2f3082572%2foptimizing-a-sum-of-functions%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$
First, the constraints are effectively linear as $f$ is monotonically increasing, you've just written them in a bad form.
Since you only have two variables, and nice nonlinearties, even a global solver will solve this problem rather quickly if $N$ is modest. In the code below, I throw it to the simple spatial branch-and-bound global solver in YALMIP (disclaimer, developed by me), and it is solved in a couple of seconds for $N=50$
N = 50;
d = randn(N,1);
c = randn(N,1);
a = 2;
b = 10;
sdpvar alpha0 alpha1
g = sum(c.*(1 + exp(alpha0 + alpha1*d)));
Model = [log(a-1) <= alpha0 + alpha1*d <= log(b-1)];
optimize(Model,g,sdpsettings('solver','bmibnb'))
Also, for all the examples I tried, a local solver found the global solution too.
answered Jan 23 at 18:31
Johan LöfbergJohan Löfberg
5,3001811
$endgroup$
add a comment |
$begingroup$
First, the constraints are effectively linear as $f$ is monotonically increasing, you've just written them in a bad form.
Since you only have two variables, and nice nonlinearties, even a global solver will solve this problem rather quickly if $N$ is modest. In the code below, I throw it to the simple spatial branch-and-bound global solver in YALMIP (disclaimer, developed by me), and it is solved in a couple of seconds for $N=50$
N = 50;
d = randn(N,1);
c = randn(N,1);
a = 2;
b = 10;
sdpvar alpha0 alpha1
g = sum(c.*(1 + exp(alpha0 + alpha1*d)));
Model = [log(a-1) <= alpha0 + alpha1*d <= log(b-1)];
optimize(Model,g,sdpsettings('solver','bmibnb'))
Also, for all the examples I tried, a local solver found the global solution too.
answered Jan 23 at 18:31
Johan LöfbergJohan Löfberg
5,3001811
$endgroup$
add a comment |
$begingroup$
First, the constraints are effectively linear as $f$ is monotonically increasing, you've just written them in a bad form.
Since you only have two variables, and nice nonlinearties, even a global solver will solve this problem rather quickly if $N$ is modest. In the code below, I throw it to the simple spatial branch-and-bound global solver in YALMIP (disclaimer, developed by me), and it is solved in a couple of seconds for $N=50$
N = 50;
d = randn(N,1);
c = randn(N,1);
a = 2;
b = 10;
sdpvar alpha0 alpha1
g = sum(c.*(1 + exp(alpha0 + alpha1*d)));
Model = [log(a-1) <= alpha0 + alpha1*d <= log(b-1)];
optimize(Model,g,sdpsettings('solver','bmibnb'))
Also, for all the examples I tried, a local solver found the global solution too.
answered Jan 23 at 18:31
Johan LöfbergJohan Löfberg
5,3001811
$endgroup$
First, the constraints are effectively linear as $f$ is monotonically increasing, you've just written them in a bad form.
Since you only have two variables, and nice nonlinearties, even a global solver will solve this problem rather quickly if $N$ is modest. In the code below, I throw it to the simple spatial branch-and-bound global solver in YALMIP (disclaimer, developed by me), and it is solved in a couple of seconds for $N=50$
N = 50;
d = randn(N,1);
c = randn(N,1);
a = 2;
b = 10;
sdpvar alpha0 alpha1
g = sum(c.*(1 + exp(alpha0 + alpha1*d)));
Model = [log(a-1) <= alpha0 + alpha1*d <= log(b-1)];
optimize(Model,g,sdpsettings('solver','bmibnb'))
Also, for all the examples I tried, a local solver found the global solution too.
answered Jan 23 at 18:31
Johan LöfbergJohan Löfberg
5,3001811
answered Jan 23 at 18:31
Johan LöfbergJohan Löfberg
5,3001811
answered Jan 23 at 18:31
Johan LöfbergJohan Löfberg
5,3001811
answered Jan 23 at 18:31
Johan LöfbergJohan Löfberg
5,3001811
5,3001811
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%2f3082572%2foptimizing-a-sum-of-functions%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
