Mixing
Finding the Dual of an LP, where variables are not well isolated.
up vote
0
down vote
favorite
Could someone guide me through how I could go about finding the dual of the following LP. Let $A subset Bbb R^{m x n}$, and $x = (x_1, ..., x_m)$.
$$text{max } z
\
text{st } z le x^TA_{.j} , forall j in {1, ldots, m}
\
x_1 + ldots + x_m = 1
\
x ge vec{0}
$$
, where $A_{.j}$ represents the j'th column of A.
My confusion is coming from the fact that in this case, $A$ is a constant matrix, but all the $x_i$'s are variables; as is z.
So I can't see how I can apply the standard primal-dual conversion.
Thanks!
optimization linear-programming duality-theorems
asked 2 days ago
Bojack Horseman
1116
add a comment |
up vote
0
down vote
favorite
Could someone guide me through how I could go about finding the dual of the following LP. Let $A subset Bbb R^{m x n}$, and $x = (x_1, ..., x_m)$.
$$text{max } z
\
text{st } z le x^TA_{.j} , forall j in {1, ldots, m}
\
x_1 + ldots + x_m = 1
\
x ge vec{0}
$$
, where $A_{.j}$ represents the j'th column of A.
My confusion is coming from the fact that in this case, $A$ is a constant matrix, but all the $x_i$'s are variables; as is z.
So I can't see how I can apply the standard primal-dual conversion.
Thanks!
optimization linear-programming duality-theorems
asked 2 days ago
Bojack Horseman
1116
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Could someone guide me through how I could go about finding the dual of the following LP. Let $A subset Bbb R^{m x n}$, and $x = (x_1, ..., x_m)$.
$$text{max } z
\
text{st } z le x^TA_{.j} , forall j in {1, ldots, m}
\
x_1 + ldots + x_m = 1
\
x ge vec{0}
$$
, where $A_{.j}$ represents the j'th column of A.
My confusion is coming from the fact that in this case, $A$ is a constant matrix, but all the $x_i$'s are variables; as is z.
So I can't see how I can apply the standard primal-dual conversion.
Thanks!
optimization linear-programming duality-theorems
asked 2 days ago
Bojack Horseman
1116
Could someone guide me through how I could go about finding the dual of the following LP. Let $A subset Bbb R^{m x n}$, and $x = (x_1, ..., x_m)$.
$$text{max } z
\
text{st } z le x^TA_{.j} , forall j in {1, ldots, m}
\
x_1 + ldots + x_m = 1
\
x ge vec{0}
$$
, where $A_{.j}$ represents the j'th column of A.
My confusion is coming from the fact that in this case, $A$ is a constant matrix, but all the $x_i$'s are variables; as is z.
So I can't see how I can apply the standard primal-dual conversion.
Thanks!
optimization linear-programming duality-theorems
optimization linear-programming duality-theorems
asked 2 days ago
Bojack Horseman
1116
asked 2 days ago
Bojack Horseman
1116
asked 2 days ago
Bojack Horseman
1116
asked 2 days ago
Bojack Horseman
1116
asked 2 days ago
Bojack Horseman
1116
1116
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
You could define $x'=begin{pmatrix}x \ zend{pmatrix}$, then the problem is:
$$begin{align}
max quad & begin{pmatrix}0 \ 0 \ vdots \ 0 \ 1end{pmatrix}^T x' \
text{s.t.} quad & begin{pmatrix} A^T & -e \ e^T & 0 \ -e^T & 0end{pmatrix}x' leq begin{pmatrix} 0 \ 0 \ vdots \ 0 \ 1 \ -1end{pmatrix} \
& x' geq 0.
end{align}$$
Deriving the dual is now simple.
answered 2 days ago
LinAlg
7,6141520
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
You could define $x'=begin{pmatrix}x \ zend{pmatrix}$, then the problem is:
$$begin{align}
max quad & begin{pmatrix}0 \ 0 \ vdots \ 0 \ 1end{pmatrix}^T x' \
text{s.t.} quad & begin{pmatrix} A^T & -e \ e^T & 0 \ -e^T & 0end{pmatrix}x' leq begin{pmatrix} 0 \ 0 \ vdots \ 0 \ 1 \ -1end{pmatrix} \
& x' geq 0.
end{align}$$
Deriving the dual is now simple.
answered 2 days ago
LinAlg
7,6141520
add a comment |
up vote
1
down vote
accepted
You could define $x'=begin{pmatrix}x \ zend{pmatrix}$, then the problem is:
$$begin{align}
max quad & begin{pmatrix}0 \ 0 \ vdots \ 0 \ 1end{pmatrix}^T x' \
text{s.t.} quad & begin{pmatrix} A^T & -e \ e^T & 0 \ -e^T & 0end{pmatrix}x' leq begin{pmatrix} 0 \ 0 \ vdots \ 0 \ 1 \ -1end{pmatrix} \
& x' geq 0.
end{align}$$
Deriving the dual is now simple.
answered 2 days ago
LinAlg
7,6141520
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
You could define $x'=begin{pmatrix}x \ zend{pmatrix}$, then the problem is:
$$begin{align}
max quad & begin{pmatrix}0 \ 0 \ vdots \ 0 \ 1end{pmatrix}^T x' \
text{s.t.} quad & begin{pmatrix} A^T & -e \ e^T & 0 \ -e^T & 0end{pmatrix}x' leq begin{pmatrix} 0 \ 0 \ vdots \ 0 \ 1 \ -1end{pmatrix} \
& x' geq 0.
end{align}$$
Deriving the dual is now simple.
answered 2 days ago
LinAlg
7,6141520
You could define $x'=begin{pmatrix}x \ zend{pmatrix}$, then the problem is:
$$begin{align}
max quad & begin{pmatrix}0 \ 0 \ vdots \ 0 \ 1end{pmatrix}^T x' \
text{s.t.} quad & begin{pmatrix} A^T & -e \ e^T & 0 \ -e^T & 0end{pmatrix}x' leq begin{pmatrix} 0 \ 0 \ vdots \ 0 \ 1 \ -1end{pmatrix} \
& x' geq 0.
end{align}$$
Deriving the dual is now simple.
answered 2 days ago
LinAlg
7,6141520
answered 2 days ago
LinAlg
7,6141520
answered 2 days ago
LinAlg
7,6141520
answered 2 days ago
LinAlg
7,6141520
7,6141520
add a comment |
add a comment |
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%2f3005642%2ffinding-the-dual-of-an-lp-where-variables-are-not-well-isolated%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
