0
$\begingroup$

I am trying to implement the Levenberg-Marquardt algorithm similarly to Cui et al. Full and fast calibration of the Heston stochastic volatility model, 2017 here (although using a different method to pricing the option under Heston dynamics). They have their damping factor set to be $\mu_0$ and an initial $\nu_0=2$. Every time calibration step is worse, they reject the step and let $\mu_{t+1} = \mu_t\nu_t$ and $\nu_{t+1} = 2\nu_t$. But when they get closer to the optimum, they accept the step and set $\mu_t =\mu_t$ and $\nu_t = \nu_t$. (So they don't decrease the damping factor).

I have seen other Heston calibration papers do the same thing. But from the literature I have read on the levenberg algorithm, the damping factor should decrease when the step is accepted (generally by the same amount as when it's accepted, so set $\mu_{t+1} =\frac{1}{\nu_t}\mu_t$).

So why is the damping factor not decreasing on accepted steps? My intuition tells me that we never decrease it because since we are calibrating over 5 parameters, we want to prevent getting stuck in local minimums. But then wouldn't you just use a normal gradient descent algorithm to begin with?

The LEVMAR package references a text by K. Madsen. METHODS FOR NON-LINEAR LEAST SQUARES PROBLEMS, 2004 here, which says that when a step is accepted, we set: $$\mu=\mu\text{max}\{\frac{1}{3},1-(2\eta-1)^3\},\quad \nu=2$$ where $\eta$ is the gain factor. When a step is rejected, we set:

$$\mu=\mu\nu, \quad \nu=2*\nu$$

But as you can see, $\mu$ will be decreasing for rejected steps, whilst the authors of the Heston paper do not decrease there's. If the calibration starts-off far away from the optimum, it will behave as gradient descent, but never behave as the Newton method once it gets close.

Also something that I’ve noticed that other papers have not addressed is that $\frac{\partial C}{\partial \rho}$ always be a lot smaller than the other parameters. So you will be constantly breaching the constraints on $\rho$ (if you want to be adjusting the other parameters in a reasonable amount of time). You can obviously force $-1<\rho<-0.001$, but $\rho$ will inevitably end-up at the bounds. Is there any literature that I’ve missed that has addressed this phenomenon?

$\endgroup$
1
  • $\begingroup$ The paper you have cited has a paragraph (below equation 35) about when the equation being dominated by GaussNewton iterates with $u_k$ at very small values, and when this can apply (which they state it does for the problem). This contradicts the Algorithm they construct. I suspect they want to use, $u_{k+1} = u_k / v_k$ not $u_{k+1} = u_k$. After a successful iterate I see no reason why they would not reduce. $\endgroup$
    – Attack68
    Commented Nov 15, 2023 at 20:55

1 Answer 1

1
$\begingroup$

The situation is a little more complicated than expected. We use this notation for the damped least squares equation

$$ [J^{T}J + \lambda I_{d}] \Delta \theta = -\nabla f(\theta) $$

where $\theta$ is the vector of model parameters, $J$ the Jacobian matrix, and $I_{d}$ the identity matrix.

Theoretically if you wanted to get the exact step value you would have to solve an additional minimization problem along the descent direction, that is, solve this problem

$$ \min_{\Delta \theta \in \mathbb{R}^{m}} || J + J \Delta \theta ||^{2}_{2} $$

Only as you can well imagine such a procedure would be even heavier in terms of computational cost. The reason why then arbitrary $\lambda$ is chosen and then gradually reduced is that implementations use simpler criteria, among the simplest being this

$$ f(\theta^{(k+1)}) < f(\theta^{(k)}) $$

Basically, you reduce lambda as long as the value of $f_{obj}$ at iteration $(k+1)$ is not less than that at iteration $(k)$, which means you are approaching a "local" minimum point.

Keep in mind that although the authors themselves have proposed strategies for estimating lambda, even they state that the choice of lambda is made "by trial and error."

I hope this has answered your question.

$\endgroup$
3
  • $\begingroup$ I am still confused. You said $\lambda$ (which is the same as $\mu$) is gradually reduced, but in the paper Heston paper, it is not reduced. I have made another edit to my post with more details. $\endgroup$ Commented Nov 7, 2023 at 3:13
  • $\begingroup$ I can't figure out what is not clear to you. The $\lambda$ reduction (or $\mu$ as you call it) however is done when the condition $f(\theta^{(k+1)}) < f(\theta^{(k)})$ because, in theory, it would be desirable to have a high enough $\lambda$ so as to take large steps and arrive with a few iterations at the minimum. However, consider that as my numerical calculus prof used to say, a search method for minima works if you give the solution (or something very close to it) as the initial input. $\endgroup$
    – SimoPape
    Commented Nov 7, 2023 at 6:56
  • $\begingroup$ It is clear, I understand why we reduce. I am asking why in the paper $\mu$ is NOT being reduced. In the paper, when $f(\theta^{(k+1)}) < f(\theta^{(k)})$ occurs, $\mu$ is left unchanged. I am asking why is that the case, when other resources, and yourself, say the opposite $\endgroup$ Commented Nov 8, 2023 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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