Why study duality in optimization?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Is the formulation of dual problem easier than the primal problem to solve, so that duality provides convenience for solving the optimization problem?
Or, does the dual formulation provide a useful theoretical instrument to prove theorems or show properties of optimization problems?
I am not clear about the motivation to study the duality in optimization. Some examples can be very helpful! Thanks!
optimization duality-theorems
asked Aug 9 at 16:17
Leonardo
161
add a comment |Â
up vote
1
down vote
favorite
Is the formulation of dual problem easier than the primal problem to solve, so that duality provides convenience for solving the optimization problem?
Or, does the dual formulation provide a useful theoretical instrument to prove theorems or show properties of optimization problems?
I am not clear about the motivation to study the duality in optimization. Some examples can be very helpful! Thanks!
optimization duality-theorems
asked Aug 9 at 16:17
Leonardo
161
1
It's interesting to note that Nesterov in his book Introductory Lectures on Convex Optimization did not even discuss the dual problem. In the preface he says, "Any concept or fact included in the book is absolutely necessary for the analysis of at least one optimization scheme. Surprisingly enough, none of the material presented requires any facts from duality theory. Thus, this topic is completely omitted. This does not mean, of course, that the author neglect this fundamental concept. However, we hope that for the first treatment of the subject such a compromise is acceptable."
– littleO
Aug 9 at 19:44
Many convex optimization algorithms can be interpreted as iterative methods for solving the KKT conditions. When we solve the KKT conditions, we are simultaneously solving the primal and the dual problem. For example, I think primal-dual interior point methods can be motivated by the idea of solving the KKT conditions using Newton's method. (This simple idea does not quite work because of the inequality constraints in the KKT conditions, so we modify the idea slightly to make it workable and discover interior point methods.)
– littleO
Aug 9 at 19:47
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Is the formulation of dual problem easier than the primal problem to solve, so that duality provides convenience for solving the optimization problem?
Or, does the dual formulation provide a useful theoretical instrument to prove theorems or show properties of optimization problems?
I am not clear about the motivation to study the duality in optimization. Some examples can be very helpful! Thanks!
optimization duality-theorems
asked Aug 9 at 16:17
Leonardo
161
Is the formulation of dual problem easier than the primal problem to solve, so that duality provides convenience for solving the optimization problem?
Or, does the dual formulation provide a useful theoretical instrument to prove theorems or show properties of optimization problems?
I am not clear about the motivation to study the duality in optimization. Some examples can be very helpful! Thanks!
optimization duality-theorems
asked Aug 9 at 16:17
Leonardo
161
asked Aug 9 at 16:17
Leonardo
161
asked Aug 9 at 16:17
Leonardo
161
asked Aug 9 at 16:17
Leonardo
161
161
1
It's interesting to note that Nesterov in his book Introductory Lectures on Convex Optimization did not even discuss the dual problem. In the preface he says, "Any concept or fact included in the book is absolutely necessary for the analysis of at least one optimization scheme. Surprisingly enough, none of the material presented requires any facts from duality theory. Thus, this topic is completely omitted. This does not mean, of course, that the author neglect this fundamental concept. However, we hope that for the first treatment of the subject such a compromise is acceptable."
– littleO
Aug 9 at 19:44
Many convex optimization algorithms can be interpreted as iterative methods for solving the KKT conditions. When we solve the KKT conditions, we are simultaneously solving the primal and the dual problem. For example, I think primal-dual interior point methods can be motivated by the idea of solving the KKT conditions using Newton's method. (This simple idea does not quite work because of the inequality constraints in the KKT conditions, so we modify the idea slightly to make it workable and discover interior point methods.)
– littleO
Aug 9 at 19:47
add a comment |Â
1
It's interesting to note that Nesterov in his book Introductory Lectures on Convex Optimization did not even discuss the dual problem. In the preface he says, "Any concept or fact included in the book is absolutely necessary for the analysis of at least one optimization scheme. Surprisingly enough, none of the material presented requires any facts from duality theory. Thus, this topic is completely omitted. This does not mean, of course, that the author neglect this fundamental concept. However, we hope that for the first treatment of the subject such a compromise is acceptable."
– littleO
Aug 9 at 19:44
Many convex optimization algorithms can be interpreted as iterative methods for solving the KKT conditions. When we solve the KKT conditions, we are simultaneously solving the primal and the dual problem. For example, I think primal-dual interior point methods can be motivated by the idea of solving the KKT conditions using Newton's method. (This simple idea does not quite work because of the inequality constraints in the KKT conditions, so we modify the idea slightly to make it workable and discover interior point methods.)
– littleO
Aug 9 at 19:47
1
1
It's interesting to note that Nesterov in his book Introductory Lectures on Convex Optimization did not even discuss the dual problem. In the preface he says, "Any concept or fact included in the book is absolutely necessary for the analysis of at least one optimization scheme. Surprisingly enough, none of the material presented requires any facts from duality theory. Thus, this topic is completely omitted. This does not mean, of course, that the author neglect this fundamental concept. However, we hope that for the first treatment of the subject such a compromise is acceptable."
– littleO
Aug 9 at 19:44
It's interesting to note that Nesterov in his book Introductory Lectures on Convex Optimization did not even discuss the dual problem. In the preface he says, "Any concept or fact included in the book is absolutely necessary for the analysis of at least one optimization scheme. Surprisingly enough, none of the material presented requires any facts from duality theory. Thus, this topic is completely omitted. This does not mean, of course, that the author neglect this fundamental concept. However, we hope that for the first treatment of the subject such a compromise is acceptable."
– littleO
Aug 9 at 19:44
Many convex optimization algorithms can be interpreted as iterative methods for solving the KKT conditions. When we solve the KKT conditions, we are simultaneously solving the primal and the dual problem. For example, I think primal-dual interior point methods can be motivated by the idea of solving the KKT conditions using Newton's method. (This simple idea does not quite work because of the inequality constraints in the KKT conditions, so we modify the idea slightly to make it workable and discover interior point methods.)
– littleO
Aug 9 at 19:47
Many convex optimization algorithms can be interpreted as iterative methods for solving the KKT conditions. When we solve the KKT conditions, we are simultaneously solving the primal and the dual problem. For example, I think primal-dual interior point methods can be motivated by the idea of solving the KKT conditions using Newton's method. (This simple idea does not quite work because of the inequality constraints in the KKT conditions, so we modify the idea slightly to make it workable and discover interior point methods.)
– littleO
Aug 9 at 19:47
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
One major reason is that the dual problem helps you to derive lower bounds (in the case of minimization) on the achievable objective. This can be exploited when developing solvers.
answered Aug 9 at 19:35
Johan Löfberg
4,6921811
add a comment |Â
up vote
0
down vote
Duality makes the problem easier most of the times it is being used for example an optimization problem with 3 variables and 10 constraints has a duality with 3 constraints and 10 variables. This is because the complexity of an optimization problem mostly depends on the number of constraints not variables.
answered Aug 9 at 16:41
Mostafa Ayaz
9,1033630
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
One major reason is that the dual problem helps you to derive lower bounds (in the case of minimization) on the achievable objective. This can be exploited when developing solvers.
answered Aug 9 at 19:35
Johan Löfberg
4,6921811
add a comment |Â
up vote
1
down vote
One major reason is that the dual problem helps you to derive lower bounds (in the case of minimization) on the achievable objective. This can be exploited when developing solvers.
answered Aug 9 at 19:35
Johan Löfberg
4,6921811
add a comment |Â
up vote
1
down vote
up vote
1
down vote
One major reason is that the dual problem helps you to derive lower bounds (in the case of minimization) on the achievable objective. This can be exploited when developing solvers.
answered Aug 9 at 19:35
Johan Löfberg
4,6921811
One major reason is that the dual problem helps you to derive lower bounds (in the case of minimization) on the achievable objective. This can be exploited when developing solvers.
answered Aug 9 at 19:35
Johan Löfberg
4,6921811
edited Aug 9 at 19:47
answered Aug 9 at 19:35
Johan Löfberg
4,6921811
answered Aug 9 at 19:35
Johan Löfberg
4,6921811
answered Aug 9 at 19:35
Johan Löfberg
4,6921811
4,6921811
add a comment |Â
add a comment |Â
up vote
0
down vote
Duality makes the problem easier most of the times it is being used for example an optimization problem with 3 variables and 10 constraints has a duality with 3 constraints and 10 variables. This is because the complexity of an optimization problem mostly depends on the number of constraints not variables.
answered Aug 9 at 16:41
Mostafa Ayaz
9,1033630
add a comment |Â
up vote
0
down vote
Duality makes the problem easier most of the times it is being used for example an optimization problem with 3 variables and 10 constraints has a duality with 3 constraints and 10 variables. This is because the complexity of an optimization problem mostly depends on the number of constraints not variables.
answered Aug 9 at 16:41
Mostafa Ayaz
9,1033630
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Duality makes the problem easier most of the times it is being used for example an optimization problem with 3 variables and 10 constraints has a duality with 3 constraints and 10 variables. This is because the complexity of an optimization problem mostly depends on the number of constraints not variables.
answered Aug 9 at 16:41
Mostafa Ayaz
9,1033630
Duality makes the problem easier most of the times it is being used for example an optimization problem with 3 variables and 10 constraints has a duality with 3 constraints and 10 variables. This is because the complexity of an optimization problem mostly depends on the number of constraints not variables.
answered Aug 9 at 16:41
Mostafa Ayaz
9,1033630
answered Aug 9 at 16:41
Mostafa Ayaz
9,1033630
answered Aug 9 at 16:41
Mostafa Ayaz
9,1033630
answered Aug 9 at 16:41
Mostafa Ayaz
9,1033630
9,1033630
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2877393%2fwhy-study-duality-in-optimization%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
1
It's interesting to note that Nesterov in his book Introductory Lectures on Convex Optimization did not even discuss the dual problem. In the preface he says, "Any concept or fact included in the book is absolutely necessary for the analysis of at least one optimization scheme. Surprisingly enough, none of the material presented requires any facts from duality theory. Thus, this topic is completely omitted. This does not mean, of course, that the author neglect this fundamental concept. However, we hope that for the first treatment of the subject such a compromise is acceptable."
– littleO
Aug 9 at 19:44
Many convex optimization algorithms can be interpreted as iterative methods for solving the KKT conditions. When we solve the KKT conditions, we are simultaneously solving the primal and the dual problem. For example, I think primal-dual interior point methods can be motivated by the idea of solving the KKT conditions using Newton's method. (This simple idea does not quite work because of the inequality constraints in the KKT conditions, so we modify the idea slightly to make it workable and discover interior point methods.)
– littleO
Aug 9 at 19:47