12 ms·

Intro to Multicriteria Optimization

69 points by Zephyr314 10y ago

Zephyr314 10y ago
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 https://sigopt.com/research
- sevensor 10y ago
  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?)
  - mccourt 10y ago
    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.
    - sevensor 10y ago
      I agree that expressing the problem can become more confusing in the presence of more levels of preemption, however it can be an effective way to organize large numbers of criteria. If your customers are mainly working with biobjective problems, I can see why you wouldn't be too interested in adding more levels!
      - mccourt 10y ago
        And I can absolutely agree that, as more criteria arise, the mechanism for linear scalarization probably becomes more fragile (subject to inconsistent behavior from the coefficients). As a result, something less sensitive but more robust, such as the tiered ordering, is probably preferable. But yeah, we just have not seen the demand yet. What actually seems to be most common is that people who have ~10 metrics spend some time thinking about it, and then realize that they mostly only cared about 1-2 so long as the rest did not cause problems/failures. That was part of the reason I wrote about the epsilon-constraint idea. We do this in one sense within our company, but it's actually not within the context of a numerical multicriteria optimization problem. We are always trying to optimize around our customer's needs, which is in some ways a multicriteria problem involving balancing: 1) the "best" parameterization of a model subject to some (usually cross-validation) metric, 2) the "cost" (number of samples) required to optimize the model quality, 3) the "robustness" of (degree to which small parameter changes impact) the resulting solution, 4) the "parallel speed" (number of simultaneous suggestions) of the optimization process. We consult with enterprise customers to understand their needs and expectations regarding these criteria to produce a sort of hierarchical ordering (as you've suggested) which helps inform our optimization procedure (maybe a customer doesn't care as much about speed but definitely cares about robustness). Obviously, it's a relatively restricted problem, and we're not considering it in a rigorous mathematical framework (just how best to serve our customers). Because these factors have no real numerical relationship, the only mechanism we can use to balance the concerns is a relative ordering, which is then manage internally. We spoke about this design at the ICML AutoML workshop this year (A Strategy for Ranking ... at https://sites.google.com/site/automl2016/accepted-papers https://sites.google.com/site/automl2016/accepted-papers)
- chaoxu 10y ago
  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.
  - Zephyr314 10y ago
    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 https://sigopt.com/careers
    - wolfgke 10y ago
      > [We] are able to solve this mixed type problem much more efficiently than techniques like gradient decent. Naive gradient descent is probably the simplest strategy that one can imagine. How do your algorithms compare to Newton methods for minimizing the primal-dual gap (interior point methods)?
      - Zephyr314 10y ago
        We compare to some standard convex optimization techniques implemented in scipy here [1]. We have comparisons to some other Bayesian methods here [2]. I'm happy to answer any questions! [1]: https://github.com/sigopt/sigopt-examples/blob/master/ipython-notebook-example/SigOpt_Introduction.ipynb https://github.com/sigopt/sigopt-examples/blob/master/ipytho... [2]: http://arxiv.org/abs/1603.09441 http://arxiv.org/abs/1603.09441
  - pizza 10y ago
    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?
mccourt 10y ago
I wrote this post and am also happy to comment. Hopefully we'll be following this up soon with a post on treating robustness and cost simultaneously in a multicriteria setting. Also, special thanks again to Devon Sigler at the University of Colorado Denver for his help editing this post.
apathy 10y ago
I guess the novelty here is that constraint based optimization with no guarantees on convexity or biconvexity is a PITA?
- mccourt 10y ago
  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-Answer strategy. For problems with more than one input variable, that will almost certainly not be the case. Really, all I was trying to say there at the end is that converting the multicriteria problem to a constraint based problem has potential benefits over scalarization. Speaking only for myself, I always default to treating multicriteria problems in some sort of norm-scalarized sense: minimize ||g|| for some vector norm. I thought it was valuable to remind myself, and maybe others, that there are other ways to naturally rephrase multicriteria problems as scalar optimization problems. I'm definitely not saying anything about how easy it is to solve, as in general these constrained problems are going to be harder than the non-constrained linear (or norm) scalarization.
  - LolWolf 10y ago
    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/gopfkl07.pdf http://www2.math.uni-wuppertal.de/~klamroth/publications/gop...
    - mccourt 10y ago
      That's very helpful. Thanks a lot!
  - apathy 10y ago
    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 sites per time point) are Bayesian. That's about the most irreducible constrained optimization problem I can think of in this setting.
bumbledraven 10y ago
> 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?
- crustygirl 10y ago
  this implies you're giving weight to the first element then the second. let's say you were optimizing something to be pretty A, delicious B, soft C. you tune the system and evaluate the prettiness, deliciousness and softness. you tuned it several times and got three products (A, B, C) of (1,2,3), (2,1,3), (3,2,1) - concrete values are correct evaluations. how exactly do you choose the best one, is prettiness more important? pareto efficiency come to mind - also discussed in the article. [1] [1] : https://en.wikipedia.org/wiki/Pareto_efficiency https://en.wikipedia.org/wiki/Pareto_efficiency
