2
1

My understanding is that robust optimization finds the optimal solution for the worst case scenario. I am working on a problem for which I need to find an average-case optimal solution. In other words, say (p) is a parameter where (a<p<b) ((a) and (b) are constants), find (X) such that for all (p) in this range (C(X,p)) holds and (sum_{p=a}^b f(X,p)) is minimized (replace sum with integral since (p) is continuous). If we had a closed form for this sum, it would be a traditional non-linear programming.

Here's the motivation: we want to come up with the best design but we don't have the parameters accurately, so we want to say that our solution is optimal assuming the parameter is somewhere in that range (each (p) in that range is equally likely). This is different from worst-case analysis because I am concerned about maximizing the average and not the worst case! – Sina

asked 26 Jan '12, 23:15

sina's gravatar image

sina
10126
accept rate: 0%

edited 20 Feb '12, 11:40

fbahr's gravatar image

fbahr ♦
4.6k716

I don't think it's well defined when you say that X satisfies C(X,p'). Does it satisfy the constraint with probability 1 (for all possible vales of p' in [a',b'])? Is it enough to satisfy the constraint with some probability alpha < 1, or do you mean something else entirely?

(27 Jan '12, 00:16) Luis de la T...

@Luis: I think you're mixing robust optimization with stochastic programming. In robust optimization, all constraints should be held for all possible realizations of uncertain parameters. Therefore, if @sina really wants to find a robust solution, constraint C(X,p') should be held with probability 1 (this is more of a stochastic programming technical term than a robust optimization one).

I must note that in robust optimization (at least interval robust optimization), we have no probability as it is assumed that there is not enough historical data to estimate such probability.

(27 Jan '12, 01:18) Ehsan ♦

Right, but the question seems to say that p is known to be U[a,b] and p' is U[a',b']. Maybe a better question should be whether this is the case, or if all we can assume is interval uncertainty of p and p'.

It's also not clear to me what is meant by being robust to the average case, but I'm curious to know if some good definition of this exists.

(27 Jan '12, 01:28) Luis de la T...

I agree that the problem definition is not complete. For example, it is not clear what is the objective function of this model. In addition, what would be the benefit of modeling/solving such model as it seems that a nominal model (a model in which all uncertain parameters obtain their mean interval values, i.e. the deterministic model) would do the same.

(27 Jan '12, 01:59) Ehsan ♦

Thanks a lot @Luis and @Ehsan: you guys are right. I need to clarify my problem statement. Let's get rid of (p') and say that we only have (p). So the average-case problem that I am trying to solve is this really: when (a<p<b), find (X) such that for all (p) in this range (C(X,p)) holds and (sum_{p=a}^b f(X,p)) is minimized (replace sum with integral since (p) is continuous). If we had a closed form for this sum, it would be a simple traditional programming.

(27 Jan '12, 10:09) sina

Also, here's the motivation: we want to come up with the best design but we don't have parameters accurately, so we want to say that our solution is optimal assuming the parameter is somewhere in that range. This is different from worst-case analysis because I am concerned about maximizing the average and not the worst case!

(27 Jan '12, 10:09) sina

@sina, can you edit the body of the question with these changes?

(27 Jan '12, 10:51) Luis de la T...

@sina: If you could define an acceptable threshold for the objective function and assume that your uncertain parameters follow the uniform PDF, perhaps you could write your model as a chance-constrained model in stochastic programming.

(28 Jan '12, 07:55) Ehsan ♦
showing 5 of 8 show 3 more comments

I understand your "robust optimization finds the optimal solution for the worst case scenario" as: classical roubst optimization is too conservative as it hedges against all scenarios and thus against all possible disruptions. Right. There are at least two conceptual alternatives:

(1) gamma robustness and (2) recoverable robustness.

The first restricts the worst case to some "smaller" number of disruptions, the second allows for some "repair" of the solution, once the scenario becomes known.

link

answered 27 Jan '12, 09:22

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

Thanks @Marco. These two problems are definitely less conservative than robust optimization, but they're still not an average-case optimization. Please see my clarifying comment.

(27 Jan '12, 10:10) sina
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×58
×16

Asked: 26 Jan '12, 23:15

Seen: 1,530 times

Last updated: 20 Feb '12, 11:41

OR-Exchange! Your site for questions, answers, and announcements about operations research.