Intro to Multicriteria Optimization • Hacker News Board

Re: Intro to Multicriteria Optimization

#11

Post by sevensor » Wed, Aug 17, 2016, 1:53 AM UTC

mccourt wrote: post #8

bumbledraven wrote: post #5

> The reason this is a more complicated situation is that an ordering of vectors in RkRk does not exist... how would one order the vectors u = (1,2,3), v = (2,1,3), w = (3,2,1)? It seems straightforward to order those vectors by first comparing the first component, then the second, then the third. The result is u,v,w. It's as if you wanted to sort a multi-column report in Excel. What am I missing?

You are absolutely correct that some sort of lexicographic ordering could exist: https://en.wikipedia.org/wiki/Lexicographical_order#Finite_s... If such an ordering did exist, then we could certainly apply that ordering to sort results from the vector objective function so as to find the "answer" to the multicriteria problem. The Wikipedia article on multiobjective optimization discusses this strategy: https://en.wik…

> most people would be willing to arrive 0.0000001 hours later to save 998 dollars

Unfortunately, if you don't know how your model behaves, you can't tell when you're setting γ whether you're actually going to get a solution that's way past the point of diminishing returns. You may not even be able to tell after the fact. This is one of the reasons for doing sensitivity analysis on γ. (Your ε-constraint scalarization helps with this problem.)

Re: Intro to Multicriteria Optimization

#12

Post by mccourt » Wed, Aug 17, 2016, 1:58 AM UTC

sevensor wrote: post #10

Zephyr314 wrote: post #2

I'm one of the co-founders of SigOpt (YC W15) and am happy to answer any questions about SigOpt or the methods we apply. More info on our research (and examples) can be found at https://sigopt.com/research

Does your platform support more than one level of preemption / lexicographic goal setting? (Like the ε-constraint scalarization technique, but with a second, third, nth set of goals between the first set and the objective?)

Our customers who are working with multicriteria problems have, thus far, had primarily two criteria, thus we have been helping them manage their two criteria problems into a scalar setting. As such, we do not, at this moment, permit the layers of ordering strategy you suggest through our API. To do so internally would introduce a complicated bifurcation between problems phrased with real-valued observations (as is our standard workflow), and the less informative comparative structure you're suggesting, whereby we would only be able to make statements about the relative order of points and not the magnitude by which they differ. If we were willing to impose a magnitude, doing so would revert the problem back into the weighted combination scalarization setting (or at least some norm-scalarization setting, if not the linear setting discussed in the post). I do not foresee us implementing such a tiered preemptive ordering any time soon.

Re: Intro to Multicriteria Optimization

#13

Post by mccourt » Wed, Aug 17, 2016, 2:05 AM UTC

sevensor wrote: post #11

mccourt wrote: post #8

Earlier quoted context omitted.

You are absolutely correct that some sort of lexicographic ordering could exist: https://en.wikipedia.org/wiki/Lexicographical_order#Finite_s... If such an ordering did exist, then we could certainly apply that ordering to sort results from the vector objective function so as to find the "answer" to the multicriteria problem. The Wikipedia article on multiobjective optimization discusses this strategy: https://en.wik…

> most people would be willing to arrive 0.0000001 hours later to save 998 dollars Unfortunately, if you don't know how your model behaves, you can't tell when you're setting γ whether you're actually going to get a solution that's way past the point of diminishing returns. You may not even be able to tell after the fact. This is one of the reasons for doing sensitivity analysis on γ. (Your ε-constraint scalarization…

You make a perfectly accurate point that, in practice, it is unlikely one would be able to make such a prediction without significant info about the model. The above comment was meant in more of a post hoc "we've executed our multicriteria optimization, approximated our Pareto frontier, now let's make a decision" sense, not within a specific scalarization context. Indeed sensitivity analysis on the gamma parameter is very important; I tried to hint at that by showing that the interplay of the choice of currency and the gamma on the optimal value is nontrivial (though predictable since this is just a toy problem).

Do you happen to have any references talking about such sensitivity analysis on scalarization parameters? I would love to add them to my reading list. Thanks.

Re: Intro to Multicriteria Optimization

#14

Post by pmalynin » Wed, Aug 17, 2016, 2:42 AM UTC

bumbledraven wrote: post #5

> The reason this is a more complicated situation is that an ordering of vectors in RkRk does not exist... how would one order the vectors u = (1,2,3), v = (2,1,3), w = (3,2,1)? It seems straightforward to order those vectors by first comparing the first component, then the second, then the third. The result is u,v,w. It's as if you wanted to sort a multi-column report in Excel. What am I missing?

Consider a simpler case of two dimensional real vectors. Lets consider the vector space of R^2, since all finite dimensional vector spaces of same dimensionality are isomorphic, R^2 is isomorphic to the complex numbers.

How would you order the complex numbers?

Re: Intro to Multicriteria Optimization

#15

Post by mccourt » Wed, Aug 17, 2016, 2:48 AM UTC

