In constrained optimization problems, when is 'naive' substitution possible?

Question

To motivate the question, consider the following constrained optimization problem: $$ (P1)\quad \underset{(x,y)}{\min} f(x,y)=x^2 +y^2 \ s.t.\ (x-1)^3 = y^2$$

By replacing the constraint $y^2 = (x-1)^3$ in $f(x,y)=x^2 +y^2$, one gets the following unconstrained optimization problem: $$ (P2)\quad \underset{x}{\min} g(x)=x^2 + (x-1)^3 \ $$

These problems are not equivalent: although $(P2)$ is unbounded and doesn't have a minimum, $(P1)$ has a minimum in the point $(x,y)=(1,0)$.

Is there any necessary/sufficient conditions to assure that the unconstrained problem stemmed by replacing the constraint in the objective function is equivalent to the original constrained problem?

Answer 1

Consider the following third problem: $$\text{(P2a)} \quad \min_x ~~ g(x) = x^2 + (x-1)^3 ~~ \text{s.t.} ~~ (x-1)^3=y^2$$ I think you will agree that (P2a) is equivalent to (P1).

So it wasn't the substitution that is the problem! It was the fact that you also eliminated the constraint. It might seem, of course, that you could eliminate it at this point, because $y$ no longer appears in the objective. But this would be incorrect, because it still serves to constrain $x$: $$\begin{aligned}&(x-1)^3=y^2\quad\Longleftrightarrow\quad (x-1)^3\geq 0, \quad y\in\{+(x-1)^{3/2},-(x-1)^{3/2}\}\\ &\qquad\Longleftrightarrow\quad x\geq 1, \quad y\in\{+(x-1)^{3/2},-(x-1)^{3/2}\} \end{aligned}$$ Therefore, a correct model after eliminating $y$ is $$\text{(P2b)} \quad \min_x ~~ g(x) = x^2 + (x-1)^3 ~~ \text{s.t.} ~~ x\geq 1$$

I would therefore challenge your question itself. Rewriting the objective function in this manner is always acceptable. Dropping a constraint, however, is only acceptable if it can be proven that it is not active at any optimal point. Therefore, do not assume you can drop a constraint just because you rewrote the objective.

EDIT: perhaps this will help. Two optimization models are equivalent only if you can readily recover the solution to one from a solution to the other, and vice versa. Thinking about the conditions that must hold in order to be able recover an eliminated variable will help to prevent the elimination of essential constraints. For example, in this case, we can only recover $y$ if $(x-1)^3$ is nonnegative.

Answer 2

Hint: It would be good to realize what causes the substituted problem to be different. What extra conditions do we indirectly imply on $x$ if $(x-1)^3$ must be equal to a squared number?

Answer 3

You just made a mistake replacing $y^2$ by $(x-1)^3$. There is a hidden constraint on $(x-1)^3$ that you forgot: $(x-1)^3\ge 0$

Answer 4

In the 2 variable case, I believe that it is only appropriate to do pure substitution (as in, with no extra constraints thereafter) when the constraint is invertible for both variables. As a result, a single optimized value for x implies a single value for y vice versa. However, this is my intuition; I'm not entirely sure if this is the case. Please correct me if my logic is wrong.