# Optimization problem equivalence

Consider the following two optimization problems:

\begin{align} \tag{1} \min_{x \in V} \quad & f(x) \\ \text{ s.t.} \quad & x \in A \end{align}

\begin{align} \tag{2} \min_{y \in W} \quad & g(y) \\ \text{s.t.} \quad & y \in B \end{align}

What is the definition of equivalence of $$(1)$$ and $$(2)$$?

Does it mean that there exists a bijection $$\phi: A \rightarrow B$$ such that \begin{align} x^{\star} \text{ is optimal for } (1) &\implies \phi(x^{\star}) \text{ is optimal for } (2) \\ y^{\star} \text{ is optimal for } (2) &\implies \phi^{-1}(y^{\star}) \text{ is optimal for } (1) \end{align}

In my opinion, the word "equivalence" is typically used in a rather informal way here. It means that you can compute a solution of (2) "easily", if you have a solution of (1) available, i.e., without "solving" (2) again; and vice versa. This can mean that you announce a function $$\phi$$ which has the property that you have mentioned, but under the "constraint", that this function can be evaluated "easily".