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}


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


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.