Question: Does anyone know about a book, a paper or an algorithm for the following optimization problem? What are the sufficient conditions for the existence of the joint optimum, and how to find it?:
Specs: Let $f : \mathbb{R}^m \times \mathbb{R}^n \rightarrow \mathbb{R}$ and let $g : \mathbb{R}^m \times \mathbb{R}^n \rightarrow \mathbb{R}$. Both $f$ and $g$ are twice continuously differentiable. Furthermore, they can be written as sums of squared non-linear functions, on the form $f(X, Y) = \sum_{i \in I} \left( \hat{f_i} (X, Y) \right)^2$ and $g(X, Y) = \sum_{j \in J} \left( \hat{g_j} (X, Y) \right)^2$, with $X \in \mathbb{R}^m$ and $Y \in \mathbb{R}^n$.
The problem, stated informally: I would like to minimize $f(X, Y)$ with respect to $X \in \mathbb{R}^m$ while at the same time minimizing $g(X, Y)$ with respect to $Y \in \mathbb{R}^n$. That is, I am looking for a solution $(X^*, Y^*)$ such that $f(X^*, Y^*)$ is locally minimal in $X^*$ and $g(X^*, Y^*)$ is locally minimal in $Y^*$. Preferably, I would like $f(X^*, Y^*)$ to be globally optimal in $X^*$ but I realize that it may be difficult to find a globally optimal point, so therefore a locally optimal point may do.
The problem, stated more formally: For local optimality, I am looking for a point $(X^*, Y^*)$ such that
$(i) \quad \exists \; \gamma > 0$ such that $\forall X \in \mathbb{R}^m: \quad \| X^* - X \|_2 < \gamma \Rightarrow f(X^*, Y^*) \leqslant f(X, Y^*)$
and
$(ii) \quad \exists \; \mu > 0$ such that $\forall Y \in \mathbb{R}^n: \quad \| Y^* - Y \|_2 < \mu \Rightarrow g(X^*, Y^*) \leqslant g(X^*, Y)$
For global optimality, $(i)$ is replaced by:
$(i) \quad \forall X \in \mathbb{R}^m: f(X^*, Y^*) \leqslant f(X, Y^*)$
Conditions for optimality: At an optimal point $(X^*, Y^*)$, I would expect that $\frac{\partial f}{\partial X} (X^*, Y^*) = 0$ and $\frac{\partial g}{\partial Y}(X^*, Y^*) = 0$. For instance, if $f$ and $g$ are quadratic functions, this condition yields a linear system of equations and a an optimal point $(X^*, Y^*)$ is a solution to that linear system.
Motivation, hints: The above problem appears in my research and I am looking for a practical approach for solving it numerically on a computer. I can easily compute first-order derivatives for a $f$ and $g$ and also resort to packages such as ADOL-C for automatic differentiation in case I need higher order derivatives. Also note that both $f$ and $g$ are sums of squared, non-linear functions. This suggests that some Gauss-Newton-inspired approach could be appropriate for solving it. To sum up, can anyone direct me to a specific paper, a book, an algorithm, a program, a webpage or anything that can be helpful for solving the above problem?
Background: The optimization problem appears in a computer-vision algorithm that I am working on. Essentially, $X$ is a vector with with 2D coordinates for points in an image and $Y$ is a vector of corresponding depths at every point. The function $f(X, Y)$ is derived from observations in an image captured from a camera and $g(X, Y)$ represents a physically related energy.
There is no structural distinction between $X$ and $Y$ variables in your question, so the equivalent form would be: given two non-negative functions $f,g:\Omega\to\Bbb R$, where $\Omega$ is e.g. $\Bbb R^{m+n}$, how to find $\omega\in \Omega$ which "minimizes" both $f$ and $g$. Even more, the nature of $\Omega$ does not really matter for the existence of the solution for the multi-objective optimization problem.
The trick is that $(f,g)\in \Bbb R^2$ which does not have a natural linear ordering, so you shall specify which way of optimality are you interested in. There are many of them, and actually the problem is very similar to game theoretical framework. You may start with reading about Pareto optimality. To adress your original questions: unless you are in a very special case, $\omega^* = (X^*,Y^*)$ does not exist even locally.