Mixing
How can I solve $inf_{x in X} x^T(Ax + b) + sum_{i=1}^n x_i log(x_i)$ in a closed form depending on...
$begingroup$
I'm trying to solve the minimization problem
$$inf_{x in X} x^T(Ax + b) + sum_{i=1}^n x_i log(x_i)$$
where $b in mathbb{R}^n$, $X subset mathbb{R}^n$ is a convex set. And $A$ is a symmetric and positive definite matrix. The optimality conditions give me something like
$$-b in 2Ax + vec{1} + L(x) + N_X(x)$$
where $L(x)$ represents the vector in $mathbb{R}^n$ obtained by taking the elementwise logarithm of $x$; i.e., $[L(x)]_i=log x_i$.
The problem is how do I take that cone out of the inclusion. If there wasn't that log term it would become a projection on the set $X$. Is there a trick to make this as a projection on $X$ of other vector or something?
I'd appreciate any help or any paper/book reference where there's some information about this kind of problem
optimization convex-analysis convex-optimization
edited Mar 23 '15 at 19:40
Michael Grant
15.2k12045
asked Mar 23 '15 at 18:58
karlaboskarlabos
401414
$endgroup$
add a comment |
$begingroup$
I'm trying to solve the minimization problem
$$inf_{x in X} x^T(Ax + b) + sum_{i=1}^n x_i log(x_i)$$
where $b in mathbb{R}^n$, $X subset mathbb{R}^n$ is a convex set. And $A$ is a symmetric and positive definite matrix. The optimality conditions give me something like
$$-b in 2Ax + vec{1} + L(x) + N_X(x)$$
where $L(x)$ represents the vector in $mathbb{R}^n$ obtained by taking the elementwise logarithm of $x$; i.e., $[L(x)]_i=log x_i$.
The problem is how do I take that cone out of the inclusion. If there wasn't that log term it would become a projection on the set $X$. Is there a trick to make this as a projection on $X$ of other vector or something?
I'd appreciate any help or any paper/book reference where there's some information about this kind of problem
optimization convex-analysis convex-optimization
edited Mar 23 '15 at 19:40
Michael Grant
15.2k12045
asked Mar 23 '15 at 18:58
karlaboskarlabos
401414
$endgroup$
1
$begingroup$
There is no closed form. You have to solve this numerically, even if $Xequivmathbb{R}^n$.
$endgroup$
– Michael Grant
Mar 23 '15 at 19:38
$begingroup$
I see. In this case do you know where can I find info on numerically solving this?
$endgroup$
– karlabos
Mar 23 '15 at 22:46
$begingroup$
I would recommend looking into CVX (incidentally, it is partially authored by the previous commenter): cvxr.com/cvx.
$endgroup$
– ChrKroer
Mar 24 '15 at 18:49
add a comment |
$begingroup$
I'm trying to solve the minimization problem
$$inf_{x in X} x^T(Ax + b) + sum_{i=1}^n x_i log(x_i)$$
where $b in mathbb{R}^n$, $X subset mathbb{R}^n$ is a convex set. And $A$ is a symmetric and positive definite matrix. The optimality conditions give me something like
$$-b in 2Ax + vec{1} + L(x) + N_X(x)$$
where $L(x)$ represents the vector in $mathbb{R}^n$ obtained by taking the elementwise logarithm of $x$; i.e., $[L(x)]_i=log x_i$.
The problem is how do I take that cone out of the inclusion. If there wasn't that log term it would become a projection on the set $X$. Is there a trick to make this as a projection on $X$ of other vector or something?
I'd appreciate any help or any paper/book reference where there's some information about this kind of problem
optimization convex-analysis convex-optimization
edited Mar 23 '15 at 19:40
Michael Grant
15.2k12045
asked Mar 23 '15 at 18:58
karlaboskarlabos
401414
$endgroup$
I'm trying to solve the minimization problem
$$inf_{x in X} x^T(Ax + b) + sum_{i=1}^n x_i log(x_i)$$
where $b in mathbb{R}^n$, $X subset mathbb{R}^n$ is a convex set. And $A$ is a symmetric and positive definite matrix. The optimality conditions give me something like
$$-b in 2Ax + vec{1} + L(x) + N_X(x)$$
where $L(x)$ represents the vector in $mathbb{R}^n$ obtained by taking the elementwise logarithm of $x$; i.e., $[L(x)]_i=log x_i$.
The problem is how do I take that cone out of the inclusion. If there wasn't that log term it would become a projection on the set $X$. Is there a trick to make this as a projection on $X$ of other vector or something?
I'd appreciate any help or any paper/book reference where there's some information about this kind of problem
optimization convex-analysis convex-optimization
optimization convex-analysis convex-optimization
edited Mar 23 '15 at 19:40
Michael Grant
15.2k12045
asked Mar 23 '15 at 18:58
karlaboskarlabos
401414
edited Mar 23 '15 at 19:40
Michael Grant
15.2k12045
asked Mar 23 '15 at 18:58
karlaboskarlabos
401414
edited Mar 23 '15 at 19:40
Michael Grant
15.2k12045
edited Mar 23 '15 at 19:40
Michael Grant
15.2k12045
edited Mar 23 '15 at 19:40
Michael Grant
15.2k12045
15.2k12045
asked Mar 23 '15 at 18:58
karlaboskarlabos
401414
asked Mar 23 '15 at 18:58
karlaboskarlabos
401414
asked Mar 23 '15 at 18:58
karlaboskarlabos
401414
401414
1
$begingroup$
There is no closed form. You have to solve this numerically, even if $Xequivmathbb{R}^n$.
$endgroup$
– Michael Grant
Mar 23 '15 at 19:38
$begingroup$
I see. In this case do you know where can I find info on numerically solving this?
$endgroup$
– karlabos
Mar 23 '15 at 22:46
$begingroup$
I would recommend looking into CVX (incidentally, it is partially authored by the previous commenter): cvxr.com/cvx.
$endgroup$
– ChrKroer
Mar 24 '15 at 18:49
add a comment |
1
$begingroup$
There is no closed form. You have to solve this numerically, even if $Xequivmathbb{R}^n$.
$endgroup$
– Michael Grant
Mar 23 '15 at 19:38
$begingroup$
I see. In this case do you know where can I find info on numerically solving this?
$endgroup$
– karlabos
Mar 23 '15 at 22:46
$begingroup$
I would recommend looking into CVX (incidentally, it is partially authored by the previous commenter): cvxr.com/cvx.
$endgroup$
– ChrKroer
Mar 24 '15 at 18:49
1
1
$begingroup$
There is no closed form. You have to solve this numerically, even if $Xequivmathbb{R}^n$.
$endgroup$
– Michael Grant
Mar 23 '15 at 19:38
$begingroup$
There is no closed form. You have to solve this numerically, even if $Xequivmathbb{R}^n$.
$endgroup$
– Michael Grant
Mar 23 '15 at 19:38
$begingroup$
I see. In this case do you know where can I find info on numerically solving this?
$endgroup$
– karlabos
Mar 23 '15 at 22:46
$begingroup$
I see. In this case do you know where can I find info on numerically solving this?
$endgroup$
– karlabos
Mar 23 '15 at 22:46
$begingroup$
I would recommend looking into CVX (incidentally, it is partially authored by the previous commenter): cvxr.com/cvx.
$endgroup$
– ChrKroer
Mar 24 '15 at 18:49
$begingroup$
I would recommend looking into CVX (incidentally, it is partially authored by the previous commenter): cvxr.com/cvx.
$endgroup$
– ChrKroer
Mar 24 '15 at 18:49
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Starting from your inclusion
$$-b in 2Ax + vec{1} + L(x) + N_X(x),$$
we can add $x$ on both sides and re-arrange to get:
$$x-2Ax-vec{1}-L(x)-b in (I+N_X)(x),$$
where $I$ denotes the identity operator $xmapsto x$.
We can now invert to get
$$x = P_Xbig(x-2Ax-vec{1}-L(x)-bbig).$$
This reformulation takes the normal cone operator out of
your problem and converts it to a fixed point problem
that you might try to approach with fixed-point theoretic
algorithms.
answered Jan 31 at 22:03
max_zornmax_zorn
3,44061429
$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%2f1203079%2fhow-can-i-solve-inf-x-in-x-xtax-b-sum-i-1n-x-i-logx-i-in-a-c%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$
Starting from your inclusion
$$-b in 2Ax + vec{1} + L(x) + N_X(x),$$
we can add $x$ on both sides and re-arrange to get:
$$x-2Ax-vec{1}-L(x)-b in (I+N_X)(x),$$
where $I$ denotes the identity operator $xmapsto x$.
We can now invert to get
$$x = P_Xbig(x-2Ax-vec{1}-L(x)-bbig).$$
This reformulation takes the normal cone operator out of
your problem and converts it to a fixed point problem
that you might try to approach with fixed-point theoretic
algorithms.
answered Jan 31 at 22:03
max_zornmax_zorn
3,44061429
$endgroup$
add a comment |
$begingroup$
Starting from your inclusion
$$-b in 2Ax + vec{1} + L(x) + N_X(x),$$
we can add $x$ on both sides and re-arrange to get:
$$x-2Ax-vec{1}-L(x)-b in (I+N_X)(x),$$
where $I$ denotes the identity operator $xmapsto x$.
We can now invert to get
$$x = P_Xbig(x-2Ax-vec{1}-L(x)-bbig).$$
This reformulation takes the normal cone operator out of
your problem and converts it to a fixed point problem
that you might try to approach with fixed-point theoretic
algorithms.
answered Jan 31 at 22:03
max_zornmax_zorn
3,44061429
$endgroup$
add a comment |
$begingroup$
Starting from your inclusion
$$-b in 2Ax + vec{1} + L(x) + N_X(x),$$
we can add $x$ on both sides and re-arrange to get:
$$x-2Ax-vec{1}-L(x)-b in (I+N_X)(x),$$
where $I$ denotes the identity operator $xmapsto x$.
We can now invert to get
$$x = P_Xbig(x-2Ax-vec{1}-L(x)-bbig).$$
This reformulation takes the normal cone operator out of
your problem and converts it to a fixed point problem
that you might try to approach with fixed-point theoretic
algorithms.
answered Jan 31 at 22:03
max_zornmax_zorn
3,44061429
$endgroup$
Starting from your inclusion
$$-b in 2Ax + vec{1} + L(x) + N_X(x),$$
we can add $x$ on both sides and re-arrange to get:
$$x-2Ax-vec{1}-L(x)-b in (I+N_X)(x),$$
where $I$ denotes the identity operator $xmapsto x$.
We can now invert to get
$$x = P_Xbig(x-2Ax-vec{1}-L(x)-bbig).$$
This reformulation takes the normal cone operator out of
your problem and converts it to a fixed point problem
that you might try to approach with fixed-point theoretic
algorithms.
answered Jan 31 at 22:03
max_zornmax_zorn
3,44061429
answered Jan 31 at 22:03
max_zornmax_zorn
3,44061429
answered Jan 31 at 22:03
max_zornmax_zorn
3,44061429
answered Jan 31 at 22:03
max_zornmax_zorn
3,44061429
3,44061429
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%2f1203079%2fhow-can-i-solve-inf-x-in-x-xtax-b-sum-i-1n-x-i-logx-i-in-a-c%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$
There is no closed form. You have to solve this numerically, even if $Xequivmathbb{R}^n$.
$endgroup$
– Michael Grant
Mar 23 '15 at 19:38
$begingroup$
I see. In this case do you know where can I find info on numerically solving this?
$endgroup$
– karlabos
Mar 23 '15 at 22:46
$begingroup$
I would recommend looking into CVX (incidentally, it is partially authored by the previous commenter): cvxr.com/cvx.
$endgroup$
– ChrKroer
Mar 24 '15 at 18:49