2
$\begingroup$

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 [1] 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.

[1] Luenberger and Ye, "Linear and Nonlinear Programming"

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – D.W. Feb 18 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.