1

I have a very basic level in optimization, so sorry in advance if my question is naive or very basic.

I am considering an objective function $f(x_1, x_2, x_3) = \phi(x_1, x_2) + \psi(x_2, x_3)$ and I'm trying to minimize it over the variable $x = (x_1, x_2, x_3) \in \mathbb{R}^3$. For several reasons relative to my problem, it's impossible to minimize the whole function in one shot. So what I do is basically the following (once again, there is no mathematical validity behind this choice, just practical considerations):

  1. Minimize $\phi$ over $(x_1, x_2)$. I obtain $x_1^*$ and $x_2^*$.
  2. Minimize $\psi$ over $(x_2, x_3)$. I obtain $x_2^{**}$ and $x_3^*$.

My two questions are the following: Is it possible (under some conditions) to upper-bound the difference $|\phi(x_1^*, x_2^*) + \phi(x_2^{**}, x_3^*) - \min_x f(x)|$ and/or the distance between $x^* = arg\min f$ and the approximate solutions $(x_1^*, x_2^{*}, x_3^*)$ and $(x_1^*, x_2^{**}, x_3^*)$?

Thank you in advance for your insights!

PAM
  • 315
  • 1
    Without providing an answer, I think that the difference can actually be quite large. Take, for instance: $$f(x_1,x_2,x_3)=\underbrace{1+x_1^2+x_2^2}{=\phi(x_1,x_2)} + \underbrace{1 + (x_2-10)^2 + (x_3-20)^2}{=\psi(x_2,x_3)}. $$ Clearly, $f$ has a global minimum at $(0,5,20)$ with: $$ 52 = \min \limits_{x_1, x_2, x_3} f(x_1, x_2, x_3). $$ With your notations $(x_1^{\ast}, x_2^{\ast})=(0, 0)$ and $(x_2^{\ast\ast},x_3^{\ast})=(10, 20).$ Then: $$ \vert \phi(x_1^{\ast},x_2^{\ast}) + \psi(x_2^{\ast\ast},x_3^{\ast}) - \min f \vert = 50. $$ – pitchounet Jul 26 '17 at 08:04
  • Interesting example, thank you! It basically shows that I have to constraint the question a bit more if I want something that cannot be arbitrarily large. – PAM Jul 26 '17 at 08:14
  • I believe so, yes. – pitchounet Jul 26 '17 at 08:15

0 Answers0