# Can Adding a Convex Term to a Non-Convex Optimization Problem Make it Convex?

In Machine Learning optimization problems - a "regularization" term is often added to the optimization problem to reduce overfitting: I have noticed that in the case of the L2-Norm regularization, this term (i.e. a function) can be considered as a Convex Term as it is basically "quadratic" in nature.

My Question: In the L2-Norm case, the optimization problem without this regularization term is likely a Non-Convex problem - but we then add a Convex Term to this problem. Do we know if doing this (i.e. adding the Convex Term to a Non-Convex Optimization Problem) automatically makes the optimization problem as Convex?

I do not think that this is the case, seeing as:

• Convex Optimization Problems are generally easier to solve than Non-Convex Optimization Problems

• Anecdotally, I have heard of Regularized Loss Functions (e.g. for Neural Networks) that are considered to be "very difficult" optimization problems - even though they have this Convex Term. This informally leads me to believe that in the case of L2 Regularization, the fundamental optimization problem remains Non-Convex.

However, "anecdotal and informal logic" is generally never acceptable in understanding mathematics.

Can someone please comment on this?

Thanks!

• Certainly not automatically; if lambda is small enough then your equation will be indistinguishable from the original. Mar 13, 2022 at 18:03
• Non-convex plus convex is non convex. One of the main issues with the optimization problems for Neural Networks is the large amount of data and the large amount of variables/constraints. But it also true that the costs may be pretty ugly.
– KBS
Mar 13, 2022 at 18:24
• Thank you everyone for your replies! Much Apprecaited! Mar 13, 2022 at 19:21
• @KBS That is a good rule of thumb but is not always true. Mar 13, 2022 at 19:48
• @RobPratt Yes, you are right.
– KBS
Mar 13, 2022 at 20:22

Yes, adding a large enough convex term can make a problem convex. For example, consider the nonconvex function $$-x^2$$ and the convex function $$x^2$$. For constant $$\lambda \ge 1$$, the sum $$-x^2 + \lambda x^2=(\lambda-1)x^2$$ is convex.
This is also a standard trick in binary quadratic programming, where $$x_i$$ is a binary decision variable and the objective is to minimize the multivariate quadratic function $$\sum_i \sum_j q_{ij} x_i x_j + \sum_i c_i x_i$$ subject to linear constraints. Let $$\lambda$$ be the absolute value of the smallest (negative) eigenvalue of $$Q=(q_{ij})$$. Then adding $$\lambda(x_i^2-x_i)$$, which is $$0$$ when $$x_i$$ is binary, makes the objective function convex.