# Using exponential penalty functions in constrained nonlinear optimization

## Background: penalty functions

Penalty functions convert a constrained optimization problem

$$\begin{equation}\begin{split} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) \leq 0 \end{split}\end{equation}$$

into an unconstrained optimization problem

$$\begin{equation}\begin{split} \text{minimize} \quad & f(x) + p(g(x), t) \end{split}\end{equation}$$

where $$p: \mathbb{R} \mapsto \mathbb{R}$$ is a nondecreasing function and $$t > 0$$ is a "temperature" that increases as the optimization procedure iterates, causing the penalty function to become "harder", i.e.:

$$\lim_{t \to \infty} p(g, t) = \begin{cases} 0 :& g < 0 \\ \infty :& g > 0 \end{cases}$$

The standard choice of a penalty function  is something like

$$p_q(g, t) = \begin{cases} 0 :& g \leq 0 \\ t g^2 :& g > 0. \end{cases}$$

This quadratic penalty has the property that $$p_q(g,t) = 0$$ whenever $$g < 0$$. In contrast, another choice would be an exponential penalty,

$$p_e(g,t) = \exp(tg).$$

The exponential penalty has the right behavior in the limit, but $$p_e(g,t) > 0$$ for $$g < 0$$ and $$t < \infty$$. This seems bad: consider the case where $$x^*$$ is a global optimizer of $$f$$ but $$g(x^*)$$ is very close to zero. If there is a solution $$x'$$ where $$f(x') > f(x^*)$$ but $$g(x') \ll 0$$, then the exponential penalty solution may be biased towards $$x'$$.

## Penalty functions with simulated annealing

I am using penalty functions with simulated annealing (SA) optimization for nonconvex problems and, despite their theoretical drawbacks, I have found generally better results using exponential penalties (solutions with lower $$f(x)$$).

Simluated annealing works as follows. Let $$E(x,t) = f(x) + p(g(x), t)$$:

1. Start with an initial guess $$x$$.
2. Generate a perturbed value $$x'$$ by applying some random small change to $$x$$
3. If $$E(x') < E(x)$$, $$x \gets x'$$
4. If $$E(x') \geq E(x)$$, $$x \gets x'$$ with probability decreasing in $$t(E(x') - E(x))$$
5. Increase $$t$$, go to 2.

Note that SA is usually written with a decreasing temperature, but I have changed it to allow using the same variable as the penalty function temperature.

Is there any reason why exponential penalties might work better in practice? I have seen some applications papers using SA with exponential penalties, but I have not found any published justifications for using exponential instead of quadratic.

One hypothesis: since the exponential penalty distinguishes between feasible solutions that nearly violate a constraint and those that are far from any constraints, it could somehow bias $$x$$ towards regions where most random perturbations produce an $$x'$$ that does not violate the constraints, making it "easier" to move between the basins of attraction of different local optima. However, I do not know if this is true, or how to formalize it.

 Luenberger and Ye, "Linear and Nonlinear Programming"

• That sounds like a plausible hypothesis. This is an empirical field where the way to find out is to try it, and where the behavior depends on the problem (on $f$), so it may be hard to know why. An experiment you might try to test your hypothesis would be to try optimizing with the penalty function $p_{e+}(g,t) = \exp(tg)$ if $g\ge 0$, else $p_{e+}(g,t) = 1$ if $g \le 0$, and see what happens. If your hypothesis is correct, I predict this should behave worse than $p_e$, i.e., it should be similar to $p_q$. – D.W. Feb 18 '19 at 1:43