For example, I have a function to optimize: $$f_1(x,y) = x^2+y^2, \quad x_{lb}\le x\le x_{ub},\quad y_{lb}\le y\le y_{ub}$$ Then I apply rotation by $\theta$ plus translation by $x_0$ and $y_0$: $$f_2(x,y) = ((x+x_0)\cos\theta + (y+y_0)\sin\theta)^2 + (-(x+x_0)\sin\theta + (y+y_0)\cos\theta)^2$$ Intuition tells these functions are equivalent given bounds are far enough from $x_0$ and $y_0$. However, practical optimization methods, e.g. Differential Evolution, usually have problems with rotated and translated functions - they optimize original functions well, but no so good the rotated versions.

So, I'd like to know some formal general proof that for optimization (especially non-convex case) these functions should be equivalent. And it's also interesting to hear reasoning why DE optimization methods may fail.

  • 1
    If they are rotational-tranlational invariance... they will be equivalent. i mean, the function $f(x) = x^Tx$ is invariant w.r.t. rotations $x'=Rx$ because $f(x') = (Rx)^TRx = x^TR^TRx=x^Tx$, since $R$ is an orthogonal matrix. – HBR May 9 at 15:34
  • Then how do I know if a function has a rotational-translational invariance? Isn't all functions rotational-translational invariant from optimization standpoint? – aleksv May 9 at 15:50
  • The minimum of $f(x) = (x-x_0)^T(x-x_0)$ is obviously $x_0$. If this minimum depends on the translation, then it is not translational invariant. – HBR May 9 at 16:34

Let $f: \mathbb R^N→\mathbb R$, $x \in \mathbb R^N$ and $z=t(x)$ where $ t$ is a bijective mapping.

Let

$$x^* = \text{argmax}_x f(x)$$

$$x_1^*= \text{argmax}_x f(t(x))$$

Using $z=t(x)$, and applying $t$ on both sides,

$$t(x_1^*)= t\left(\text{argmax}_{t^{-1}(z)} f(z)\right)$$

So we have

$$t(x_1^*)= \text{argmax}_{z} f(z) = x^*$$

For intuition, we can think of the transformation as doing some kind of rearrangement of points in the domain. So the max value of the function remains unchanged. The argument which maximizes will be different. We get the original solution by transforming the argument.

If you are already doing the argument transformation, then may be you need to transform the initial points also to get similar results as that of the original optimization.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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