Solving an Optimization Problem with Two Functions

[Or Entity?]

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: $f_1(x_1,\cdots, x_n,y_1,\cdots, y_n )$ and $f_2(x_1,\cdots x_n,y_1,\cdots, y_n )$.

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

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

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

Any ideas of how to solve this? Thanks!

 

[haruspex]

Are you familiar with Nash equilibria?

 

[Or Entity?]

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?

 

[haruspex]

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?

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.

 

[Stephen Tashi]

I have an optimization problem

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.

 

[Or Entity?]

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.

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).

 

[Stephen Tashi]

I don't know if I agree. The problem is an optimization task stated in the first post..

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 $f_2$ with respect to all its variables
2. Set the $y$ variables in $f_1$ equal to the $y$ values of the answer into step 1. and maximize $f_1$ with respect to the $x$ variables.

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

with $y_1,\dots,y_n$ fixed at the values that maximizes $f_2$

.

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 $f_1$ and $f_2$ are differentiable functions.