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 discrete-optimization non-convex-optimization
edited Nov 17 at 21:12
Rodrigo de Azevedo
12.7k41753
asked Nov 15 at 7:18
Lee
807
|
show 4 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 discrete-optimization non-convex-optimization
edited Nov 17 at 21:12
Rodrigo de Azevedo
12.7k41753
asked Nov 15 at 7:18
Lee
807
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
Nov 15 at 7:39
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
Nov 15 at 7:49
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
Nov 15 at 7:54
1
Related: math.stackexchange.com/q/2126489/339790
– Rodrigo de Azevedo
Nov 15 at 7:59
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
Nov 15 at 10:00
|
show 4 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 discrete-optimization non-convex-optimization
edited Nov 17 at 21:12
Rodrigo de Azevedo
12.7k41753
asked Nov 15 at 7:18
Lee
807
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 discrete-optimization non-convex-optimization
optimization positive-definite discrete-optimization non-convex-optimization
edited Nov 17 at 21:12
Rodrigo de Azevedo
12.7k41753
asked Nov 15 at 7:18
Lee
807
edited Nov 17 at 21:12
Rodrigo de Azevedo
12.7k41753
asked Nov 15 at 7:18
Lee
807
edited Nov 17 at 21:12
Rodrigo de Azevedo
12.7k41753
edited Nov 17 at 21:12
Rodrigo de Azevedo
12.7k41753
edited Nov 17 at 21:12
Rodrigo de Azevedo
12.7k41753
12.7k41753
asked Nov 15 at 7:18
Lee
807
asked Nov 15 at 7:18
Lee
807
asked Nov 15 at 7:18
Lee
807
807
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
Nov 15 at 7:39
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
Nov 15 at 7:49
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
Nov 15 at 7:54
1
Related: math.stackexchange.com/q/2126489/339790
– Rodrigo de Azevedo
Nov 15 at 7:59
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
Nov 15 at 10:00
|
show 4 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
Nov 15 at 7:39
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
Nov 15 at 7:49
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
Nov 15 at 7:54
1
Related: math.stackexchange.com/q/2126489/339790
– Rodrigo de Azevedo
Nov 15 at 7:59
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
Nov 15 at 10:00
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
Nov 15 at 7:39
in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong
– Lee
Nov 15 at 7:39
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
Nov 15 at 7:49
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
Nov 15 at 7:49
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
Nov 15 at 7:54
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
Nov 15 at 7:54
1
1
Related: math.stackexchange.com/q/2126489/339790
– Rodrigo de Azevedo
Nov 15 at 7:59
Related: math.stackexchange.com/q/2126489/339790
– Rodrigo de Azevedo
Nov 15 at 7:59
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
Nov 15 at 10:00
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
Nov 15 at 10:00
|
show 4 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
Nov 15 at 7:39
so $|x_i|$=1 and $||x||_{infty}=1$ are similar?
– Lee
Nov 15 at 7:49
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
Nov 15 at 7:54
1
Related: math.stackexchange.com/q/2126489/339790
– Rodrigo de Azevedo
Nov 15 at 7:59
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
Nov 15 at 10:00