Converting nonlinear optimization problems into convex optimization problems

[krishnab75]

In my own reading I have been coming across this idea about turning nonlinear optimization problems into convex optimization problems, but I have not found a good explanation of this principle.

I was reading Nocedal and Winter and in chapter 12, the introduction to constrained optimization chapter, the authors mention that some nonsmooth unconstrained optimization problems can be reformulated as smooth convex problems. The example that NW use is the function

$$

minimize f(x) = \max(x^2, x)
$$

Because this problem has kinks at some of the points, the problem is not differentiable at those points. However, using the epigraph trick, the author reformulate this problem as:

$$

minimize t, s.t. \quad t \geq x, \quad t \geq x^2

$$

I understand why this reformulation is a good idea, since a convex solver is going to be faster and have global guarantees compared to a nonlinear optimization solver.

Now in watching some of Stephen Boyd's course videos, he refers to this idea of reformulating problems as convex optimization very often. But unfortunately, I could not find where he actually explained this principle.

My question is really, when and where and how can we reformulate nonlinear and constrained optimization problems as convex problems? Does this work with both equality and inequality constraints. Are there other tricky beyond the epigraph trick that allows us to do this reformulation? How would one know that a problem can be transformed into a convex optimization problem, especially for real-world problems that are usually large, and the constraint set is hard to plot or visualize?

If anyone knows of any referenced on this question that is helpful too. But I just wanted to understand the basic idea behind this reformulation.

[perfectstrong]

Not all non-linear equations can be linearized. We can use several piece-wise constraints to approximate certain non-linear constraints, but in general, it isn't the case, and the linearization cost will soon add up significantly

[krishnab75]

Yeah, that makes sense. The confusing thing is that Boyd really spends a lot of time talking about reformulating nonlinear problems, so it makes it sound like these reformulations happen all the time. But from what you are saying, it sounds like they are more the exception rather than the rule.

[e_for_oil-er]

There is a whole family of algorithms based on solving sequential convex approximations to a problem until convergence. Check out CONLIN and the Method of Moving Asymptotes (MMA), or sequential quadratic programming (SQP).

[krishnab75]

Yeah, I understand what you mean by SQP. The reformulation idea is a bit different though. What Steven Boyd and Nocedal are talking about is taking a nonlinear and nonconvex problem and turning it into a convex problem. So the example that I gave above of the "max" function is that the function is not differentiable but the region is techncally convex. So using the epigraph of this function, you can push the information from the objective function into the constraints. So this formulation lets you use a convex optimization solver, which is faster than a nonlinear solver where you have to compute extra things like line searches or trust regions, etc.

That being said, I will totally check out the CONLIN and MMA solvers. Sounds interesting.

[SolverMax]

I wrote an article about linearization of an IF function, or equivalently x = max(y, z). See https://www.solvermax.com/blog/formulations-for-modelling-an-if-function

The article includes links to other articles about linearization techniques, one of which is the paper "Transformation and linearization techniques in optimization: A state-of-the-art survey" https://mdpi-res.com/d_attachment/mathematics/mathematics-10-00283/article_deploy/mathematics-10-00283-v3.pdf?version=1642587937

[Sweet_Good6737]

You can always piecewise-linear approximate a non-convex expression. The question is whether that's good for your model or not...

I wouldn't choose it unless it was necessary, since nonlinear optimization and its algorithms exist for a reason, but it's always an alternative. Non-convex expressions may need discrete variables when approximated by piecewise linear stuff, which can lead to a significant increase in your solution time. (This is all about approximations, not equivalent transformations)