The Exponential Cone and Semi-definite programming
$begingroup$
I have a problem at the intersection of a range of topics: exponential programming, semi-definite programming and computer science, that I am having trouble finding a decent method for solving.
Take $A_iinmathbb{R}^{dtimes d}$ with $A_i = A^T_i$, $iinmathcal{I}$ and $mathcal{I}$ is a finite set of indices. $-infty < text{tr}(A_i)< 0, forall iinmathcal{I}$. We also have $b_iinmathbb{R}^+$.
We seek $X_iinmathbb{R}^{d times d}$ that solves the optimization problem
begin{align}
&min sum_i b_i e^{text{tr}(A_i X_i)} \
text{s.t.} & sum_i e^{text{tr}(X_i)} leq mathcal{C} \
& | X_i |^2_{Fr} leq alpha\
& X_i = X^T_i
end{align}
This can be solved using CVX, and thus satisfies Disciplined Convex Programming. The problem is that because it is semi-definite programming on the exponential cone, it requires an approximation of the cone, thus is quite slow. I have also used the large blunt object that is NLOPT which performs quickly, but this seems unsatisfactory given it doesn't really exploit the convex structure.
My question is: What other methods could I reasonably attack this problem with? In particular ones that might work in parallel (the real set $mathcal{I}$ is sufficiently large that the problem is distributed across many computers).
convex-optimization semidefinite-programming
asked Jan 11 at 15:46
NeedsToKnowMoreMathsNeedsToKnowMoreMaths
728
$endgroup$
add a comment |
$begingroup$
I have a problem at the intersection of a range of topics: exponential programming, semi-definite programming and computer science, that I am having trouble finding a decent method for solving.
Take $A_iinmathbb{R}^{dtimes d}$ with $A_i = A^T_i$, $iinmathcal{I}$ and $mathcal{I}$ is a finite set of indices. $-infty < text{tr}(A_i)< 0, forall iinmathcal{I}$. We also have $b_iinmathbb{R}^+$.
We seek $X_iinmathbb{R}^{d times d}$ that solves the optimization problem
begin{align}
&min sum_i b_i e^{text{tr}(A_i X_i)} \
text{s.t.} & sum_i e^{text{tr}(X_i)} leq mathcal{C} \
& | X_i |^2_{Fr} leq alpha\
& X_i = X^T_i
end{align}
This can be solved using CVX, and thus satisfies Disciplined Convex Programming. The problem is that because it is semi-definite programming on the exponential cone, it requires an approximation of the cone, thus is quite slow. I have also used the large blunt object that is NLOPT which performs quickly, but this seems unsatisfactory given it doesn't really exploit the convex structure.
My question is: What other methods could I reasonably attack this problem with? In particular ones that might work in parallel (the real set $mathcal{I}$ is sufficiently large that the problem is distributed across many computers).
convex-optimization semidefinite-programming
asked Jan 11 at 15:46
NeedsToKnowMoreMathsNeedsToKnowMoreMaths
728
$endgroup$
1
$begingroup$
Your terminology is a bit off. This isn't semidefinite programming. Semidefinite programs can only have linear matrix inequalities for nonlinearities, and this has none of those. This is simply a smooth nonlinear program.
$endgroup$
– Michael Grant
Jan 12 at 2:52
$begingroup$
And I see nothing whatsoever wrong with using NLOPT, if its performance and accuracy are acceptable.
$endgroup$
– Michael Grant
Jan 12 at 2:54
$begingroup$
Ah thank you, I see now that all the matrix operations can be re-written as linear sums of functions of the indices of the matrices. I'm looking into TAO for the time being.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:24
add a comment |
$begingroup$
I have a problem at the intersection of a range of topics: exponential programming, semi-definite programming and computer science, that I am having trouble finding a decent method for solving.
Take $A_iinmathbb{R}^{dtimes d}$ with $A_i = A^T_i$, $iinmathcal{I}$ and $mathcal{I}$ is a finite set of indices. $-infty < text{tr}(A_i)< 0, forall iinmathcal{I}$. We also have $b_iinmathbb{R}^+$.
We seek $X_iinmathbb{R}^{d times d}$ that solves the optimization problem
begin{align}
&min sum_i b_i e^{text{tr}(A_i X_i)} \
text{s.t.} & sum_i e^{text{tr}(X_i)} leq mathcal{C} \
& | X_i |^2_{Fr} leq alpha\
& X_i = X^T_i
end{align}
This can be solved using CVX, and thus satisfies Disciplined Convex Programming. The problem is that because it is semi-definite programming on the exponential cone, it requires an approximation of the cone, thus is quite slow. I have also used the large blunt object that is NLOPT which performs quickly, but this seems unsatisfactory given it doesn't really exploit the convex structure.
My question is: What other methods could I reasonably attack this problem with? In particular ones that might work in parallel (the real set $mathcal{I}$ is sufficiently large that the problem is distributed across many computers).
convex-optimization semidefinite-programming
asked Jan 11 at 15:46
NeedsToKnowMoreMathsNeedsToKnowMoreMaths
728
$endgroup$
I have a problem at the intersection of a range of topics: exponential programming, semi-definite programming and computer science, that I am having trouble finding a decent method for solving.
Take $A_iinmathbb{R}^{dtimes d}$ with $A_i = A^T_i$, $iinmathcal{I}$ and $mathcal{I}$ is a finite set of indices. $-infty < text{tr}(A_i)< 0, forall iinmathcal{I}$. We also have $b_iinmathbb{R}^+$.
We seek $X_iinmathbb{R}^{d times d}$ that solves the optimization problem
begin{align}
&min sum_i b_i e^{text{tr}(A_i X_i)} \
text{s.t.} & sum_i e^{text{tr}(X_i)} leq mathcal{C} \
& | X_i |^2_{Fr} leq alpha\
& X_i = X^T_i
end{align}
This can be solved using CVX, and thus satisfies Disciplined Convex Programming. The problem is that because it is semi-definite programming on the exponential cone, it requires an approximation of the cone, thus is quite slow. I have also used the large blunt object that is NLOPT which performs quickly, but this seems unsatisfactory given it doesn't really exploit the convex structure.
My question is: What other methods could I reasonably attack this problem with? In particular ones that might work in parallel (the real set $mathcal{I}$ is sufficiently large that the problem is distributed across many computers).
convex-optimization semidefinite-programming
convex-optimization semidefinite-programming
asked Jan 11 at 15:46
NeedsToKnowMoreMathsNeedsToKnowMoreMaths
728
asked Jan 11 at 15:46
NeedsToKnowMoreMathsNeedsToKnowMoreMaths
728
asked Jan 11 at 15:46
NeedsToKnowMoreMathsNeedsToKnowMoreMaths
728
asked Jan 11 at 15:46
NeedsToKnowMoreMathsNeedsToKnowMoreMaths
728
asked Jan 11 at 15:46
NeedsToKnowMoreMathsNeedsToKnowMoreMaths
728
728
1
$begingroup$
Your terminology is a bit off. This isn't semidefinite programming. Semidefinite programs can only have linear matrix inequalities for nonlinearities, and this has none of those. This is simply a smooth nonlinear program.
$endgroup$
– Michael Grant
Jan 12 at 2:52
$begingroup$
And I see nothing whatsoever wrong with using NLOPT, if its performance and accuracy are acceptable.
$endgroup$
– Michael Grant
Jan 12 at 2:54
$begingroup$
Ah thank you, I see now that all the matrix operations can be re-written as linear sums of functions of the indices of the matrices. I'm looking into TAO for the time being.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:24
add a comment |
1
$begingroup$
Your terminology is a bit off. This isn't semidefinite programming. Semidefinite programs can only have linear matrix inequalities for nonlinearities, and this has none of those. This is simply a smooth nonlinear program.
$endgroup$
– Michael Grant
Jan 12 at 2:52
$begingroup$
And I see nothing whatsoever wrong with using NLOPT, if its performance and accuracy are acceptable.
$endgroup$
– Michael Grant
Jan 12 at 2:54
$begingroup$
Ah thank you, I see now that all the matrix operations can be re-written as linear sums of functions of the indices of the matrices. I'm looking into TAO for the time being.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:24
1
1
$begingroup$
Your terminology is a bit off. This isn't semidefinite programming. Semidefinite programs can only have linear matrix inequalities for nonlinearities, and this has none of those. This is simply a smooth nonlinear program.
$endgroup$
– Michael Grant
Jan 12 at 2:52
$begingroup$
Your terminology is a bit off. This isn't semidefinite programming. Semidefinite programs can only have linear matrix inequalities for nonlinearities, and this has none of those. This is simply a smooth nonlinear program.
$endgroup$
– Michael Grant
Jan 12 at 2:52
$begingroup$
And I see nothing whatsoever wrong with using NLOPT, if its performance and accuracy are acceptable.
$endgroup$
– Michael Grant
Jan 12 at 2:54
$begingroup$
And I see nothing whatsoever wrong with using NLOPT, if its performance and accuracy are acceptable.
$endgroup$
– Michael Grant
Jan 12 at 2:54
$begingroup$
Ah thank you, I see now that all the matrix operations can be re-written as linear sums of functions of the indices of the matrices. I'm looking into TAO for the time being.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:24
$begingroup$
Ah thank you, I see now that all the matrix operations can be re-written as linear sums of functions of the indices of the matrices. I'm looking into TAO for the time being.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:24
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are solvers that can work directly with the exponential cone. Look at ECOS and the forthcoming Mosek version 9. If your problems are of a size where interior point methods are viable, one of those solvers might work for you.
What are the actual sizes of your problem instances?
answered Jan 11 at 21:29
Brian BorchersBrian Borchers
6,16611320
$endgroup$
$begingroup$
The optimization arises in a finite element post process, so its typically of the order of number of elements in the mesh. This can be up in the 1e7 territory, at which point the mesh is already distributed over a large number processors. I'm investigating the TAO optimizer for the time being, as it seems to be the parallel optimizer of choice.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:26
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%2f3069990%2fthe-exponential-cone-and-semi-definite-programming%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$
There are solvers that can work directly with the exponential cone. Look at ECOS and the forthcoming Mosek version 9. If your problems are of a size where interior point methods are viable, one of those solvers might work for you.
What are the actual sizes of your problem instances?
answered Jan 11 at 21:29
Brian BorchersBrian Borchers
6,16611320
$endgroup$
$begingroup$
The optimization arises in a finite element post process, so its typically of the order of number of elements in the mesh. This can be up in the 1e7 territory, at which point the mesh is already distributed over a large number processors. I'm investigating the TAO optimizer for the time being, as it seems to be the parallel optimizer of choice.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:26
add a comment |
$begingroup$
There are solvers that can work directly with the exponential cone. Look at ECOS and the forthcoming Mosek version 9. If your problems are of a size where interior point methods are viable, one of those solvers might work for you.
What are the actual sizes of your problem instances?
answered Jan 11 at 21:29
Brian BorchersBrian Borchers
6,16611320
$endgroup$
$begingroup$
The optimization arises in a finite element post process, so its typically of the order of number of elements in the mesh. This can be up in the 1e7 territory, at which point the mesh is already distributed over a large number processors. I'm investigating the TAO optimizer for the time being, as it seems to be the parallel optimizer of choice.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:26
add a comment |
$begingroup$
There are solvers that can work directly with the exponential cone. Look at ECOS and the forthcoming Mosek version 9. If your problems are of a size where interior point methods are viable, one of those solvers might work for you.
What are the actual sizes of your problem instances?
answered Jan 11 at 21:29
Brian BorchersBrian Borchers
6,16611320
$endgroup$
There are solvers that can work directly with the exponential cone. Look at ECOS and the forthcoming Mosek version 9. If your problems are of a size where interior point methods are viable, one of those solvers might work for you.
What are the actual sizes of your problem instances?
answered Jan 11 at 21:29
Brian BorchersBrian Borchers
6,16611320
edited Jan 11 at 21:46
answered Jan 11 at 21:29
Brian BorchersBrian Borchers
6,16611320
answered Jan 11 at 21:29
Brian BorchersBrian Borchers
6,16611320
answered Jan 11 at 21:29
Brian BorchersBrian Borchers
6,16611320
6,16611320
$begingroup$
The optimization arises in a finite element post process, so its typically of the order of number of elements in the mesh. This can be up in the 1e7 territory, at which point the mesh is already distributed over a large number processors. I'm investigating the TAO optimizer for the time being, as it seems to be the parallel optimizer of choice.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:26
add a comment |
$begingroup$
The optimization arises in a finite element post process, so its typically of the order of number of elements in the mesh. This can be up in the 1e7 territory, at which point the mesh is already distributed over a large number processors. I'm investigating the TAO optimizer for the time being, as it seems to be the parallel optimizer of choice.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:26
$begingroup$
The optimization arises in a finite element post process, so its typically of the order of number of elements in the mesh. This can be up in the 1e7 territory, at which point the mesh is already distributed over a large number processors. I'm investigating the TAO optimizer for the time being, as it seems to be the parallel optimizer of choice.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:26
$begingroup$
The optimization arises in a finite element post process, so its typically of the order of number of elements in the mesh. This can be up in the 1e7 territory, at which point the mesh is already distributed over a large number processors. I'm investigating the TAO optimizer for the time being, as it seems to be the parallel optimizer of choice.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:26
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%2f3069990%2fthe-exponential-cone-and-semi-definite-programming%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$
Your terminology is a bit off. This isn't semidefinite programming. Semidefinite programs can only have linear matrix inequalities for nonlinearities, and this has none of those. This is simply a smooth nonlinear program.
$endgroup$
– Michael Grant
Jan 12 at 2:52
$begingroup$
And I see nothing whatsoever wrong with using NLOPT, if its performance and accuracy are acceptable.
$endgroup$
– Michael Grant
Jan 12 at 2:54
$begingroup$
Ah thank you, I see now that all the matrix operations can be re-written as linear sums of functions of the indices of the matrices. I'm looking into TAO for the time being.
$endgroup$
– NeedsToKnowMoreMaths
Feb 27 at 14:24