Hi,

What would be some good books to read on duality theory - both in combinatorial and convex optimization?

Thanks

asked 29 May '12, 18:16

Sid's gravatar image

Sid
5312917
accept rate: 18%


For convex optimization, you could do worse than starting with Luenberger's Linear and Nonlinear Programming. I don't know whether that would be sufficient coverage for your needs, but the book is written well and accessible with a reasonable mathematical background.

link

answered 30 May '12, 18:29

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thanks for the response. I'm very familiar with the basic duality covered in books like Papadimitriou's Comb Opt. and Bertsekas' Nonlinear Programming so if you know about some more advanced books, that would be great!

(30 May '12, 22:19) Sid

Start with Bertsimas's "intro to linear programming" and then read Bazaraa and Shetty's nonlinear optimization book. What you need is a deep understanding of three concepts 1) Separating hyperplanes 2) Farkas Lemma 3) Duality

Think about how separating hyperplanes can describe duality. If you get that everything else is easy.

If those books are easy for you then you can go on to read Schrijver's book "Theory of Linear and Integer Programming" but it is very hard for the beginners.

link

answered 30 May '12, 22:29

Igor%20Pangal's gravatar image

Igor Pangal
147210
accept rate: 0%

I just read a few sections of Bazaraa's book on NLP. It is easy to read and very insightful: I was able to understand what I was looking for at a glance.

(31 May '12, 12:58) Thiago Serra
1

I recommend Bazarra et al.'s linear programming book. It's the book that I always use for duality and LP.

(31 May '12, 15:26) lamclay

It is a little bit classical but one of the best references on duality theory is a paper by Geoffrion: "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development," SIAM Review, Vol. 13, No. 1, Jan., 1971. It may be a little bit hard to understand but it is worth to spend the time.

A more recent reference is from "Nonlinear Optimization" book by Ruszczynski. Chapter 4. Good luck!

link

answered 05 Jun '12, 11:58

Burcu%20Keskin's gravatar image

Burcu Keskin
211
accept rate: 0%

1

@Burcu: Welcome to OR-X!

(05 Jun '12, 18:09) Paul Rubin ♦♦

I've just stumbled across the following: Convexity, Duality and Lagrange Multipliers, developed by Bertsekas. Judging from your reply to Paul Rubin's answer, it might be what you're looking for. From the Preface:

These topics include Lagrange multiplier theory, Lagrangian and conjugate duality, and nondifferentiable optimization. The notes contain substantial portions that are adapted from my textbook “Nonlinear Programming: 2nd Edition,” Athena Scientific, 1999. However, the notes are more advanced, more mathematical, and more research-oriented.

Hope it helps!

link

answered 01 Jul '12, 11:58

yeesian's gravatar image

yeesian
846210
accept rate: 3%

edited 01 Jul '12, 12:03

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×29
×17

Asked: 29 May '12, 18:16

Seen: 3,293 times

Last updated: 01 Jul '12, 12:03

OR-Exchange! Your site for questions, answers, and announcements about operations research.