- mccourt 10y ago
  You are absolutely correct that some sort of lexicographic ordering could exist: https://en.wikipedia.org/wiki/Lexicographical_order#Finite_subsets 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.wikipedia.org/wiki/Multi-objective_optimization#A_priori_methods https://en.wikipedia.org/wiki/Multi-objective_optimization#A.... On that note, lemme throw a shout out to the wonderful person who took the time to write that Wikipedia article - it is outstanding. Given that, such an ordering may not be appropriate in all circumstances. Sorting objective vectors from the function suggested in this post would first sort by "time to destination" and then break ties in "time to destination" with "cost of trip". That would mean that (1, 1000) < (1.0000001, 2), but I think most people would be willing to arrive 0.0000001 hours later to save 998 dollars. The flexibility in interpreting the vector objective and making tradeoffs is why the standard lexicographic ordering is not always appropriate. Does that help?
oli5679 10y ago
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.org/doc/scipy/reference/tutorial/optimize.html http://docs.scipy.org/doc/scipy/reference/tutorial/optimize....
- ogrisel 10y ago
  scipy.optimize can only do single-criterion optimization (scalar-valued objective function instead of vector-valued objective functions).
  - radarsat1 10y ago
    > 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.
    - ogrisel 10y ago
      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_posteriori_methods https://en.wikipedia.org/wiki/Multi-objective_optimization#A...
  - oli5679 10y ago
    True, you need to assign weights to a vector of outputs as discussed in this article. After that, scipy.optimize is easy to use though.
- 10y ago
orasis 10y ago
Here is a much simpler approach that works for many problems: minimize the distance to a desired multi-variate state. https://medium.com/@justchap/using-the-pythagorean-theorem-to-model-complicated-goals-in-machine-learning-b85f04b34ad4#.9tajh1t0l https://medium.com/@justchap/using-the-pythagorean-theorem-t...
- mccourt 10y ago
  That strategy can be viable; it's discussed in the Wikipedia article: https://en.wikipedia.org/wiki/Multi-objective_optimization#No-preference_methods https://en.wikipedia.org/wiki/Multi-objective_optimization#N... As is suggested there, though, implementing this no-preference strategy requires some clean rescaling of the component functions in order to yield equal significance for all of them. If you have such a rescaling, that's outstanding; however, as I suggested in the section of the article dealing with the impact of the choice of currency, rescaling a problem may be a difficult proposition. This is especially true for problems that aren't as simple as the toy problem I've proposed here.

69 points by Zephyr314 10y ago

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 https://sigopt.com/research

sevensor 10y ago
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?)
- mccourt 10y ago
  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.
  - sevensor 10y ago
    I agree that expressing the problem can become more confusing in the presence of more levels of preemption, however it can be an effective way to organize large numbers of criteria. If your customers are mainly working with biobjective problems, I can see why you wouldn't be too interested in adding more levels!
    - mccourt 10y ago
      And I can absolutely agree that, as more criteria arise, the mechanism for linear scalarization probably becomes more fragile (subject to inconsistent behavior from the coefficients). As a result, something less sensitive but more robust, such as the tiered ordering, is probably preferable. But yeah, we just have not seen the demand yet. What actually seems to be most common is that people who have ~10 metrics spend some time thinking about it, and then realize that they mostly only cared about 1-2 so long as the rest did not cause problems/failures. That was part of the reason I wrote about the epsilon-constraint idea. We do this in one sense within our company, but it's actually not within the context of a numerical multicriteria optimization problem. We are always trying to optimize around our customer's needs, which is in some ways a multicriteria problem involving balancing: 1) the "best" parameterization of a model subject to some (usually cross-validation) metric, 2) the "cost" (number of samples) required to optimize the model quality, 3) the "robustness" of (degree to which small parameter changes impact) the resulting solution, 4) the "parallel speed" (number of simultaneous suggestions) of the optimization process. We consult with enterprise customers to understand their needs and expectations regarding these criteria to produce a sort of hierarchical ordering (as you've suggested) which helps inform our optimization procedure (maybe a customer doesn't care as much about speed but definitely cares about robustness). Obviously, it's a relatively restricted problem, and we're not considering it in a rigorous mathematical framework (just how best to serve our customers). Because these factors have no real numerical relationship, the only mechanism we can use to balance the concerns is a relative ordering, which is then manage internally. We spoke about this design at the ICML AutoML workshop this year (A Strategy for Ranking ... at https://sites.google.com/site/automl2016/accepted-papers https://sites.google.com/site/automl2016/accepted-papers)
chaoxu 10y ago
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.
- Zephyr314 10y ago
  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 https://sigopt.com/careers
  - wolfgke 10y ago
    > [We] are able to solve this mixed type problem much more efficiently than techniques like gradient decent. Naive gradient descent is probably the simplest strategy that one can imagine. How do your algorithms compare to Newton methods for minimizing the primal-dual gap (interior point methods)?
    - Zephyr314 10y ago
      We compare to some standard convex optimization techniques implemented in scipy here [1]. We have comparisons to some other Bayesian methods here [2]. I'm happy to answer any questions! [1]: https://github.com/sigopt/sigopt-examples/blob/master/ipython-notebook-example/SigOpt_Introduction.ipynb https://github.com/sigopt/sigopt-examples/blob/master/ipytho... [2]: http://arxiv.org/abs/1603.09441 http://arxiv.org/abs/1603.09441
- pizza 10y ago
  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?

mccourt 10y ago

I wrote this post and am also happy to comment. Hopefully we'll be following this up soon with a post on treating robustness and cost simultaneously in a multicriteria setting. Also, special thanks again to Devon Sigler at the University of Colorado Denver for his help editing this post.

apathy 10y ago

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

mccourt 10y ago
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-Answer strategy. For problems with more than one input variable, that will almost certainly not be the case. Really, all I was trying to say there at the end is that converting the multicriteria problem to a constraint based problem has potential benefits over scalarization. Speaking only for myself, I always default to treating multicriteria problems in some sort of norm-scalarized sense: minimize ||g|| for some vector norm. I thought it was valuable to remind myself, and maybe others, that there are other ways to naturally rephrase multicriteria problems as scalar optimization problems. I'm definitely not saying anything about how easy it is to solve, as in general these constrained problems are going to be harder than the non-constrained linear (or norm) scalarization.
- LolWolf 10y ago
  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/gopfkl07.pdf http://www2.math.uni-wuppertal.de/~klamroth/publications/gop...
  - mccourt 10y ago
    That's very helpful. Thanks a lot!
- apathy 10y ago
  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 sites per time point) are Bayesian. That's about the most irreducible constrained optimization problem I can think of in this setting.

