4

TLDR: If George Costanza was supposed to do Robust Optimization, he would instead do Best Case Optimization, which is (sort of) the opposite of Robust Optimization.

Is there a literature or problem nomenclature associated with the concept of optimization with respect to the best case? That is sort of the opposite of Robust Optimization, which is optimizing with respect to the worst case.

Robust optimization optimizes the worst case outcome with respect to some defined universe of possibilities. For instance, the increasingly popular "Wasserstein distributionally robust optimization". It finds the optimum for the worst case within a specified Wasserstein distance.

Optimizing for the best case would find the optimum for the best case, within a specified Wasserstein distance (or possibly otherwise).

Roughly speaking, optimizing for the best case would let the optimizer choose the most favorable among a set of possible constraints, basically an "or"; whereas robust optimization essentially amounts to an "and".

Another analogy would be to Stochastic Programming. But in best optimization, the optimizer gets to choose the most favorable scenario to incorporate as a constraint.

For example, let's say that (at least) one out of n of the matrix constraints, $A_ix = b_i$ is satisfied, but we don't know which one. Best case optimization would solve

$$\text{min (w.r.t. to i,x)}: \text{f}(x), \text{s.t.} A_ix=b_i$$ So mini-min, not mini-max.

Mark L. Stone
  • 13,392
  • 1
  • 31
  • 67
  • 1
    I can suggest a nomenclature: "wishful thinking optimization". – prubin Dec 02 '22 at 19:05
  • @prubin I'm trying to find out if there are existing names/nomenclature for this. It does have real-world application even for people who are not wishful thinkers, just as TSP has application to circuit design, even though there are no salesmen in the circuits. – Mark L. Stone Dec 02 '22 at 19:18
  • It could also be called: optimizer gets to choose its (favorite) constraint. – Mark L. Stone Dec 02 '22 at 19:25
  • I've thought about this question from time to time, but I usually stop thinking about it based on the ideas and principles of decision analysis and risk management. When dealing with uncertainty, people are usually interested in preventing unfavorable outcomes. What you're proposing is the opposite of risk management, which I've not seen any instance in management and industrial engineering literature. – Ehsan Dec 02 '22 at 19:26
  • @Ehsan Yes, this is the opposite of the way O.R. and risk management people are trained to think. – Mark L. Stone Dec 02 '22 at 19:28
  • @MarkL.Stone Perhaps you should look into the concept of "perfect information" in decision analysis and stochastic programming. Best-Case Optimization leads to no structural property in the optimal/feasible solution (e.g., satisfying the constraints of all possible scenarios), which I find it not wise. – Ehsan Dec 02 '22 at 19:34
  • @Eshan Before you label this wise, consider there are various situations in which it might arise. For instance, branch and bound eliminates portions of a search tree based on as assessment that even in the most favorable case, that portion of the tree can't possibly be better than an incumbent. If the best case isn't good enough ... – Mark L. Stone Dec 02 '22 at 19:40
  • In stoch programming when you take expected value or sample average approx, isn't that kind of best case? – Sutanu Majumdar Dec 02 '22 at 20:08
  • Sutanu, No. That is "average" case, which depending on the details of the problem, may or may not be biased. – Mark L. Stone Dec 02 '22 at 20:29
  • 2
    @MarkL.Stone Unfortunately, I cannot follow your example and its relation to the discussion. I suffice to say that without structural property, your example of best-case optimization reduces to solving n separate optimization problems and picking the solution that has the best objective function. Ensuring the feasibility of the solution for all scenarios seems like a must to me. – Ehsan Dec 03 '22 at 04:41
  • @Sutanu Following Mark's comment, this approach is called "risk-neutral" in the literature as you're not interested in controlling deviations from the average. – Ehsan Dec 03 '22 at 04:43
  • @Ehsan You are correct. Can either solve n separate problems, or solve one problem with choice of 1 of n constraints. I've done it both ways, and variations., such as choose m of n constraints. I still want to know if there is a literature or name for this. It doesn't necessarily have anything to do with risk preferences of the "user" or customer of the optimization. – Mark L. Stone Dec 03 '22 at 13:32

0 Answers0