Exterior penalty method in optimization

Question

If we need to minimize a function $f(x) = x$ under the constraint $g(x) = 5 - x <0$ using the exterior penalty method, so instead of minimizing $f(x)$, we minimize the function: \begin{equation} min \ \ f(x) + \mu [max(0,g(x))]^2 \end{equation} My question is why do we square the penalty function $max(0,g(x))$ not to power 1, or power 3?

Answer 1

The penalty function could have any power, but with power 2 we have that smooth convex problems, i.e., \begin{align} \text{min } & f(x) \\ \text{s.t. }&\ \ Ax=b \\ & -x \leq 0 \\ & c(x) \leq 0, \end{align} with $c: \mathbb{R}^{n}\rightarrow \mathbb{R}^p$ and $f: \mathbb{R}^{n}\rightarrow \mathbb{R}$ convex in each coordinate, transforms into an unconstrained smooth convex problems, i.e., the optimization problem $$\text{min} \ f(x) + \mu \left(\|Ax-b\|^2 + \|(-x)_{+}\|^2 + \|c(x)_{+}\|^2 \right)$$ is still smooth and convex. This type of smooth problem is the easiest to solve. For odd power number, this is not true. Furthermore, for higher even powers, the penalized problem starts to become more and more ill-conditioned, which means that the problem becomes hard for numerical algorithms to find a precise minimum. Roughly, ill-conditioned problems are related to more computational effort in solving subproblems, which makes the original problem harder to solve.

For example, your optimization problem stated in your question is convex and is transformed into an unconstrained convex problem by the quadratic penalty function. With other powers, the problem or it would be harder to solve, or it would not be convex and smooth.