3

Ask HN: Literature for Mathematical Optimization?

 3 years ago
source link: https://news.ycombinator.com/item?id=27719928
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Ask HN: Literature for Mathematical Optimization? Ask HN: Literature for Mathematical Optimization? 52 points by samuel2 6 hours ago | hide | past | favorite | 21 comments Hi! Do you know any books on math optimization that are essential for anybody getting into this field? Is there any classical literature for optimization related to ML? Thanks!

My current list includes:

1. Numerical Optimization by Jorge Nocedal Stephen J. Wright

2. Algorithms for Optimization - introduction to optimization with a focus on practical algorithms

3. Algorithms for Decision Making - a broad introduction to algorithms for decision making under uncertainty

[2] https://algorithmsbook.com/optimization/

[3] https://algorithmsbook.com/

So for medium to non-technical people reading this, I took a course in grad school that showed me how to do this in Excel with solver.

It was easily one of the top 3 courses I took and heavily based off of this text book:

https://www.amazon.com/Spreadsheet-Modeling-Decision-Analysi...

Here's an excerpt from a comment I previously made on Hacker News:

I'm a Ph.D. student in operations research (OR). My suggestion would be to first build a strong foundation in linear programming. This will introduce you to the notion of duality, which is heavily emphasized in many mathematical programming courses. Here's a good open-source book on linear programming written by Jon Lee, the current editor of Mathematical Programming A: https://github.com/jon77lee/JLee_LinearOptimizationBook

Then I'd suggest studying more general methods for continuous and convex optimization. The book I see mentioned a lot is Convex Optimization by Boyd and Vandenberghe, although we didn't use this in our coursework. Instead, we used a lot of the material presented here: http://mitmgmtfaculty.mit.edu/rfreund/educationalactivities/

If you read the above (or any other two books on linear programming and convex optimization), you'll probably have a better idea of what you want to study next and how you want to go about it. The next natural step would be to study combinatorial (i.e., integer or mixed-integer) optimization. (Jon Lee has another book on this subject; I've also heard good things about the Schrijver book.)

s.gif
In addition to Boyd and Vandenberghe, I like "Lectures on Modern Convex Optimization" by Ben-Tal and Nemirovski. Particularly the section comparing linear and conic optimization problems.
s.gif
For linear programming I much preferred the Bertsimas/Tsitsiklis (Introduction to Linear Optimization). Not free, but if you look at the first couple Google result you may get nice surprises.
I started from zero, and my approach was to read Nocedal/Wright cover-to-cover, and then the same with "Numerical Linear Algebra" by Trefethen/Bau. Usually it goes the other way, but I found the linear algebra primer in N/W to be good enough to get started.

I also read "Practical Optimization" by Murray/Gill, which is interesting because it has a lot of conversational coverage of e.g. corner cases, stuff that most textbooks won't cover.

That will cover the expected baseline of almost everything you'll encounter in the convex smooth continuous domain. I don't have great answers for moving past that.

For theoretical continuous/nonlinear/convex optimization, your #1 is the bible, together with

"Convex Optimization" by Boyd & Vandenberghe.

However, beware that both are grad textbooks. They can be tough going at times. Unfortunately, I never found undergrad textbooks I liked much, for theory.

If you're interested in discrete optimization too (the other half of math optimization), the classics are:

"Optimization Over Integers" by Bertsimas & Weismantel

"Integer and Combinatorial Optimization" by Nemhauser & Wolsey

s.gif
Not sure what you mean by the bible?
s.gif
Sorry, I meant that those two books seem to be "classics" that are often used as references in graduate courses.
s.gif
You grab a copy of "Convex Optimization" by Boyd & Vandenberghe over here: https://web.stanford.edu/~boyd/cvxbook/

This is more optimal control but I really enjoyed reading through these notes: https://math.berkeley.edu/~evans/control.course.pdf

Nocedal and Wright is good. +1 also to the suggestions for Boyd and Vandenberghe. I really like Boyd's writing in general; he has coauthored some good review articles on proximal algorithms and ADMM.

