# 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}

## 1 Answer

First, I would like to mention that what you have written is equivalent to "the cardinality of solutions of (1) coincides with the cardinality of solutions of (2)".

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".