What is the maximum value of $x^TAx$ subject to $xin{pm1}^n$?
up vote
2
down vote
favorite
Let $A in mathbb{R}^{ntimes n}$ be symmetric and positive definite. What is the following maximum?
$$max_{xin{pm1}^n}x^T A x$$
My attempt:
if all $a_{ij}geq 0$, then
begin{equation}
max_{xin{pm1}^n}x^TAx=sum a_{ij}
end{equation}
and in this case $x=[1quad 1quadcdotsquad 1]'$ or $x=[-1quad -1quadcdotsquad -1]'$.
if some $a_{ij}<0$, then situation is not clear, but we know that $x^TAxleqsum{|a_{ij}|}$.
For example:
begin{equation}
A=
begin{bmatrix}
2 & 3 & 1 \
3 & 10 & -8 \
1 & -8 & 17
end{bmatrix}.
end{equation}
begin{equation}
max_{xin{pm1}^n}x^TAx=49<sum |a_{ij}|=53
end{equation}
and in this case $x=[1quad1quad-1]'$ or $x=[-1quad-1quad1]'$. So idea is to sacrifice $2a_{13}$ since it is smaller than $2a_{23}$ and $2a_{12}$.
Is there any systematic way to tell the maximum of $x^TAx$ for any $n$ if $A$ is given? and if yes how to find $x$ that will give the maximum? Any suggestions are welcome :)
optimization positive-definite non-convex-optimization
asked 23 hours ago
Lee
606
|
show 2 more comments
up vote
2
down vote
favorite
Let $A in mathbb{R}^{ntimes n}$ be symmetric and positive definite. What is the following maximum?
$$max_{xin{pm1}^n}x^T A x$$
My attempt:
if all $a_{ij}geq 0$, then
begin{equation}
max_{xin{pm1}^n}x^TAx=sum a_{ij}
end{equation}
and in this case $x=[1quad 1quadcdotsquad 1]'$ or $x=[-1quad -1quadcdotsquad -1]'$.
if some $a_{ij}<0$, then situation is not clear, but we know that $x^TAxleqsum{|a_{ij}|}$.
For example:
begin{equation}
A=
begin{bmatrix}
2 & 3 & 1 \
3 & 10 & -8 \
1 & -8 & 17
end{bmatrix}.
end{equation}
begin{equation}
max_{xin{pm1}^n}x^TAx=49<sum |a_{ij}|=53
end{equation}
and in this case $x=[1quad1quad-1]'$ or $x=[-1quad-1quad1]'$. So idea is to sacrifice $2a_{13}$ since it is smaller than $2a_{23}$ and $2a_{12}$.
Is there any systematic way to tell the maximum of $x^TAx$ for any $n$ if $A$ is given? and if yes how to find $x$ that will give the maximum? Any suggestions are welcome :)
optimization positive-definite non-convex-optimization
asked 23 hours ago
Lee
606
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
22 hours ago
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
22 hours ago
1
what I wanted to say is that all elements of $x$ are equal to 1 or -1, so I think I will better stick to $|x_i|=1$
– Lee
22 hours ago
@Lee and Rodrigo : Both of you are right. Sorry it is my mistake still, precising that $i$ goes from $1$ to $n$ would not hurt. An alternative way to write is simply $xin{-1,1}^n$
– Surb
22 hours ago
1
This is known as a Binary Quadratic Problem and is hard. There are some solvers for it, for instance www-lipn.univ-paris13.fr/BiqCrunch and you can have some success solving a sequence of semidefinite relaxations.
– Michal Adamaszek
20 hours ago
|
show 2 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $A in mathbb{R}^{ntimes n}$ be symmetric and positive definite. What is the following maximum?
$$max_{xin{pm1}^n}x^T A x$$
My attempt:
if all $a_{ij}geq 0$, then
begin{equation}
max_{xin{pm1}^n}x^TAx=sum a_{ij}
end{equation}
and in this case $x=[1quad 1quadcdotsquad 1]'$ or $x=[-1quad -1quadcdotsquad -1]'$.
if some $a_{ij}<0$, then situation is not clear, but we know that $x^TAxleqsum{|a_{ij}|}$.
For example:
begin{equation}
A=
begin{bmatrix}
2 & 3 & 1 \
3 & 10 & -8 \
1 & -8 & 17
end{bmatrix}.
end{equation}
begin{equation}
max_{xin{pm1}^n}x^TAx=49<sum |a_{ij}|=53
end{equation}
and in this case $x=[1quad1quad-1]'$ or $x=[-1quad-1quad1]'$. So idea is to sacrifice $2a_{13}$ since it is smaller than $2a_{23}$ and $2a_{12}$.
Is there any systematic way to tell the maximum of $x^TAx$ for any $n$ if $A$ is given? and if yes how to find $x$ that will give the maximum? Any suggestions are welcome :)
optimization positive-definite non-convex-optimization
asked 23 hours ago
Lee
606
Let $A in mathbb{R}^{ntimes n}$ be symmetric and positive definite. What is the following maximum?
$$max_{xin{pm1}^n}x^T A x$$
My attempt:
if all $a_{ij}geq 0$, then
begin{equation}
max_{xin{pm1}^n}x^TAx=sum a_{ij}
end{equation}
and in this case $x=[1quad 1quadcdotsquad 1]'$ or $x=[-1quad -1quadcdotsquad -1]'$.
if some $a_{ij}<0$, then situation is not clear, but we know that $x^TAxleqsum{|a_{ij}|}$.
For example:
begin{equation}
A=
begin{bmatrix}
2 & 3 & 1 \
3 & 10 & -8 \
1 & -8 & 17
end{bmatrix}.
end{equation}
begin{equation}
max_{xin{pm1}^n}x^TAx=49<sum |a_{ij}|=53
end{equation}
and in this case $x=[1quad1quad-1]'$ or $x=[-1quad-1quad1]'$. So idea is to sacrifice $2a_{13}$ since it is smaller than $2a_{23}$ and $2a_{12}$.
Is there any systematic way to tell the maximum of $x^TAx$ for any $n$ if $A$ is given? and if yes how to find $x$ that will give the maximum? Any suggestions are welcome :)
optimization positive-definite non-convex-optimization
optimization positive-definite non-convex-optimization
asked 23 hours ago
Lee
606
asked 23 hours ago
Lee
606
edited 22 hours ago
asked 23 hours ago
Lee
606
asked 23 hours ago
Lee
606
asked 23 hours ago
Lee
606
606
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
22 hours ago
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
22 hours ago
1
what I wanted to say is that all elements of $x$ are equal to 1 or -1, so I think I will better stick to $|x_i|=1$
– Lee
22 hours ago
@Lee and Rodrigo : Both of you are right. Sorry it is my mistake still, precising that $i$ goes from $1$ to $n$ would not hurt. An alternative way to write is simply $xin{-1,1}^n$
– Surb
22 hours ago
1
This is known as a Binary Quadratic Problem and is hard. There are some solvers for it, for instance www-lipn.univ-paris13.fr/BiqCrunch and you can have some success solving a sequence of semidefinite relaxations.
– Michal Adamaszek
20 hours ago
|
show 2 more comments
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
22 hours ago
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
22 hours ago
1
what I wanted to say is that all elements of $x$ are equal to 1 or -1, so I think I will better stick to $|x_i|=1$
– Lee
22 hours ago
@Lee and Rodrigo : Both of you are right. Sorry it is my mistake still, precising that $i$ goes from $1$ to $n$ would not hurt. An alternative way to write is simply $xin{-1,1}^n$
– Surb
22 hours ago
1
This is known as a Binary Quadratic Problem and is hard. There are some solvers for it, for instance www-lipn.univ-paris13.fr/BiqCrunch and you can have some success solving a sequence of semidefinite relaxations.
– Michal Adamaszek
20 hours ago
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
22 hours ago
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
22 hours ago
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
22 hours ago
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
22 hours ago
1
1
what I wanted to say is that all elements of $x$ are equal to 1 or -1, so I think I will better stick to $|x_i|=1$
– Lee
22 hours ago
what I wanted to say is that all elements of $x$ are equal to 1 or -1, so I think I will better stick to $|x_i|=1$
– Lee
22 hours ago
@Lee and Rodrigo : Both of you are right. Sorry it is my mistake still, precising that $i$ goes from $1$ to $n$ would not hurt. An alternative way to write is simply $xin{-1,1}^n$
– Surb
22 hours ago
@Lee and Rodrigo : Both of you are right. Sorry it is my mistake still, precising that $i$ goes from $1$ to $n$ would not hurt. An alternative way to write is simply $xin{-1,1}^n$
– Surb
22 hours ago
1
1
This is known as a Binary Quadratic Problem and is hard. There are some solvers for it, for instance www-lipn.univ-paris13.fr/BiqCrunch and you can have some success solving a sequence of semidefinite relaxations.
– Michal Adamaszek
20 hours ago
This is known as a Binary Quadratic Problem and is hard. There are some solvers for it, for instance www-lipn.univ-paris13.fr/BiqCrunch and you can have some success solving a sequence of semidefinite relaxations.
– Michal Adamaszek
20 hours ago
|
show 2 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2999348%2fwhat-is-the-maximum-value-of-xtax-subject-to-x-in-pm1-n%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
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
22 hours ago
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
22 hours ago
1
what I wanted to say is that all elements of $x$ are equal to 1 or -1, so I think I will better stick to $|x_i|=1$
– Lee
22 hours ago
@Lee and Rodrigo : Both of you are right. Sorry it is my mistake still, precising that $i$ goes from $1$ to $n$ would not hurt. An alternative way to write is simply $xin{-1,1}^n$
– Surb
22 hours ago
1
This is known as a Binary Quadratic Problem and is hard. There are some solvers for it, for instance www-lipn.univ-paris13.fr/BiqCrunch and you can have some success solving a sequence of semidefinite relaxations.
– Michal Adamaszek
20 hours ago