Multi-Objective Linear Optimisation Pareto Solution
$begingroup$
I'm looking at optimising weightings over a set of different amounts to achieve a total, whilst minimising the amount over the total these are.
Think: I have macronutrient targets, I want to make sure I hit them but don't go over by an excessive amount so what 'weight' of each meal would I want.
So the constraint is:
$left( begin{array}
QP_{11} & P_{12} & P_{13} \
P_{21} & P_{22} & P_{23} \
P_{31} & P_{32} & P_{33} \
P_{41} & P_{42} & P_{43} end{array}right) cdot
left(begin{array} Qw_1 \
w_2 \
w_3 end{array} right) ge left( begin{array} QT_1 \
T_2 \
T_3 \
T_4 end{array} right)$
Whilst we want to minimise:
$mathrm{min} left[left( begin{array}
QP_{11} & P_{12} & P_{13} \
P_{21} & P_{22} & P_{23} \
P_{31} & P_{32} & P_{33} \
P_{41} & P_{42} & P_{43} end{array}right) cdot
left(begin{array} Qw_1 \
w_2 \
w_3 end{array} right) - left( begin{array} QT_1 \
T_2 \
T_3 \
T_4 end{array} right)right]$
I'm having a bit of trouble on where to start with this though. I know that for a problem with two objectives I could just make one objective as efficient as possible, but not really sure where to start here. And of course if the matrix P was 3x3 if it has an inverse the problem is automatically solved.
I'd also possibly want to expand this to more than three weightings. So any algorithm would need to be extendable to n-objectives and indeed m payoffs.
Are there any names of specific algorithms for this? Ideally something that is suitable for automation given a P matrix and a T vector.
optimization convex-optimization linear-programming
$endgroup$
add a comment |
$begingroup$
I'm looking at optimising weightings over a set of different amounts to achieve a total, whilst minimising the amount over the total these are.
Think: I have macronutrient targets, I want to make sure I hit them but don't go over by an excessive amount so what 'weight' of each meal would I want.
So the constraint is:
$left( begin{array}
QP_{11} & P_{12} & P_{13} \
P_{21} & P_{22} & P_{23} \
P_{31} & P_{32} & P_{33} \
P_{41} & P_{42} & P_{43} end{array}right) cdot
left(begin{array} Qw_1 \
w_2 \
w_3 end{array} right) ge left( begin{array} QT_1 \
T_2 \
T_3 \
T_4 end{array} right)$
Whilst we want to minimise:
$mathrm{min} left[left( begin{array}
QP_{11} & P_{12} & P_{13} \
P_{21} & P_{22} & P_{23} \
P_{31} & P_{32} & P_{33} \
P_{41} & P_{42} & P_{43} end{array}right) cdot
left(begin{array} Qw_1 \
w_2 \
w_3 end{array} right) - left( begin{array} QT_1 \
T_2 \
T_3 \
T_4 end{array} right)right]$
I'm having a bit of trouble on where to start with this though. I know that for a problem with two objectives I could just make one objective as efficient as possible, but not really sure where to start here. And of course if the matrix P was 3x3 if it has an inverse the problem is automatically solved.
I'd also possibly want to expand this to more than three weightings. So any algorithm would need to be extendable to n-objectives and indeed m payoffs.
Are there any names of specific algorithms for this? Ideally something that is suitable for automation given a P matrix and a T vector.
optimization convex-optimization linear-programming
$endgroup$
$begingroup$
are you just looking for any Pareto Solution?
$endgroup$
– LinAlg
Jan 3 at 12:44
$begingroup$
Any efficient solution would suffice, from there it should be possible to extend to all efficient solutions.
$endgroup$
– user403033
Jan 3 at 14:40
$begingroup$
Is $w_1+w_2+w_3=1$ and addtionally $w_igeq 0 forall i in {1,2,3 } $?
$endgroup$
– callculus
Jan 3 at 19:05
$begingroup$
No, the weights would not have to sum to 1 but they would need to be positive.
$endgroup$
– user403033
Jan 4 at 9:45
add a comment |
$begingroup$
I'm looking at optimising weightings over a set of different amounts to achieve a total, whilst minimising the amount over the total these are.
Think: I have macronutrient targets, I want to make sure I hit them but don't go over by an excessive amount so what 'weight' of each meal would I want.
So the constraint is:
$left( begin{array}
QP_{11} & P_{12} & P_{13} \
P_{21} & P_{22} & P_{23} \
P_{31} & P_{32} & P_{33} \
P_{41} & P_{42} & P_{43} end{array}right) cdot
left(begin{array} Qw_1 \
w_2 \
w_3 end{array} right) ge left( begin{array} QT_1 \
T_2 \
T_3 \
T_4 end{array} right)$
Whilst we want to minimise:
$mathrm{min} left[left( begin{array}
QP_{11} & P_{12} & P_{13} \
P_{21} & P_{22} & P_{23} \
P_{31} & P_{32} & P_{33} \
P_{41} & P_{42} & P_{43} end{array}right) cdot
left(begin{array} Qw_1 \
w_2 \
w_3 end{array} right) - left( begin{array} QT_1 \
T_2 \
T_3 \
T_4 end{array} right)right]$
I'm having a bit of trouble on where to start with this though. I know that for a problem with two objectives I could just make one objective as efficient as possible, but not really sure where to start here. And of course if the matrix P was 3x3 if it has an inverse the problem is automatically solved.
I'd also possibly want to expand this to more than three weightings. So any algorithm would need to be extendable to n-objectives and indeed m payoffs.
Are there any names of specific algorithms for this? Ideally something that is suitable for automation given a P matrix and a T vector.
optimization convex-optimization linear-programming
$endgroup$
I'm looking at optimising weightings over a set of different amounts to achieve a total, whilst minimising the amount over the total these are.
Think: I have macronutrient targets, I want to make sure I hit them but don't go over by an excessive amount so what 'weight' of each meal would I want.
So the constraint is:
$left( begin{array}
QP_{11} & P_{12} & P_{13} \
P_{21} & P_{22} & P_{23} \
P_{31} & P_{32} & P_{33} \
P_{41} & P_{42} & P_{43} end{array}right) cdot
left(begin{array} Qw_1 \
w_2 \
w_3 end{array} right) ge left( begin{array} QT_1 \
T_2 \
T_3 \
T_4 end{array} right)$
Whilst we want to minimise:
$mathrm{min} left[left( begin{array}
QP_{11} & P_{12} & P_{13} \
P_{21} & P_{22} & P_{23} \
P_{31} & P_{32} & P_{33} \
P_{41} & P_{42} & P_{43} end{array}right) cdot
left(begin{array} Qw_1 \
w_2 \
w_3 end{array} right) - left( begin{array} QT_1 \
T_2 \
T_3 \
T_4 end{array} right)right]$
I'm having a bit of trouble on where to start with this though. I know that for a problem with two objectives I could just make one objective as efficient as possible, but not really sure where to start here. And of course if the matrix P was 3x3 if it has an inverse the problem is automatically solved.
I'd also possibly want to expand this to more than three weightings. So any algorithm would need to be extendable to n-objectives and indeed m payoffs.
Are there any names of specific algorithms for this? Ideally something that is suitable for automation given a P matrix and a T vector.
optimization convex-optimization linear-programming
optimization convex-optimization linear-programming
asked Jan 3 at 10:27
user403033user403033
357
357
$begingroup$
are you just looking for any Pareto Solution?
$endgroup$
– LinAlg
Jan 3 at 12:44
$begingroup$
Any efficient solution would suffice, from there it should be possible to extend to all efficient solutions.
$endgroup$
– user403033
Jan 3 at 14:40
$begingroup$
Is $w_1+w_2+w_3=1$ and addtionally $w_igeq 0 forall i in {1,2,3 } $?
$endgroup$
– callculus
Jan 3 at 19:05
$begingroup$
No, the weights would not have to sum to 1 but they would need to be positive.
$endgroup$
– user403033
Jan 4 at 9:45
add a comment |
$begingroup$
are you just looking for any Pareto Solution?
$endgroup$
– LinAlg
Jan 3 at 12:44
$begingroup$
Any efficient solution would suffice, from there it should be possible to extend to all efficient solutions.
$endgroup$
– user403033
Jan 3 at 14:40
$begingroup$
Is $w_1+w_2+w_3=1$ and addtionally $w_igeq 0 forall i in {1,2,3 } $?
$endgroup$
– callculus
Jan 3 at 19:05
$begingroup$
No, the weights would not have to sum to 1 but they would need to be positive.
$endgroup$
– user403033
Jan 4 at 9:45
$begingroup$
are you just looking for any Pareto Solution?
$endgroup$
– LinAlg
Jan 3 at 12:44
$begingroup$
are you just looking for any Pareto Solution?
$endgroup$
– LinAlg
Jan 3 at 12:44
$begingroup$
Any efficient solution would suffice, from there it should be possible to extend to all efficient solutions.
$endgroup$
– user403033
Jan 3 at 14:40
$begingroup$
Any efficient solution would suffice, from there it should be possible to extend to all efficient solutions.
$endgroup$
– user403033
Jan 3 at 14:40
$begingroup$
Is $w_1+w_2+w_3=1$ and addtionally $w_igeq 0 forall i in {1,2,3 } $?
$endgroup$
– callculus
Jan 3 at 19:05
$begingroup$
Is $w_1+w_2+w_3=1$ and addtionally $w_igeq 0 forall i in {1,2,3 } $?
$endgroup$
– callculus
Jan 3 at 19:05
$begingroup$
No, the weights would not have to sum to 1 but they would need to be positive.
$endgroup$
– user403033
Jan 4 at 9:45
$begingroup$
No, the weights would not have to sum to 1 but they would need to be positive.
$endgroup$
– user403033
Jan 4 at 9:45
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your problem can be summarized as $min_{s,x}{s : Ax+sgeq b, sgeq 0}$. Weighted sum optimization gives a Pareto Solution as long as each weight is strictly positive:
$min_{x,s}{w^Ts : Ax+sgeq b, sgeq 0}$. These problems can be solved with the simplex method (available with linprog in scipy or Matlab).
$endgroup$
$begingroup$
I assume in this instance $s$ is the vector of my minimisation condition and $w$ are the weights I'm applying to each? So that I'm then left with a scalar to minimise?
$endgroup$
– user403033
Jan 4 at 9:48
$begingroup$
@user403033 that is correct!
$endgroup$
– LinAlg
Jan 4 at 14:20
$begingroup$
Thanks, I'll give it a go with weightings of 1 across the board to start. A scalar condition will be much easier to deal with though. I assume if a particular entry of the P matrix is dominating the solution (due to relative size etc), to avoid this the problem is going to need to be reformulated?
$endgroup$
– user403033
Jan 4 at 15:03
$begingroup$
@user403033 you can either adjust the weights, or constrain two values of $P$ while optimizing the third value
$endgroup$
– LinAlg
Jan 16 at 20:06
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%2f3060426%2fmulti-objective-linear-optimisation-pareto-solution%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$
Your problem can be summarized as $min_{s,x}{s : Ax+sgeq b, sgeq 0}$. Weighted sum optimization gives a Pareto Solution as long as each weight is strictly positive:
$min_{x,s}{w^Ts : Ax+sgeq b, sgeq 0}$. These problems can be solved with the simplex method (available with linprog in scipy or Matlab).
$endgroup$
$begingroup$
I assume in this instance $s$ is the vector of my minimisation condition and $w$ are the weights I'm applying to each? So that I'm then left with a scalar to minimise?
$endgroup$
– user403033
Jan 4 at 9:48
$begingroup$
@user403033 that is correct!
$endgroup$
– LinAlg
Jan 4 at 14:20
$begingroup$
Thanks, I'll give it a go with weightings of 1 across the board to start. A scalar condition will be much easier to deal with though. I assume if a particular entry of the P matrix is dominating the solution (due to relative size etc), to avoid this the problem is going to need to be reformulated?
$endgroup$
– user403033
Jan 4 at 15:03
$begingroup$
@user403033 you can either adjust the weights, or constrain two values of $P$ while optimizing the third value
$endgroup$
– LinAlg
Jan 16 at 20:06
add a comment |
$begingroup$
Your problem can be summarized as $min_{s,x}{s : Ax+sgeq b, sgeq 0}$. Weighted sum optimization gives a Pareto Solution as long as each weight is strictly positive:
$min_{x,s}{w^Ts : Ax+sgeq b, sgeq 0}$. These problems can be solved with the simplex method (available with linprog in scipy or Matlab).
$endgroup$
$begingroup$
I assume in this instance $s$ is the vector of my minimisation condition and $w$ are the weights I'm applying to each? So that I'm then left with a scalar to minimise?
$endgroup$
– user403033
Jan 4 at 9:48
$begingroup$
@user403033 that is correct!
$endgroup$
– LinAlg
Jan 4 at 14:20
$begingroup$
Thanks, I'll give it a go with weightings of 1 across the board to start. A scalar condition will be much easier to deal with though. I assume if a particular entry of the P matrix is dominating the solution (due to relative size etc), to avoid this the problem is going to need to be reformulated?
$endgroup$
– user403033
Jan 4 at 15:03
$begingroup$
@user403033 you can either adjust the weights, or constrain two values of $P$ while optimizing the third value
$endgroup$
– LinAlg
Jan 16 at 20:06
add a comment |
$begingroup$
Your problem can be summarized as $min_{s,x}{s : Ax+sgeq b, sgeq 0}$. Weighted sum optimization gives a Pareto Solution as long as each weight is strictly positive:
$min_{x,s}{w^Ts : Ax+sgeq b, sgeq 0}$. These problems can be solved with the simplex method (available with linprog in scipy or Matlab).
$endgroup$
Your problem can be summarized as $min_{s,x}{s : Ax+sgeq b, sgeq 0}$. Weighted sum optimization gives a Pareto Solution as long as each weight is strictly positive:
$min_{x,s}{w^Ts : Ax+sgeq b, sgeq 0}$. These problems can be solved with the simplex method (available with linprog in scipy or Matlab).
answered Jan 4 at 2:12
LinAlgLinAlg
10.1k1521
10.1k1521
$begingroup$
I assume in this instance $s$ is the vector of my minimisation condition and $w$ are the weights I'm applying to each? So that I'm then left with a scalar to minimise?
$endgroup$
– user403033
Jan 4 at 9:48
$begingroup$
@user403033 that is correct!
$endgroup$
– LinAlg
Jan 4 at 14:20
$begingroup$
Thanks, I'll give it a go with weightings of 1 across the board to start. A scalar condition will be much easier to deal with though. I assume if a particular entry of the P matrix is dominating the solution (due to relative size etc), to avoid this the problem is going to need to be reformulated?
$endgroup$
– user403033
Jan 4 at 15:03
$begingroup$
@user403033 you can either adjust the weights, or constrain two values of $P$ while optimizing the third value
$endgroup$
– LinAlg
Jan 16 at 20:06
add a comment |
$begingroup$
I assume in this instance $s$ is the vector of my minimisation condition and $w$ are the weights I'm applying to each? So that I'm then left with a scalar to minimise?
$endgroup$
– user403033
Jan 4 at 9:48
$begingroup$
@user403033 that is correct!
$endgroup$
– LinAlg
Jan 4 at 14:20
$begingroup$
Thanks, I'll give it a go with weightings of 1 across the board to start. A scalar condition will be much easier to deal with though. I assume if a particular entry of the P matrix is dominating the solution (due to relative size etc), to avoid this the problem is going to need to be reformulated?
$endgroup$
– user403033
Jan 4 at 15:03
$begingroup$
@user403033 you can either adjust the weights, or constrain two values of $P$ while optimizing the third value
$endgroup$
– LinAlg
Jan 16 at 20:06
$begingroup$
I assume in this instance $s$ is the vector of my minimisation condition and $w$ are the weights I'm applying to each? So that I'm then left with a scalar to minimise?
$endgroup$
– user403033
Jan 4 at 9:48
$begingroup$
I assume in this instance $s$ is the vector of my minimisation condition and $w$ are the weights I'm applying to each? So that I'm then left with a scalar to minimise?
$endgroup$
– user403033
Jan 4 at 9:48
$begingroup$
@user403033 that is correct!
$endgroup$
– LinAlg
Jan 4 at 14:20
$begingroup$
@user403033 that is correct!
$endgroup$
– LinAlg
Jan 4 at 14:20
$begingroup$
Thanks, I'll give it a go with weightings of 1 across the board to start. A scalar condition will be much easier to deal with though. I assume if a particular entry of the P matrix is dominating the solution (due to relative size etc), to avoid this the problem is going to need to be reformulated?
$endgroup$
– user403033
Jan 4 at 15:03
$begingroup$
Thanks, I'll give it a go with weightings of 1 across the board to start. A scalar condition will be much easier to deal with though. I assume if a particular entry of the P matrix is dominating the solution (due to relative size etc), to avoid this the problem is going to need to be reformulated?
$endgroup$
– user403033
Jan 4 at 15:03
$begingroup$
@user403033 you can either adjust the weights, or constrain two values of $P$ while optimizing the third value
$endgroup$
– LinAlg
Jan 16 at 20:06
$begingroup$
@user403033 you can either adjust the weights, or constrain two values of $P$ while optimizing the third value
$endgroup$
– LinAlg
Jan 16 at 20:06
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%2f3060426%2fmulti-objective-linear-optimisation-pareto-solution%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
$begingroup$
are you just looking for any Pareto Solution?
$endgroup$
– LinAlg
Jan 3 at 12:44
$begingroup$
Any efficient solution would suffice, from there it should be possible to extend to all efficient solutions.
$endgroup$
– user403033
Jan 3 at 14:40
$begingroup$
Is $w_1+w_2+w_3=1$ and addtionally $w_igeq 0 forall i in {1,2,3 } $?
$endgroup$
– callculus
Jan 3 at 19:05
$begingroup$
No, the weights would not have to sum to 1 but they would need to be positive.
$endgroup$
– user403033
Jan 4 at 9:45