1

Say I have an optimization problem where I want to maximize $x$ such that $f(x; p)$ is largest. Here, $p$ is a parameter, $x$ is a variable, and $f$ is a function that depends on $x$ and $p$.

However, the issue is that I don't know what $p$ is, I only know that it is somewhere in the set $P = \{p_1, ..., p_n\}$, with all entries being equally likely.

I can then try two things.

  1. I take the average value, or the expected value $E p = \frac{p_1 + ... + p_n}{n}$, and use this to maximize $f(x;p)$ in $x$.
  2. I solve each individual optimization problem for each $p_i$. Then I simply set the optimal $x^*$ to be the average of all the individual solutions to each subproblem.
  3. Perhaps I can try other things too? If so, please let me know in the answers!

My question is now, considering the different ways one can solve this problem, what are the conceptual differences mathematically. When would one use over another? What is the intuition here?

Bernard
  • 175,478
Mail
  • 11
  • I think none of your approach is really suitable. I'd rather value over the maximal output $f(x^,p)$ rather than over $x^$. But that depends what exactly you are looking for. – Severin Schraven Mar 13 '21 at 21:43
  • You can not maximize both. Are you looking for x to maximize f? – Moti Mar 14 '21 at 02:45
  • Taking the average over the inputs p or x does not make any sense to me! How about taking the average over the values $f(x,p)$ while p ranging in the sample space, and $x$ is fixed. – Red shoes Mar 14 '21 at 06:35

1 Answers1

1

Your question really relates to the area of stochastic optimization.

There is no single answer, but it depends on your objective and the sequence of your decision in this decision making problem. Let me explain.

First, one situation is that you need to make the decision $x$ before you really know the true value of $p$ (this seems to be your case). This is called static decision making. However, another situation is that you can observe $p$ first, then make your decision $x$. Then, of course, you will make $x$ to be optimal for the specific $p$ you see. This is called adaptive decision making. In your question, this is a trivial case. But if imagine that you have to make a decision first before knowing $p$, then you can adjust your decision after you see $p$ and you want to minimize the overall cost. Then this becomes an interesting two-stage stochastic program.

Yes, as an example of adaptive decision making, we can formulate a two-stage stochastic program as $\min_{x_1}\{ f_1(x_1) + \mathbb{E}_p[Q(x_1,p)]\}$, where $Q(x_1,p)=\min_{x_2} f_2(x_2, x_1, p)$. Note that $Q(x_1,p)$ is the optimal objective of an optimization problem given $x_1, p$. A practical example: you need to first decide how much to invest $(x_1)$ in say stock market this month, then after you see the performance of the stocks, you can adjust your position $(x_2)$ in month 2, and you want to determine $x_1$ by considering what could happen in month 2, so you write the two-stage stochastic program.

Second, now let's talk about the objective. In your case, you can minimize the average cost as $$\min_x \; \mathbb{E}_p[f(x,p)] \quad (1)$$ where the expectation is taken over the distribution of the random variable $p$. Why do we care about this formulation? Imagine that your decision $x$ is evaluated repeatedly over randomly drawn $p$, then the solution from (1) minimizes the long-term average cost, while the solutions from your choices 1 and 2 do not. So this stochastic program (1) gives you superior solution on average. The benefit is called the value of the stochastic solution.

Other objectives are also possible, for example, if you want to minimize certain risk measure of your solution, such as variance, value-at-risk (VaR), or conditional value at risk (CVaR).

A good reference is John Birge and Francois Louveaux's book Introduction to Stochastic Programming.

max
  • 296
  • Nice explanation! To me, adaptive decision-making is nothing but the usual deterministic approach in optimization. Am I right?

    Can you plz also what do you mean by"adjust your decision "? Is there any mathematical formulation for that?

     – Red shoes Mar 14 '21 at 06:44
  • 1
    I edited my answer with some more explanation of adaptive decision making. – max Mar 14 '21 at 06:59
  • Nice, looks like bilevel programming! – Red shoes Mar 14 '21 at 07:17
  • @Redshoes, yes, a two-stage stochastic program can be viewed as a bilevel program. – max Mar 14 '21 at 07:30