Checking inequality
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let $pi$ be a given permutation of the integers $1,ldots,n$ and let
$$mathcalX=xinmathbbR_+^n mid x_pi(1)geqcdotsgeq x_pi(n),mathbb1^top xgeq alpha,$$
for some $alpha>0$. Let $ainmathbbR$, $binmathbbR^n$ and $QinmathbbR^ntimes n$ symmetric. Is there a way to check if
beginalign*
a+b^topx+x^topQx<0,quad forall xinmathcalX,
endalign*
in general? For example, if $Q$ is negative semidefinite, then we can use convex quadratic programming to solve the problem. However, can we do something in the general case? Perhaps the eigendecomposition of $Q$ and the structure of $mathcalX$ might be used.
matrices analysis optimization quadratic-programming
asked Aug 20 at 9:17
BasicUser
15414
add a comment |Â
up vote
2
down vote
favorite
Let $pi$ be a given permutation of the integers $1,ldots,n$ and let
$$mathcalX=xinmathbbR_+^n mid x_pi(1)geqcdotsgeq x_pi(n),mathbb1^top xgeq alpha,$$
for some $alpha>0$. Let $ainmathbbR$, $binmathbbR^n$ and $QinmathbbR^ntimes n$ symmetric. Is there a way to check if
beginalign*
a+b^topx+x^topQx<0,quad forall xinmathcalX,
endalign*
in general? For example, if $Q$ is negative semidefinite, then we can use convex quadratic programming to solve the problem. However, can we do something in the general case? Perhaps the eigendecomposition of $Q$ and the structure of $mathcalX$ might be used.
matrices analysis optimization quadratic-programming
asked Aug 20 at 9:17
BasicUser
15414
My instinct says that there might not be an efficient way to establish the inequality, since what you want is essentially to maximize an non-concave quadratic over a polyhedron, which is in general NP-hard. However, your polyhedron has a specific structure, so I'm not sure if there is a special instance of it that is known to be NP-hard.
– madnessweasley
Aug 20 at 20:28
A necessary condition for the inequality to hold (that can be checked in polynomial time) is that any eigenvector corresponding to a positive eigenvalue of $Q$ must not belong to the recession cone of $mathcalX$ (this doesn't answer your question)
– madnessweasley
Aug 21 at 2:44
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $pi$ be a given permutation of the integers $1,ldots,n$ and let
$$mathcalX=xinmathbbR_+^n mid x_pi(1)geqcdotsgeq x_pi(n),mathbb1^top xgeq alpha,$$
for some $alpha>0$. Let $ainmathbbR$, $binmathbbR^n$ and $QinmathbbR^ntimes n$ symmetric. Is there a way to check if
beginalign*
a+b^topx+x^topQx<0,quad forall xinmathcalX,
endalign*
in general? For example, if $Q$ is negative semidefinite, then we can use convex quadratic programming to solve the problem. However, can we do something in the general case? Perhaps the eigendecomposition of $Q$ and the structure of $mathcalX$ might be used.
matrices analysis optimization quadratic-programming
asked Aug 20 at 9:17
BasicUser
15414
Let $pi$ be a given permutation of the integers $1,ldots,n$ and let
$$mathcalX=xinmathbbR_+^n mid x_pi(1)geqcdotsgeq x_pi(n),mathbb1^top xgeq alpha,$$
for some $alpha>0$. Let $ainmathbbR$, $binmathbbR^n$ and $QinmathbbR^ntimes n$ symmetric. Is there a way to check if
beginalign*
a+b^topx+x^topQx<0,quad forall xinmathcalX,
endalign*
in general? For example, if $Q$ is negative semidefinite, then we can use convex quadratic programming to solve the problem. However, can we do something in the general case? Perhaps the eigendecomposition of $Q$ and the structure of $mathcalX$ might be used.
matrices analysis optimization quadratic-programming
asked Aug 20 at 9:17
BasicUser
15414
asked Aug 20 at 9:17
BasicUser
15414
asked Aug 20 at 9:17
BasicUser
15414
asked Aug 20 at 9:17
BasicUser
15414
15414
My instinct says that there might not be an efficient way to establish the inequality, since what you want is essentially to maximize an non-concave quadratic over a polyhedron, which is in general NP-hard. However, your polyhedron has a specific structure, so I'm not sure if there is a special instance of it that is known to be NP-hard.
– madnessweasley
Aug 20 at 20:28
A necessary condition for the inequality to hold (that can be checked in polynomial time) is that any eigenvector corresponding to a positive eigenvalue of $Q$ must not belong to the recession cone of $mathcalX$ (this doesn't answer your question)
– madnessweasley
Aug 21 at 2:44
add a comment |Â
My instinct says that there might not be an efficient way to establish the inequality, since what you want is essentially to maximize an non-concave quadratic over a polyhedron, which is in general NP-hard. However, your polyhedron has a specific structure, so I'm not sure if there is a special instance of it that is known to be NP-hard.
– madnessweasley
Aug 20 at 20:28
A necessary condition for the inequality to hold (that can be checked in polynomial time) is that any eigenvector corresponding to a positive eigenvalue of $Q$ must not belong to the recession cone of $mathcalX$ (this doesn't answer your question)
– madnessweasley
Aug 21 at 2:44
My instinct says that there might not be an efficient way to establish the inequality, since what you want is essentially to maximize an non-concave quadratic over a polyhedron, which is in general NP-hard. However, your polyhedron has a specific structure, so I'm not sure if there is a special instance of it that is known to be NP-hard.
– madnessweasley
Aug 20 at 20:28
My instinct says that there might not be an efficient way to establish the inequality, since what you want is essentially to maximize an non-concave quadratic over a polyhedron, which is in general NP-hard. However, your polyhedron has a specific structure, so I'm not sure if there is a special instance of it that is known to be NP-hard.
– madnessweasley
Aug 20 at 20:28
A necessary condition for the inequality to hold (that can be checked in polynomial time) is that any eigenvector corresponding to a positive eigenvalue of $Q$ must not belong to the recession cone of $mathcalX$ (this doesn't answer your question)
– madnessweasley
Aug 21 at 2:44
A necessary condition for the inequality to hold (that can be checked in polynomial time) is that any eigenvector corresponding to a positive eigenvalue of $Q$ must not belong to the recession cone of $mathcalX$ (this doesn't answer your question)
– madnessweasley
Aug 21 at 2:44
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2888565%2fchecking-inequality%23new-answer', 'question_page');
);
Post as a guest
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
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
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
My instinct says that there might not be an efficient way to establish the inequality, since what you want is essentially to maximize an non-concave quadratic over a polyhedron, which is in general NP-hard. However, your polyhedron has a specific structure, so I'm not sure if there is a special instance of it that is known to be NP-hard.
– madnessweasley
Aug 20 at 20:28
A necessary condition for the inequality to hold (that can be checked in polynomial time) is that any eigenvector corresponding to a positive eigenvalue of $Q$ must not belong to the recession cone of $mathcalX$ (this doesn't answer your question)
– madnessweasley
Aug 21 at 2:44