Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

An optimization task

  1. Jul 22, 2012 #1
    I have an optimization problem and I am looking for a method rather than a solution here. I'll state it in a general form.

    Let there be two functions: [itex]f_1(x_1,\cdots, x_n,y_1,\cdots, y_n )[/itex] and [itex]f_2(x_1,\cdots x_n,y_1,\cdots, y_n )[/itex].

    Maximize [itex]f_1[/itex] with regards to variables [itex]x_1,\cdots, x_n[/itex] with [itex]y_1,\cdots, y_n[/itex] fixed at the values that maximizes [itex]f_2[/itex].

    Maximize [itex]f_2[/itex] with regards to variables [itex]y_1,\cdots, y_n[/itex] with [itex]x_1,\cdots, x_n[/itex] fixed at the values that maximizes [itex]f_1[/itex].

    You could regard them as two utility functions in a game theoretical problem where where agent 1 controls [itex]x_1,\cdots, x_n[/itex], and agent 2 controls [itex]y_1,\cdots, y_n[/itex]. Both utility functions depends on the choices of both players.

    Any ideas of how to solve this? Thanks!
     
  2. jcsd
  3. Jul 22, 2012 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Are you familiar with Nash equilibria?
     
  4. Jul 23, 2012 #3
    Of course, its exactly what I want to do, calculate Nash Equilibrium for a case where each of the two agents controls a continuous function of multiple variables. Any idea of how these kinds of problems are solved?
     
  5. Jul 23, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    The only way I know is to assign a probability vector of choices to each player. Express the outcome (for player 1, say) as function of this, and apply calculus to max wrt player 1's vector and min wrt player 2's. A lot of work, generally.
    But in your case, the choices are continuous variables, right? So that makes it a calculus of variations problem, I guess. In practice, I would write a program to hunt.
     
  6. Jul 25, 2012 #5

    Stephen Tashi

    User Avatar
    Science Advisor

    You limited your audience to those who already know about "Nash equilibrium" because you didn't state an optimization problem. You stated two different problems and did not explain any relation between them.
     
  7. Jul 26, 2012 #6
    I don't know if I agree. The problem is an optimization task stated in the first post. How could later confirming that it is (or equivalent to) a search for Nash equilibrium (just terminology) be a disadvantage?

    I guess that it is possible in principle to regard both functions as function of both x's and y's and take the partial derivatives of the first wrt x's and the second wtr of y's, ending up with n nonlinear equations of n variables. Solving and then looking for maximums (nummerically).
     
  8. Jul 26, 2012 #7

    Stephen Tashi

    User Avatar
    Science Advisor

    Without the specifics of how agents in a game might act, the optimization task stated in the first post can only be interpreted as two unrelated optimization problems.

    The first problem stated would be solved by the steps:

    1. Maximize [itex] f_2 [/itex] with respect to all its variables
    2. Set the [itex] y [/itex] variables in [itex] f_1 [/itex] equal to the [itex] y [/itex] values of the answer in to step 1. and maximize [itex] f_1 [/itex] with respect to the [itex] x [/itex] variables.

    If that isn't what you meant then you need to explain the meaning of the phrase
    .

    The second optimization task you state is equivalent to the first. It just uses different notation.

    I agree that looking at the system of equations defined by setting the partial derivatives of the varying variables equal to zero might be the thing to do. You didn't say whether [itex] f_1 [/itex] and [itex] f_2 [/itex] are differentiable functions.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: An optimization task
  1. Hard task with primes (Replies: 7)

  2. One Task (Replies: 4)

  3. Dynamic Optimization (Replies: 1)

Loading...