I have a doubt with the concept of nonconvexity in equality constraints.
For an optimization problem to be convex, the objective function and the constraints have to be convex. $x^2$ is a convex function, since its epigraph is a convex set. Therefore, an example of a convex optimization problem is:
$$\min x^2 \tag{I}$$
However, we could rewrite this problem as:
$$\begin{equation}\min y\\s.t. \qquad y=x^2\end{equation}\tag{II}$$
Does this mean that the second notation is nonconvex, even though they are the same problem? It is true that the equality can be divided in a convex and nonconvex region using inequalities.
$$\min y\\s.t. \qquad y\geq x^2 \quad(convex)\\ \qquad \,\,\,\quad y\leq x^2 \quad(nonconvex) \tag{III}$$
But isn't it basically the same as $II$, which is basically the same as $I$?
Thank you for your time!
Best Answer
I think your intuition is correct, i.e. you can sometimes transform a non-convex problem in an equivalent convex one and vice versa. For example, as long as the cost function is non-linear, you can apply a substitution like you did, adding a non-linear equation as constraint and splitting said equation in a convex + non-convex pair of inequalities. In this sense, convexity also depends on the form in which the problem is formulated.
Even though mathematically speaking the solutions to the different forms are equivalent, form does make a difference when you attempt to solve such problems through numerical optimization. In fact, the solution of convex problems is usually much faster.