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

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!

• I guess P2 may be non convex in general. – AndreaCassioli Dec 9 '17 at 13:35
• @AndreaCassioli You are right, and thanks very much for your comments. – Ryan Dec 9 '17 at 13:37
• @AndreaCassioli How to close this problem without deleting it? – Ryan Dec 9 '17 at 13:40
• You can't, really. But it is fine to leave it. – Michael Grant Dec 9 '17 at 21:32
• @MichaelGrant Thanks for your help :-) – Ryan Dec 10 '17 at 2:09

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.