degeneracy and duality in linear programming
up vote
1
down vote
favorite
I'm currently learning about linear programming and optimization methods and the most recent subject was duality
I'm trying to understand the connection between degeneracy of the primal and properties of the dual.
We were told in lecture (at least for the case of standard linear programming) that if the primal is non-degenerate then the dual has a unique optimal solution. But this statement wasn't prove and I wasn't able to prove it by myself
I would appreciate some assistant
just to be clear the standard form requires to $min(c^t cdot x)$ subject to $Acdot x = b$ and $xgeq 0$
optimization linear-programming duality-theorems
asked Nov 14 at 18:43
user615821
62
add a comment |
up vote
1
down vote
favorite
I'm currently learning about linear programming and optimization methods and the most recent subject was duality
I'm trying to understand the connection between degeneracy of the primal and properties of the dual.
We were told in lecture (at least for the case of standard linear programming) that if the primal is non-degenerate then the dual has a unique optimal solution. But this statement wasn't prove and I wasn't able to prove it by myself
I would appreciate some assistant
just to be clear the standard form requires to $min(c^t cdot x)$ subject to $Acdot x = b$ and $xgeq 0$
optimization linear-programming duality-theorems
asked Nov 14 at 18:43
user615821
62
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I'm currently learning about linear programming and optimization methods and the most recent subject was duality
I'm trying to understand the connection between degeneracy of the primal and properties of the dual.
We were told in lecture (at least for the case of standard linear programming) that if the primal is non-degenerate then the dual has a unique optimal solution. But this statement wasn't prove and I wasn't able to prove it by myself
I would appreciate some assistant
just to be clear the standard form requires to $min(c^t cdot x)$ subject to $Acdot x = b$ and $xgeq 0$
optimization linear-programming duality-theorems
asked Nov 14 at 18:43
user615821
62
I'm currently learning about linear programming and optimization methods and the most recent subject was duality
I'm trying to understand the connection between degeneracy of the primal and properties of the dual.
We were told in lecture (at least for the case of standard linear programming) that if the primal is non-degenerate then the dual has a unique optimal solution. But this statement wasn't prove and I wasn't able to prove it by myself
I would appreciate some assistant
just to be clear the standard form requires to $min(c^t cdot x)$ subject to $Acdot x = b$ and $xgeq 0$
optimization linear-programming duality-theorems
optimization linear-programming duality-theorems
asked Nov 14 at 18:43
user615821
62
asked Nov 14 at 18:43
user615821
62
edited Nov 14 at 18:57
asked Nov 14 at 18:43
user615821
62
asked Nov 14 at 18:43
user615821
62
asked Nov 14 at 18:43
user615821
62
62
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Let $x in mathbb{R}^n$ and $A in mathbb{R}^{m times n}$ where the rows of $A$ are linearly independent.
Suppose it is nondegenerate, then there are $m$ components of $x$ which are positive. Denote the set of such indices to be $B$.
By complementary slackness condition,
$$forall i in B, x_i(p^TA_i-c_i)=0$$
$$forall i in B, p^TA_i=c_i$$
Notice that the columns of $A_i$ where $i in B$ are linearly independent, hence we can solve for $p$ uniquely.
answered Nov 15 at 2:58
Siong Thye Goh
94.3k1462114
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Let $x in mathbb{R}^n$ and $A in mathbb{R}^{m times n}$ where the rows of $A$ are linearly independent.
Suppose it is nondegenerate, then there are $m$ components of $x$ which are positive. Denote the set of such indices to be $B$.
By complementary slackness condition,
$$forall i in B, x_i(p^TA_i-c_i)=0$$
$$forall i in B, p^TA_i=c_i$$
Notice that the columns of $A_i$ where $i in B$ are linearly independent, hence we can solve for $p$ uniquely.
answered Nov 15 at 2:58
Siong Thye Goh
94.3k1462114
add a comment |
up vote
0
down vote
Let $x in mathbb{R}^n$ and $A in mathbb{R}^{m times n}$ where the rows of $A$ are linearly independent.
Suppose it is nondegenerate, then there are $m$ components of $x$ which are positive. Denote the set of such indices to be $B$.
By complementary slackness condition,
$$forall i in B, x_i(p^TA_i-c_i)=0$$
$$forall i in B, p^TA_i=c_i$$
Notice that the columns of $A_i$ where $i in B$ are linearly independent, hence we can solve for $p$ uniquely.
answered Nov 15 at 2:58
Siong Thye Goh
94.3k1462114
add a comment |
up vote
0
down vote
up vote
0
down vote
Let $x in mathbb{R}^n$ and $A in mathbb{R}^{m times n}$ where the rows of $A$ are linearly independent.
Suppose it is nondegenerate, then there are $m$ components of $x$ which are positive. Denote the set of such indices to be $B$.
By complementary slackness condition,
$$forall i in B, x_i(p^TA_i-c_i)=0$$
$$forall i in B, p^TA_i=c_i$$
Notice that the columns of $A_i$ where $i in B$ are linearly independent, hence we can solve for $p$ uniquely.
answered Nov 15 at 2:58
Siong Thye Goh
94.3k1462114
Let $x in mathbb{R}^n$ and $A in mathbb{R}^{m times n}$ where the rows of $A$ are linearly independent.
Suppose it is nondegenerate, then there are $m$ components of $x$ which are positive. Denote the set of such indices to be $B$.
By complementary slackness condition,
$$forall i in B, x_i(p^TA_i-c_i)=0$$
$$forall i in B, p^TA_i=c_i$$
Notice that the columns of $A_i$ where $i in B$ are linearly independent, hence we can solve for $p$ uniquely.
answered Nov 15 at 2:58
Siong Thye Goh
94.3k1462114
answered Nov 15 at 2:58
Siong Thye Goh
94.3k1462114
answered Nov 15 at 2:58
Siong Thye Goh
94.3k1462114
answered Nov 15 at 2:58
Siong Thye Goh
94.3k1462114
94.3k1462114
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%2f2998662%2fdegeneracy-and-duality-in-linear-programming%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
