Find KKT point of $min_{x in mathbb{R}^4} x^Tx$ subject to $x^TAx geq 1$.
$begingroup$
onsider the following problem:
$$min_{x in mathbb{R}^4} x^Tx$$
over $C={x in mathbb{R}^4 mid x^TAx geq 1}$ where $A in mathbb{R}^{4 times 4}$ is a symmetric matrix with two distinct positive eigenvalues and other eigenvalues of $A$ are nonpositive.
Find KKT point of the problem.
My try:
We can show that every Fritz-John point is a KKT point so we can write the following system of equlity and inequality to find the minimizer. Let $L(x, lambda)=x^Tx+lambda (1-x^TAx)$ be the Lagrangian. Then,
$$
2x + lambda(-2Ax)=0 tag{1}
$$
And,
$$
lambda geq 0 , x^TAx geq 1, lambda (1-x^TAx)=0 tag{2}
$$
From (1) we know that $lambda$ cannot be zero because otherwise $x=0$ which violates the constraint. So it is $lambda > 0$ and we have
$$
x = lambda(Ax)
$$
And,
$$
x^TAx=1
$$
How can I proceed?
optimization karush-kuhn-tucker
asked Dec 17 '18 at 3:50
SepideSepide
4558
$endgroup$
add a comment |
$begingroup$
onsider the following problem:
$$min_{x in mathbb{R}^4} x^Tx$$
over $C={x in mathbb{R}^4 mid x^TAx geq 1}$ where $A in mathbb{R}^{4 times 4}$ is a symmetric matrix with two distinct positive eigenvalues and other eigenvalues of $A$ are nonpositive.
Find KKT point of the problem.
My try:
We can show that every Fritz-John point is a KKT point so we can write the following system of equlity and inequality to find the minimizer. Let $L(x, lambda)=x^Tx+lambda (1-x^TAx)$ be the Lagrangian. Then,
$$
2x + lambda(-2Ax)=0 tag{1}
$$
And,
$$
lambda geq 0 , x^TAx geq 1, lambda (1-x^TAx)=0 tag{2}
$$
From (1) we know that $lambda$ cannot be zero because otherwise $x=0$ which violates the constraint. So it is $lambda > 0$ and we have
$$
x = lambda(Ax)
$$
And,
$$
x^TAx=1
$$
How can I proceed?
optimization karush-kuhn-tucker
asked Dec 17 '18 at 3:50
SepideSepide
4558
$endgroup$
$begingroup$
There is an extra minus in (1).
$endgroup$
– LinAlg
Dec 17 '18 at 13:39
add a comment |
$begingroup$
onsider the following problem:
$$min_{x in mathbb{R}^4} x^Tx$$
over $C={x in mathbb{R}^4 mid x^TAx geq 1}$ where $A in mathbb{R}^{4 times 4}$ is a symmetric matrix with two distinct positive eigenvalues and other eigenvalues of $A$ are nonpositive.
Find KKT point of the problem.
My try:
We can show that every Fritz-John point is a KKT point so we can write the following system of equlity and inequality to find the minimizer. Let $L(x, lambda)=x^Tx+lambda (1-x^TAx)$ be the Lagrangian. Then,
$$
2x + lambda(-2Ax)=0 tag{1}
$$
And,
$$
lambda geq 0 , x^TAx geq 1, lambda (1-x^TAx)=0 tag{2}
$$
From (1) we know that $lambda$ cannot be zero because otherwise $x=0$ which violates the constraint. So it is $lambda > 0$ and we have
$$
x = lambda(Ax)
$$
And,
$$
x^TAx=1
$$
How can I proceed?
optimization karush-kuhn-tucker
asked Dec 17 '18 at 3:50
SepideSepide
4558
$endgroup$
onsider the following problem:
$$min_{x in mathbb{R}^4} x^Tx$$
over $C={x in mathbb{R}^4 mid x^TAx geq 1}$ where $A in mathbb{R}^{4 times 4}$ is a symmetric matrix with two distinct positive eigenvalues and other eigenvalues of $A$ are nonpositive.
Find KKT point of the problem.
My try:
We can show that every Fritz-John point is a KKT point so we can write the following system of equlity and inequality to find the minimizer. Let $L(x, lambda)=x^Tx+lambda (1-x^TAx)$ be the Lagrangian. Then,
$$
2x + lambda(-2Ax)=0 tag{1}
$$
And,
$$
lambda geq 0 , x^TAx geq 1, lambda (1-x^TAx)=0 tag{2}
$$
From (1) we know that $lambda$ cannot be zero because otherwise $x=0$ which violates the constraint. So it is $lambda > 0$ and we have
$$
x = lambda(Ax)
$$
And,
$$
x^TAx=1
$$
How can I proceed?
optimization karush-kuhn-tucker
optimization karush-kuhn-tucker
asked Dec 17 '18 at 3:50
SepideSepide
4558
asked Dec 17 '18 at 3:50
SepideSepide
4558
edited Dec 18 '18 at 19:48
Sepide
asked Dec 17 '18 at 3:50
SepideSepide
4558
asked Dec 17 '18 at 3:50
SepideSepide
4558
asked Dec 17 '18 at 3:50
SepideSepide
4558
4558
$begingroup$
There is an extra minus in (1).
$endgroup$
– LinAlg
Dec 17 '18 at 13:39
add a comment |
$begingroup$
There is an extra minus in (1).
$endgroup$
– LinAlg
Dec 17 '18 at 13:39
$begingroup$
There is an extra minus in (1).
$endgroup$
– LinAlg
Dec 17 '18 at 13:39
$begingroup$
There is an extra minus in (1).
$endgroup$
– LinAlg
Dec 17 '18 at 13:39
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
From $x=lambda Ax$ you know that $x$ is an eigenvector of $A$ (since $Ax = (1/lambda) x$). Let $x$ be an eigenvector with eigenvalue $mu$. Since $x^T A x = 1$, $mu x^Tx = 1$, so $x^Tx = 1/mu$. The objective value is therefore minimized by the eigenvector with the largest eigenvalue.
answered Dec 17 '18 at 13:43
LinAlgLinAlg
10k1521
$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%2f3043505%2ffind-kkt-point-of-min-x-in-mathbbr4-xtx-subject-to-xtax-geq-1%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$
From $x=lambda Ax$ you know that $x$ is an eigenvector of $A$ (since $Ax = (1/lambda) x$). Let $x$ be an eigenvector with eigenvalue $mu$. Since $x^T A x = 1$, $mu x^Tx = 1$, so $x^Tx = 1/mu$. The objective value is therefore minimized by the eigenvector with the largest eigenvalue.
answered Dec 17 '18 at 13:43
LinAlgLinAlg
10k1521
$endgroup$
add a comment |
$begingroup$
From $x=lambda Ax$ you know that $x$ is an eigenvector of $A$ (since $Ax = (1/lambda) x$). Let $x$ be an eigenvector with eigenvalue $mu$. Since $x^T A x = 1$, $mu x^Tx = 1$, so $x^Tx = 1/mu$. The objective value is therefore minimized by the eigenvector with the largest eigenvalue.
answered Dec 17 '18 at 13:43
LinAlgLinAlg
10k1521
$endgroup$
add a comment |
$begingroup$
From $x=lambda Ax$ you know that $x$ is an eigenvector of $A$ (since $Ax = (1/lambda) x$). Let $x$ be an eigenvector with eigenvalue $mu$. Since $x^T A x = 1$, $mu x^Tx = 1$, so $x^Tx = 1/mu$. The objective value is therefore minimized by the eigenvector with the largest eigenvalue.
answered Dec 17 '18 at 13:43
LinAlgLinAlg
10k1521
$endgroup$
From $x=lambda Ax$ you know that $x$ is an eigenvector of $A$ (since $Ax = (1/lambda) x$). Let $x$ be an eigenvector with eigenvalue $mu$. Since $x^T A x = 1$, $mu x^Tx = 1$, so $x^Tx = 1/mu$. The objective value is therefore minimized by the eigenvector with the largest eigenvalue.
answered Dec 17 '18 at 13:43
LinAlgLinAlg
10k1521
answered Dec 17 '18 at 13:43
LinAlgLinAlg
10k1521
answered Dec 17 '18 at 13:43
LinAlgLinAlg
10k1521
answered Dec 17 '18 at 13:43
LinAlgLinAlg
10k1521
10k1521
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%2f3043505%2ffind-kkt-point-of-min-x-in-mathbbr4-xtx-subject-to-xtax-geq-1%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$
There is an extra minus in (1).
$endgroup$
– LinAlg
Dec 17 '18 at 13:39