2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your rapid answer. Note, however, that $f$ does not need to be optimal w.r.t. $Y$ and $g$ does not need to be optimal w.r.t. $X$. After you posted your answer, I added to my answer also suggesting that, at locally optimal points $(X^*, Y^*)$ it ought to be true that $\frac{\partial f}{\partial X} (X^*, Y^*) = 0$ and $\frac{\partial g}{\partial Y}(X^*, Y^*) = 0$. This gives rise to a as many (non)linear equations (m+n) as the total dimension (m+n) of $X^*$ and $Y^*$. What makes you think that generally, $\omega^* = (X^*, Y^*)$ does not exist even locally? Cheers $\endgroup$ – Rulle Jun 24 '13 at 11:42
  • $\begingroup$ @Piostruk: what makes me think that way is that $f$ and $g$ may go against each other even though they are positive. Imagine $g = 1/f$, then whenever you increase $f$ by tuning $X$, you decrease $g$. For example, let $f(X,Y) = \mathrm e^{XY}$ and $g(X,Y) = \mathrm e^{-XY}$ - what about their common optima? $\endgroup$ – Ilya Jun 24 '13 at 11:45
  • $\begingroup$ That's a good example. I see that $\frac{\partial f}{\partial X} = e^{XY} > 0$ and $\frac{\partial g}{\partial Y} = -e^{XY} < 0$ so this problem does not have any optima. However, for some other choices of $f$ and $g$, there exists at least an optimum, such as for the quadratic functions $f(X, Y) = X^2 - 2XY + X$ and $g(X, Y) = 2XY + Y^2 - Y$. In case at least one such optimum exists, it would be desirable with an algorithm that can locate it, even for more complicated choices of $f$ and $g$. $\endgroup$ – Rulle Jun 24 '13 at 11:59
  • $\begingroup$ @Piostruk: unfortunately, I don't know such conditions, so sorry. $\endgroup$ – Ilya Jun 24 '13 at 12:01
  • 1
    $\begingroup$ Thank you anyway :-), I have upvoted your answer, but I will wait for others to have the chance to answer before accepting anything. $\endgroup$ – Rulle Jun 24 '13 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.