Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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$

share|improve this answer

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.