pmalynin wrote: post #14

bumbledraven wrote: post #5

> The reason this is a more complicated situation is that an ordering of vectors in RkRk does not exist... how would one order the vectors u = (1,2,3), v = (2,1,3), w = (3,2,1)? It seems straightforward to order those vectors by first comparing the first component, then the second, then the third. The result is u,v,w. It's as if you wanted to sort a multi-column report in Excel. What am I missing?

Consider a simpler case of two dimensional real vectors. Lets consider the vector space of R^2, since all finite dimensional vector spaces of same dimensionality are isomorphic, R^2 is isomorphic to the complex numbers. How would you order the complex numbers?

Good call. That's a simpler example than where I was going.

Re: Intro to Multicriteria Optimization

#16

Post by chaoxu » Wed, Aug 17, 2016, 3:04 AM UTC

Zephyr314 wrote: post #2

I'm one of the co-founders of SigOpt (YC W15) and am happy to answer any questions about SigOpt or the methods we apply. More info on our research (and examples) can be found at https://sigopt.com/research

I do research in combinatorial optimization. Does your company solve any problems with a combinatorial flavor? (say, things can be optimized using combinatorial algorithms instead of going for gradient descent.

Re: Intro to Multicriteria Optimization

#17

Post by Zephyr314 » Wed, Aug 17, 2016, 4:38 AM UTC

chaoxu wrote: post #16

Zephyr314 wrote: post #2

I'm one of the co-founders of SigOpt (YC W15) and am happy to answer any questions about SigOpt or the methods we apply. More info on our research (and examples) can be found at https://sigopt.com/research

I do research in combinatorial optimization. Does your company solve any problems with a combinatorial flavor? (say, things can be optimized using combinatorial algorithms instead of going for gradient descent.

We don't (yet), but we are growing rapidly and always looking for ways to help our customers solve optimization problems. Fwiw, we do support categorical parameters (as well as continuous and integer) and our ensemble of Bayesian optimization techniques are able to solve this mixed type problem much more efficiently than techniques like gradient decent. Although the way we handle the purely combinatorial (only category) problem isn't as flushed out as our mixed type problems. We are looking to grow the team (and our offerings) if you're interested though [1].

[1]: https://sigopt.com/careers

Re: Intro to Multicriteria Optimization

#18

Post by LolWolf » Wed, Aug 17, 2016, 4:54 AM UTC

mccourt wrote: post #6

apathy wrote: post #4

I guess the novelty here is that constraint based optimization with no guarantees on convexity or biconvexity is a PITA?

First off, I am very hesitant to say anything about biconvex problems - I only see them in passing and they are definitely not in my wheelhouse. If anyone out there is an expert, or even just has a solid (basic) reference on biconvex problems, please feel free to drop some knowledge on me. For this particular problem, which has only one input variable, yes the answer can be resolved with a good-old fashioned Plug-In-…

The usual reference is this[1] paper which outlines most well-known results on biconvexity and optimiality thereof.

[1] http://www2.math.uni-wuppertal.de/~klamroth/publications/gop...

Re: Intro to Multicriteria Optimization

#19

Post by pizza » Wed, Aug 17, 2016, 4:58 AM UTC

chaoxu wrote: post #16

Zephyr314 wrote: post #2

I'm one of the co-founders of SigOpt (YC W15) and am happy to answer any questions about SigOpt or the methods we apply. More info on our research (and examples) can be found at https://sigopt.com/research

I do research in combinatorial optimization. Does your company solve any problems with a combinatorial flavor? (say, things can be optimized using combinatorial algorithms instead of going for gradient descent.

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?

Re: Intro to Multicriteria Optimization

#20

Post by wolfgke » Wed, Aug 17, 2016, 9:31 AM UTC

pizza wrote: post #19

chaoxu wrote: post #16

Earlier quoted context omitted.

I do research in combinatorial optimization. Does your company solve any problems with a combinatorial flavor? (say, things can be optimized using combinatorial algorithms instead of going for gradient descent.

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?

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 combinatorics; IMHO the best book, but not the most approachable), "Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms" (more focus on algorithms; easier to read). This of course includes (mixed-)integer linear programming ((M)ILP).

- Of course learning about (M)ILPs means understanding linear programming (LP). Here I personally prefer "Alexander Schrijver - Theory of Linear and Integer Programming" (this books also covers ILP aspects, but not MILPs).

- Other books for learning about ILPs are "Dimitris Bertsimas, Robert Weismantel - Optimization Over Integers" (main focus is ILP, nevertheless a good book) and "Conforti, Cornuejols, Zambelli - Integer Programming". There are no really good books about MILPs that I know of, but these two books at least will cover some aspects of it.

- Sometimes semidefinite relaxations will occur (most famous example: Goemans-Williamson Algorithm; less famous, but also important: Lovasz-Schrijver hierarchy, Sherali-Adams hierarchy, Lasserre hierarchy)