I have an optimization problem roughly of the form
$$ \max_{\mathbf x} f(\mathbf x) \quad \text{s.t. } g(\mathbf x) \leq 0$$
where $f(\mathbf x)$ is convex and $g(\mathbf x)$ is convex in $x_i$, $i\in\mathcal I$, and concave in $x_i$, $i\not\in\mathcal I$.
Can one reformulate this to a new problem with convex feasible region, so that $g(\mathbf x)$ appears as term of the objective function?
My motivation for this is to then analyse this new objective further and may being able to apply Difference-of-Convex programming methods in order to solve this.
Best Answer
Yes, it's possible for an infinite sequence of problems. Let us say that the problem is written as: $$ \max_{\mathbf x} f(\mathbf x) \quad \text{s.t. } g(\mathbf x) \leq 0, h(\mathbf x)\leq 0,$$ with $g$ convex and $h$ concave. Hence, your concern is equivalent to optimize all problems of the form: $$ \max_{\mathbf x} f(\mathbf x) + \rho_k\|h(\mathbf x)_{+}\| \quad \text{s.t. } g(\mathbf x) \leq 0,$$ with $\rho_k$ increasing to infinity. This technique is called penalization. Augmented Lagrangian methods already use these ideas, but they try to not increase $\rho_k$ to infinity by adding an augmented term in the objective function. You could use these ideas, trying to learn how to use it for your purposes.
Interior points methods have similar ideas, but I'm not aware of an Interior Point method implementation that have similar properties of not necessarily increasing the penalization during the optimization process, but I am not an expert in such methods.
P.S.: The article A Shifted Primal-Dual Penalty-Barrier Method for Nonlinear Optimization describes an Interior Point method that uses the ideas of the Augmented Lagrangian method of not needing to increase the penalization. If I am not mistaken, his ideas on the CAKKT are wrong. The CAKKT optimality condition is not proven to be satisfied by limits point of such method. Although the method has interesting numerical results.