A couple of other suggestions:

Nesterov's Introductory Lectures on Convex Optimization. This one is pretty tough sledding, but I found the perspectives in the first chapter particularly to be enlightening. It seems like there's a newer Springer book which is probably an expansion on this.

Bertsekas's Nonlinear Programming. Bertsekas has written a lot of books, and there's a fair amount of overlapping going on. This one seemed to be the one that has the most nuts and bolts about the basics of optimization.

EDIT: If you want more understanding of convexity beyond what's presented in these books, Rockafellar's Convex Analysis is helpful.

I recently bought "Introduction to Nonlinear Optimization" by Amir Beck. It's published by the SIAM. It covers the field from beginning to intermediate level and includes examples written in MATLAB. I found the book very readable and illuminating. It's also not overly long nor verbose, which is a plus in my mind. I would recommend it -- I used some of its ideas as fodder to teach the optimization section of my class in Numerical Analysis.

https://epubs.siam.org/doi/book/10.1137/1.9781611973655?mobi...

Without a doubt you should read the following.

It is the clearest, most in depth, introduction from "zero to hero" for optimization. Mostly from a math perspective, useful for many things outside of ML too!

https://www.amazon.com/Foundations-Applied-Mathematics-Appro...

I recommend Bayesian Methods for hackers [1]. It doesn’t go too deep on theory but I feel like it’s well written and has really good coded up examples of theory being applied to problems. It has a relatively narrow scope, but I find myself reaching for methods I learned from the author frequently.

[1] https://github.com/CamDavidsonPilon/Probabilistic-Programmin...

Sébastien Bubeck's book is excellent mathematical introduction to modern convex optimization: https://arxiv.org/abs/1405.4980
I'm planning on taking a course in optimization this fall, the textbook for it is "An introduction to optimization" by Chong and Zak. Dunno if it's any good, but I just ordered it so we'll see.
I'd also add C. T. Kelley's "Iterative Methods for Optimization" for more non convex theory. Nemirovski also has a variety of books and course notes that are available, but I haven't spent as much time with them.

I agree with thxg, there are few undergraduate textbooks that I've liked.

Mathematical Optimization still has many subfields that can be of interest. I guess that non-linear mathematical optimization is most more typical for many machine learning applications. Many pratical applications in scheduling, logistics, planning etc used linear (integer) programming and combinatorial optimization. The following are some points towards that body of literature.

Alexander Schrijver [1] has lecture notes on Combinatorial Optimization on his website [2]. He also has an affordable 1800 page three volume set of books "Combinatorial Optimization - Polyhedra and Efficiency" [3], although I would say it is better suited as reference material because it is quite densely written.

There is also the classic book "Combinatorial Optimization - Algorithms and Complexity" [4] by Papadimitriou (Bill Gates' MSc thesis supervisor) and Steiglitz that is a nice introduction to the topic as well.

"In Pursuit of the Traveling Salesman - Mathematics at the Limits of Computation" by William J. Cook [5] is a more popular science book on the history of the Traveling Salesman Problem, that also explains how linear programming is used in the state of the art solvers, but is of course focuses on a very specific problem. There is also a book that contains all the scientific and mathematical details by Applegate, Bixby, Chvátal and Cook [6] if that is preferred.

In recent years, there is a trend that mathematical optimization researchers work more with ML. In particular Dimitris Bertsimas has done some work on the intersection of those area's in recent years [7] and apparently has a book on the topic as well [8] (but I am not familiar with it).

[1] https://homepages.cwi.nl/~lex/ [2] https://homepages.cwi.nl/~lex/files/dict.pdf [3] https://www.springer.com/us/book/9783540443896 [4] https://www.amazon.com/Combinatorial-Optimization-Algorithms... [5] https://press.princeton.edu/books/paperback/9780691163529/in... [6] http://www.math.uwaterloo.ca/tsp/book/index.html [7] https://dbertsim.mit.edu/papers/ [8] https://www.dynamic-ideas.com/books/machine-learning-under-a...

s.gif Apply early for the YC Winter 2022 batch
Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search:

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK