Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Intro to Multicriteria Optimization

blog.sigopt.com

Post reply on HN
Print view View original

41–46 of 46 posts

Re: Intro to Multicriteria Optimization

#41

Post by wolfgke »

mccourt wrote: post #38
wolfgke wrote: post #20

Earlier quoted context omitted.

Doing research in mixed-integer linear optimization (but wrote diploma thesis about some topic in combinatorial optimization): > What are the bread and butter of combinatorial optimization? In other words, the concepts you would first come across, at an undergrad level if possible? - Polyhedral combinatorics (Books: "Alexander Schrijver - Combinatorial Optimization: Polyhedra and Efficiency" (more focus on polyhedral…

I'd also like to throw in some work by a former colleague of mine at Argonne, Sven Leyffer on nonlinear programming: - A compendium he co-edited named (appropriately enough) Mixed Integer Nonlinear Programming - A review paper he co-authored for Acta Numerica: http://www.mcs.anl.gov/papers/P3060-1112.pdf Also, yeah, the "Alexander Schrijver - Theory of Linear and Integer Programming" reference is solid.

The survey article by Sven Leyffer is a good paper, but comes from a completely different direction:

It comes from people from convex optimization trying to additionally apply some integrality conditions (a little bit as second-class citizen). On the other hand classical combinatorial optimization is integrality conditions as first-class citizen. I, coming from (M)ILP, would argue that the MINLP people coming from convex optimization tend to sidestep all the problems that make ILP so hard (and interesting). On the other hand MINLP people would equally vocally argue that the (M)ILP people tend to prefer "academic" problems and don't grasp how many important research questions they miss.

It's up to the reader to decide which side is right. :-)

My personal opinion in this "flamewar" is that if you come from a computer science background (in particular theoretical computer science) you will probably prefer classic MILP culture. On the other hand if you come from engineering you will probably prefer MINLP theory as outlined in Sven Leyffer's survey paper.

Re: Intro to Multicriteria Optimization

#42

Post by mccourt »

wolfgke wrote: post #41
mccourt wrote: post #38

Earlier quoted context omitted.

I'd also like to throw in some work by a former colleague of mine at Argonne, Sven Leyffer on nonlinear programming: - A compendium he co-edited named (appropriately enough) Mixed Integer Nonlinear Programming - A review paper he co-authored for Acta Numerica: http://www.mcs.anl.gov/papers/P3060-1112.pdf Also, yeah, the "Alexander Schrijver - Theory of Linear and Integer Programming" reference is solid.

The survey article by Sven Leyffer is a good paper, but comes from a completely different direction: It comes from people from convex optimization trying to additionally apply some integrality conditions (a little bit as second-class citizen). On the other hand classical combinatorial optimization is integrality conditions as first-class citizen. I, coming from (M)ILP, would argue that the MINLP people coming from co…

Yeah, I think that's probably the split - folks from computer science/discrete math on one side and folks from engineering on the other. I grew up in math, but I was on the numerical analysis side so I definitely ended up on the MINLP side, which is why that's what I generally reference. There is certainly something elegant about ILP problems which gets lost when treating them with the sledgehammer that is gradient-based convex optimization.

Re: Intro to Multicriteria Optimization

#43

Post by wolfgke »

mccourt wrote: post #42
wolfgke wrote: post #41

Earlier quoted context omitted.

The survey article by Sven Leyffer is a good paper, but comes from a completely different direction: It comes from people from convex optimization trying to additionally apply some integrality conditions (a little bit as second-class citizen). On the other hand classical combinatorial optimization is integrality conditions as first-class citizen. I, coming from (M)ILP, would argue that the MINLP people coming from co…

Yeah, I think that's probably the split - folks from computer science/discrete math on one side and folks from engineering on the other. I grew up in math, but I was on the numerical analysis side so I definitely ended up on the MINLP side, which is why that's what I generally reference. There is certainly something elegant about ILP problems which gets lost when treating them with the sledgehammer that is gradient-b…

> There is certainly something elegant about ILP problems which gets lost when treating them with the sledgehammer that is gradient-based convex optimization.

It is funny that you call gradient-based convex optimization a "sledgehammer" since people working in combinatorial optimization (opposed to ILP) tend to denote ILP methods (e.g. cutting plane algorithms, branch & bound, branch & cut, relaxation hierarchies, ...) also as a "sledgehammer". :-D They are just jealous. :-)

Re: Intro to Multicriteria Optimization

#44

Post by oli5679 »

Zephyr314 wrote: post #31
oli5679 wrote: post #23

For anyone looking for a free optimization tool in python, sypy.opimize is easy to use. Eg if I have a complicated function revenue([A,B,C,D]) I can define obj([A,B,C,D]) = -1* revenue([A,B,C,D]) and use: >>>import numpy as np >>>from scipy.optimize import minimize >>>X0 = np.array([1.5, 0.7, 1.2, 100]) >>>options={'xtol': 1e-4, 'disp': True}) >>>X* = minimize(obj, x0, method='nelder-mead', options) http://docs.scipy…

The methods in scipy.optimize are great if your function is serial, cheap, deterministic, and convex. Many ML models and real world problems don't fit into this context though. We have a Jupyter notebook showing how SigOpt compares to several scipy.optimize methods as well as standard methods like grid/random on a simple non-convex problem here [1]. These results only get more striking as the dimensionality increases…

Many of these scipy methods can cope with concave, noisy functions. There's a bit of skill/alchemy with selecting starting values and tolerance parameters. Interesting to see that your approach has superior performance in that case, but in many cases these free tools with no need for an api would be sufficient.

Re: Intro to Multicriteria Optimization

#45

Post by apathy »

mccourt wrote: post #40
apathy wrote: post #33

Earlier quoted context omitted.

That makes sense, at least as long as the vector- or matrix-valued objective behaves somewhat. I guess I've been using this all along (with transformations to enforce proper behavior) for matrix and tensor completion anyways... Hmm. I just didn't implement it terribly elegantly! Now that I think about it, all of the methods I've ever seen for matrix-valued time series fits (i.e. multiple measurements at multiple site…

Do you have a reference for fitting matrix-valued time series with nonlinear criteria? I'm familiar with the standard Box-Jenkins methods but I usually see that done with linear least-squares methods. I'd love to up my game on that front.

I'm buried under manuscripts right now but making a mental note to look up Mike West's notes when I get home.

Re: Intro to Multicriteria Optimization

#46

Post by ogrisel »

radarsat1 wrote: post #28
ogrisel wrote: post #24

Earlier quoted context omitted.

scipy.optimize can only do single-criterion optimization (scalar-valued objective function instead of vector-valued objective functions).

> The tradeoffs between these two criteria can either be managed by some supervisory decision maker (the driver of the car in this example) or by merging the multiple criteria into some single criteria and phrasing the problem as a standard optimization problem. You always have to reduce the problem to a scalar if you want a single answer.

You might want to discover the full Pareto frontier to gain some insights on the structure of the trade-off.

I think the best methods to explore the Pareto frontier are based on the concepts of evolutionary computation like NSGA-II and SPEA-2:

https://en.wikipedia.org/wiki/Multi-objective_optimization#A...

Post reply on HN