bumbledraven 10y ago

> 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?

crustygirl 10y ago
this implies you're giving weight to the first element then the second. let's say you were optimizing something to be pretty A, delicious B, soft C. you tune the system and evaluate the prettiness, deliciousness and softness. you tuned it several times and got three products (A, B, C) of (1,2,3), (2,1,3), (3,2,1) - concrete values are correct evaluations. how exactly do you choose the best one, is prettiness more important? pareto efficiency come to mind - also discussed in the article. [1] [1] : https://en.wikipedia.org/wiki/Pareto_efficiency https://en.wikipedia.org/wiki/Pareto_efficiency
mccourt 10y ago
You are absolutely correct that some sort of lexicographic ordering could exist: https://en.wikipedia.org/wiki/Lexicographical_order#Finite_subsets 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.wikipedia.org/wiki/Multi-objective_optimization#A_priori_methods https://en.wikipedia.org/wiki/Multi-objective_optimization#A.... On that note, lemme throw a shout out to the wonderful person who took the time to write that Wikipedia article - it is outstanding. Given that, such an ordering may not be appropriate in all circumstances. Sorting objective vectors from the function suggested in this post would first sort by "time to destination" and then break ties in "time to destination" with "cost of trip". That would mean that (1, 1000) < (1.0000001, 2), but I think most people would be willing to arrive 0.0000001 hours later to save 998 dollars. The flexibility in interpreting the vector objective and making tradeoffs is why the standard lexicographic ordering is not always appropriate. Does that help?

oli5679 10y ago

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.org/doc/scipy/reference/tutorial/optimize.html http://docs.scipy.org/doc/scipy/reference/tutorial/optimize....

ogrisel 10y ago
scipy.optimize can only do single-criterion optimization (scalar-valued objective function instead of vector-valued objective functions).
- radarsat1 10y ago
  > 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.
  - ogrisel 10y ago
    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_posteriori_methods https://en.wikipedia.org/wiki/Multi-objective_optimization#A...
- oli5679 10y ago
  True, you need to assign weights to a vector of outputs as discussed in this article. After that, scipy.optimize is easy to use though.
10y ago

orasis 10y ago

Here is a much simpler approach that works for many problems: minimize the distance to a desired multi-variate state. https://medium.com/@justchap/using-the-pythagorean-theorem-to-model-complicated-goals-in-machine-learning-b85f04b34ad4#.9tajh1t0l https://medium.com/@justchap/using-the-pythagorean-theorem-t...

mccourt 10y ago
That strategy can be viable; it's discussed in the Wikipedia article: https://en.wikipedia.org/wiki/Multi-objective_optimization#No-preference_methods https://en.wikipedia.org/wiki/Multi-objective_optimization#N... As is suggested there, though, implementing this no-preference strategy requires some clean rescaling of the component functions in order to yield equal significance for all of them. If you have such a rescaling, that's outstanding; however, as I suggested in the section of the article dealing with the impact of the choice of currency, rescaling a problem may be a difficult proposition. This is especially true for problems that aren't as simple as the toy problem I've proposed here.