In Boyd and Vandenberghe (https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf), section 4.1.3, they say:
We call two problems equivalent if from a solution of one, a solution of the other is readily found, and vice versa. (It is possible, but complicated, to give a formal definition of equivalence.)
I'm trying to find a formal definition. I have something relatively simple, so I wonder if I'm missing something.
Let $P$ be a problem defined over a domain $D$ and $Q$ a problem defined over a domain $E$. We say that $P$ are $Q$ are equivalent iff there exist functions $\phi : D \rightarrow E$ and $\psi : E \rightarrow D$ such that:
- $x \in D$ optimal in $P$ $\Rightarrow$ $\phi(x) \in E$ optimal in $Q$.
- $y \in E$ optimal in $Q$ $\Rightarrow$ $\psi(y) \in D$ optimal in $P$.
In particular, what I might be missing is whether any properties should be required on $\phi$ and $\psi$. Maybe they need to be monotonic? Thoughts?