3
$\begingroup$

I'm using BFGS to optimize a smooth but non-convex function $f$ that is computed by a simulation. The simulation also gives me a semi-analytical gradient $g$, which is verified by the numerical gradient.

As $f$ is non-convex and I am using a penalty function to enforce bound constraints, I do not expect to find a global minimum, but rather a local one where the gradient also happens to vanish. However, when BFGS "converges" (in terms of very small $\Delta x$ and $\Delta f$), $\Vert g \Vert_\infty$ remains quite large. I can think of a few reasons for this:

  1. The penalty function is large close to the bounds -- this is not the case here though, as the penalty function is sufficiently scaled down at this point

  2. The downward slope of the gradient is intersecting with one of the boundaries -- BFGS can't move away from the boundary since that will increase the function, but also cannot approach it further, causing it to get stuck. This might be the case since the step size is virtually zero at "convergence".

Can anyone suggest any other reasons for this behavior, or a way to verify if (2) is indeed the cause?

$\endgroup$
  • $\begingroup$ We're not really in a position to check what's happening in your code. Your second hypothesis is quite reasonable- why not check for yourself whether this is happening? $\endgroup$ – Brian Borchers May 9 at 14:36
  • $\begingroup$ Of course not, and I left further details about the function and gradient out of my question so the answers can help others who encounter a similar problem (i.e. I'm looking for potential reasons and how to test them rather than a solution for my specific code). To be clear, I did check, and some of the variables are practically at their boundaries. But I'm not sure if that's the cause or if there's another potential one I'm missing. $\endgroup$ – convergedandconfused May 9 at 14:40
  • 2
    $\begingroup$ To more fully understand @Wolfgang Bangerth 's answe, look up Karush-Kuhn-Tucker (KKT) conditions en.wikipedia.org/wiki/… . Also, putting penalties on bound constraint violations is a numerically bad way of dealing with the,. Use a BFGS code designed for at least bound constraints. $\endgroup$ – Mark L. Stone May 10 at 15:48
7
$\begingroup$

For a bounds-constrained problem to minimize $f(x)$ subject to $h(x)\ge 0$, there is no reason for $\nabla f(x^\ast)$ to be small at the optimum $x^\ast$. All the theory guarantees is that $\nabla f(x^\ast) + \lambda^\ast \nabla h(x^\ast)=0$ if the optimum is at a place where the bound is active.

In your case, you are imposing the bound via a penalty approach, which I assume to mean that you are minimizing $F_\varepsilon(x)=f(x)-\frac{1}{\varepsilon}\ln(h(x))$. In that case, at the optimum, it is again not reasonable to expect that $\nabla f(x^\ast)$ is small. All you know is that $\nabla F_\varepsilon(x^\ast)$ is small -- something you can easily check.

$\endgroup$
  • $\begingroup$ Thank you, that all makes sense. For the original constrained problem, what you wrote seems to be the theoretical explanation for case (2). Regarding the "unconstrained" penalized problem, using your notation I assume that $\varepsilon \rightarrow \infty$, and indeed at convergence it is so large that $\nabla f$, $\nabla F_\infty$ are practically identical and not small at all (I realize that the gradient of the barrier function should grow to compensate). When minimizing, say, $f=sin(x)$ for $x \in [0,\pi/2]$, I do get the behavior you describe, so I wonder if there's something else at work. $\endgroup$ – convergedandconfused May 10 at 10:58
  • $\begingroup$ I let $\varepsilon\rightarrow 0$. At the optimum, $\nabla F_\varepsilon(x^\ast)=0$, which implies that $\nabla f(x^\ast) = \frac{1}{\varepsilon h(x^\ast)}\nabla h(x^\ast)$. $\endgroup$ – Wolfgang Bangerth May 10 at 16:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.