Is it a correct way to solve any convex optimization problem with inequality constraints?

Question

Let $x \in {\mathbb R}^n$, and $f_0,f_1,\ldots f_m$ are convex functions on ${\mathbb R}^n$. Consider the following problem:

\begin{equation} (\mathrm{P1})~~~~~~~~~~~~~~~~~~ \begin{split} &\mathrm{minimize}~~~~~f_0(x)\\ &s.t.~~~~~~~~~~~~~~f_i(x) \leq 0,\quad i\in\{1,\ldots,m\} \end{split} \end{equation}

Then, can I solve (P1) by the following procedure?

Step 1: Solve $\mathrm{minimize}~f_0(x)$, and derive $x_1^*$.

Step 2: Judge if $x_1^*$ is feasible to the constraints in (P1), i.e., if $f_i(x_1^*) \leq 0$ for all $i \in \{1,\ldots,m\}$. If $x_1^*$ is feasible to them, then the minimizer of (P1) is $x_1^*$. Otherwise, we consider Step 3.

Step 3: Solve

\begin{equation} (\mathrm{P2})~~~~~~~~~~~~~~~~~~ \begin{split} &\mathrm{minimize}~~~~~f_0(x)\\ &s.t.~~~~~~~~~~~~~~f_i(x) = 0,\quad i\in\{1,\ldots,m\}, \end{split} \end{equation} and derive $x_2^*$. Then, $x_2^*$ is the optimal solution to (P1).

The algorithm above does not need any optimization technique in dealing with the inequality constraints. In step 1, we solve an unconstrained optimization problem. In step 2, we solve an optimization problem with equality constraints.

In my opinion, this algorithm can correctly return the optimal solution to (P1), since the global minimizer is either within the feasible region described by $f_i(x) \leq 0$ ($i \in \{1,\ldots,m\}$), or on the boundary of the feasible region. Am I right?

Thanks!

Answer 1

This is an excellent question, almost always asked by our students. This approach has several major flaws:

1. Solving equality constrained problems, unless the constraints are affine, is harder than inequality constrained problems. For example, the constraint $x^2 + y^2 - xy - y = 2$ is harder to handle than $x^2 + y^2 - xy -y \leq 2$
2. It might happen that all optimal points $x^*$ satisfy some of the constraints with equality while others as strong inequalities. That is, for some $i$ we have $f_i(x^*) = 0$, while for other $i$ we have $f_i(x^*) < 0$. In that case, your algorithm will miss all optimal points.