Mixing
Is the composition of two linear programs a convex problem?
up vote
0
down vote
favorite
This question comes from the empirical observation, for a particular problem
that I am considering, that the solution to a sequence of two linear programms lies a convex set. I could not come up with any theoretical proof that would confirm my empirical observations, so I am asking for some help from the community.
Here is the classical part of the problem:
I want to solve a linear feasibility problem to find a vector $mathbf{x} in mathbb{R}^3$:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{x} in mathbb{R}^3 &&\
st quad & mathbf{A} mathbf{x} leq mathbf{b} \
end{aligned} end{equation}$
with $mathbf{A} in mathbb{R}^{m times 3}$, $mathbf{b} in mathbb{R}^{m}$.
However, $mathbf{x}$ is going to serve as input for another feasibility problem to find a variable $mathbf{y} in mathbb{R}^3$:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{y} in mathbb{R}^3 &&\
st quad & (mathbf{C} mathbf{x}_{times} + mathbf{D}) mathbf{y} leq mathbf{e} \
end{aligned} end{equation}$
with $mathbf{C}$ and $mathbf{D} in mathbb{R}^{k times 3}$, $mathbf{e} in mathbb{R}^{k}$, and $mathbf{x}_{times}$ being the skew-symmetric matrix for the cross product by $mathbf{x}$.
My objective is to find, if it exists, an $mathbf{x}$ such that there exists a feasible $mathbf{y}$. The problem thus becomes:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{x} in mathbb{R}^3 &&\
st quad & mathbf{A} mathbf{x} leq mathbf{b} \
& exists mathbf{y}, (mathbf{C} mathbf{x}_{times} + mathbf{D}) mathbf{y} leq mathbf{e} \
end{aligned} end{equation}$
In the general case, is this a convex problem ? Can it be solved as an LP or other classical convex optimization techniques ?
Thanks a lot for your help
Steve
convex-analysis linear-programming
asked 9 mins ago
Steve T.
284
add a comment |
up vote
0
down vote
favorite
This question comes from the empirical observation, for a particular problem
that I am considering, that the solution to a sequence of two linear programms lies a convex set. I could not come up with any theoretical proof that would confirm my empirical observations, so I am asking for some help from the community.
Here is the classical part of the problem:
I want to solve a linear feasibility problem to find a vector $mathbf{x} in mathbb{R}^3$:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{x} in mathbb{R}^3 &&\
st quad & mathbf{A} mathbf{x} leq mathbf{b} \
end{aligned} end{equation}$
with $mathbf{A} in mathbb{R}^{m times 3}$, $mathbf{b} in mathbb{R}^{m}$.
However, $mathbf{x}$ is going to serve as input for another feasibility problem to find a variable $mathbf{y} in mathbb{R}^3$:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{y} in mathbb{R}^3 &&\
st quad & (mathbf{C} mathbf{x}_{times} + mathbf{D}) mathbf{y} leq mathbf{e} \
end{aligned} end{equation}$
with $mathbf{C}$ and $mathbf{D} in mathbb{R}^{k times 3}$, $mathbf{e} in mathbb{R}^{k}$, and $mathbf{x}_{times}$ being the skew-symmetric matrix for the cross product by $mathbf{x}$.
My objective is to find, if it exists, an $mathbf{x}$ such that there exists a feasible $mathbf{y}$. The problem thus becomes:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{x} in mathbb{R}^3 &&\
st quad & mathbf{A} mathbf{x} leq mathbf{b} \
& exists mathbf{y}, (mathbf{C} mathbf{x}_{times} + mathbf{D}) mathbf{y} leq mathbf{e} \
end{aligned} end{equation}$
In the general case, is this a convex problem ? Can it be solved as an LP or other classical convex optimization techniques ?
Thanks a lot for your help
Steve
convex-analysis linear-programming
asked 9 mins ago
Steve T.
284
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
This question comes from the empirical observation, for a particular problem
that I am considering, that the solution to a sequence of two linear programms lies a convex set. I could not come up with any theoretical proof that would confirm my empirical observations, so I am asking for some help from the community.
Here is the classical part of the problem:
I want to solve a linear feasibility problem to find a vector $mathbf{x} in mathbb{R}^3$:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{x} in mathbb{R}^3 &&\
st quad & mathbf{A} mathbf{x} leq mathbf{b} \
end{aligned} end{equation}$
with $mathbf{A} in mathbb{R}^{m times 3}$, $mathbf{b} in mathbb{R}^{m}$.
However, $mathbf{x}$ is going to serve as input for another feasibility problem to find a variable $mathbf{y} in mathbb{R}^3$:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{y} in mathbb{R}^3 &&\
st quad & (mathbf{C} mathbf{x}_{times} + mathbf{D}) mathbf{y} leq mathbf{e} \
end{aligned} end{equation}$
with $mathbf{C}$ and $mathbf{D} in mathbb{R}^{k times 3}$, $mathbf{e} in mathbb{R}^{k}$, and $mathbf{x}_{times}$ being the skew-symmetric matrix for the cross product by $mathbf{x}$.
My objective is to find, if it exists, an $mathbf{x}$ such that there exists a feasible $mathbf{y}$. The problem thus becomes:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{x} in mathbb{R}^3 &&\
st quad & mathbf{A} mathbf{x} leq mathbf{b} \
& exists mathbf{y}, (mathbf{C} mathbf{x}_{times} + mathbf{D}) mathbf{y} leq mathbf{e} \
end{aligned} end{equation}$
In the general case, is this a convex problem ? Can it be solved as an LP or other classical convex optimization techniques ?
Thanks a lot for your help
Steve
convex-analysis linear-programming
asked 9 mins ago
Steve T.
284
This question comes from the empirical observation, for a particular problem
that I am considering, that the solution to a sequence of two linear programms lies a convex set. I could not come up with any theoretical proof that would confirm my empirical observations, so I am asking for some help from the community.
Here is the classical part of the problem:
I want to solve a linear feasibility problem to find a vector $mathbf{x} in mathbb{R}^3$:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{x} in mathbb{R}^3 &&\
st quad & mathbf{A} mathbf{x} leq mathbf{b} \
end{aligned} end{equation}$
with $mathbf{A} in mathbb{R}^{m times 3}$, $mathbf{b} in mathbb{R}^{m}$.
However, $mathbf{x}$ is going to serve as input for another feasibility problem to find a variable $mathbf{y} in mathbb{R}^3$:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{y} in mathbb{R}^3 &&\
st quad & (mathbf{C} mathbf{x}_{times} + mathbf{D}) mathbf{y} leq mathbf{e} \
end{aligned} end{equation}$
with $mathbf{C}$ and $mathbf{D} in mathbb{R}^{k times 3}$, $mathbf{e} in mathbb{R}^{k}$, and $mathbf{x}_{times}$ being the skew-symmetric matrix for the cross product by $mathbf{x}$.
My objective is to find, if it exists, an $mathbf{x}$ such that there exists a feasible $mathbf{y}$. The problem thus becomes:
$begin{equation} begin{aligned}
mathbf{find} quad & mathbf{x} in mathbb{R}^3 &&\
st quad & mathbf{A} mathbf{x} leq mathbf{b} \
& exists mathbf{y}, (mathbf{C} mathbf{x}_{times} + mathbf{D}) mathbf{y} leq mathbf{e} \
end{aligned} end{equation}$
In the general case, is this a convex problem ? Can it be solved as an LP or other classical convex optimization techniques ?
Thanks a lot for your help
Steve
convex-analysis linear-programming
convex-analysis linear-programming
asked 9 mins ago
Steve T.
284
asked 9 mins ago
Steve T.
284
edited 4 mins ago
asked 9 mins ago
Steve T.
284
asked 9 mins ago
Steve T.
284
asked 9 mins ago
Steve T.
284
284
add a comment |
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004694%2fis-the-composition-of-two-linear-programs-a-convex-problem%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
