## Chaotic behavior in an algorithm to escape from poor local minima in lens design

Optics Express, Vol. 17, Issue 8, pp. 6436-6450 (2009)

http://dx.doi.org/10.1364/OE.17.006436

Acrobat PDF (880 KB)

### Abstract

In lens design, damped least-squares methods are typically used to find the nearest local minimum to a starting configuration in the merit function landscape. In this paper, we explore the use of such a method for a purpose that goes beyond local optimization. The merit function barrier, which separates an unsatisfactory solution from a neighboring one that is better, can be overcome by using low damping and by allowing the merit function to temporarily increase. However, such an algorithm displays chaos, chaotic transients and other types of complex behavior. A successful escape of the iteration trajectory from a poor local minimum to a better one is associated with a crisis phenomenon that transforms a chaotic attractor into a chaotic saddle. The present analysis also enables a better understanding of peculiarities encountered with damped least-squares algorithms in conventional local optimization tasks.

© 2009 Optical Society of America

## 1. Introduction

1. G. W. Forbes and A. E. Jones, “Towards global optimization with adaptive simulated annealing,” in *1990 Intl Lens Design Conf*,
G. N. Lawrence, ed., **vol. 1354** of Proc. SPIE , 144–153 (1991). [CrossRef]

4. K. E. Moore, “Algorithm for global optimization of optical systems based on genetic competition,” in *Optical Design and Analysis Software*,
R. C. Juergens, ed., **vol. 3780** of Proc. SPIE , 40–47 (1999). [CrossRef]

5. L. W. Jones, S. H. Al-Sakran, and J. R. Koza, “Automated synthesis of both the topology and numerical parameters for seven patented optical lens systems using genetic programming,” in *Current Developments in Lens Design and Optical Engineering VI*,
P. Z. Mouroulis, W. J. Smith, and R. B. Johnson, eds., **vol. 5874** of Proc. SPIE , 587403 (2005). [CrossRef]

6. J. P. McGuire, “Designing easily manufactured lenses using a global method,” in *International Optical Design Conference 2006*,
G. G. Gregory, J. M. Howard, and R. J. Koshel, eds., **vol. 6342** of Proc. SPIE , 63420O (2006). [CrossRef]

07. J. R. Rogers, “Using global synthesis to find tolerance-insensitive design forms,” in *International Optical Design Conference 2006*,
G. G. Gregory, J. M. Howard, and R. J. Koshel, eds., **vol. 6342** of Proc. SPIE , 63420M (2006). [CrossRef]

8. O. Marinescu and F. Bociort, “Network search method in the design of EUV lithographic objectives,” Appl. Opt. **46**, 8385–8393 (2007). [CrossRef] [PubMed]

11. A. Serebriakov, F. Bociort, and J. Braat, “Finding new local minima by switching merit functions in optical system optimization,” Opt. Eng. **44**, 100,501 (2005). [CrossRef]

15. M. van Turnhout and F. Bociort, “Instabilities and fractal basins of attraction in optical system optimization,” Opt. Express **17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

## 2. Algorithm with adaptive damping for searching beyond local minima

**J**of the optimization problem to find the search direction in which the value of the merit function decreases. This derivative matrix

**J**is subjected to a singular value decomposition (SVD) with complete orthogonalization of both the operand space (dimension

*m*) and the variable space (dimension

*n*).

*λ*. Successive linear damped solutions are then obtained by solving the system

*λ*, where the index

_{k}*k*denotes the cycle number of the inner loop.

**I**is the identity matrix, zero padded where needed given the dimensions (

*m*,

*n*) of the system and

**f**is the vector of operand values to be reduced to zero or certain target values. The vector of operand values is extended when necessary with the weighted values of constraint violations. For more details, see Ref. [16].

*λ*is done as follows. For the

_{k}*k*-th iteration in the inner loop,

*λ*is given by:

_{k}*S*

_{1}is the largest singular value delivered by the SVD and

*p*and

*a*are values to be provided by the user. In this work, we have chosen a fixed value

*a*= 10, but the value of

*p*has been varied. In the following two sections,

*p*will be the control parameter that determines whether the algorithm converges or whether its behavior is more complex. During optimization, the algorithm monitors the decrease in the squared value ∣

**f**

*∣*

_{k}^{2}of the merit function as a function of the counter

*k*and stops the iteration of the inner loop when the merit function starts increasing again.

**x**corresponding to the exact local minimum of the merit function. The quasi-minimal linear solution

**x**

*is used to update the system variables. The new working point is then used to obtain the derivative matrix that serves for the next (outer) optimization cycle.*

_{k}**f**

_{k+1}∣

^{2}> ∣

**f**

*∣*

_{k}^{2}.

## 3. Period doubling route to chaos

*c*

_{2}and

*c*

_{3}, respectively) as variables. For sufficiently large damping, optimizing the two variable curvatures results in five different local minima (A, B, C, D, and E), which are shown in Fig. 1. More details about this optimization problem are given in a recent open access paper [15

15. M. van Turnhout and F. Bociort, “Instabilities and fractal basins of attraction in optical system optimization,” Opt. Express **17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

*p*, and the number of iterations that have been performed. Therefore, in this paper, we present three sorts of numerical results, in which one of these factors is varied.

*p*is sufficiently large, the algorithm is convergent, as expected. For our example, in order to show which configuration leads to a certain local minimum, we compute the basin of attraction for that local minimum. (The set of all starting configurations that are attracted to a local minimum is the basin of attraction for that minimum [15

15. M. van Turnhout and F. Bociort, “Instabilities and fractal basins of attraction in optical system optimization,” Opt. Express **17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

18. H. E. Nusse and J. A. Yorke, “Basins of attraction,” Science **271**, 1376–1380 (1996). [CrossRef]

*p*= 0.002. In this and in the following figures of the same kind, curvatures

*c*

_{2}and

*c*

_{3}are plotted along the vertical and horizontal axis, respectively. The five local minima (see Fig. 1) are indicated by blue dots and the letters A, B, C, D, and E. Compared to the other minima, minimum B has a high merit function value.

*p*, we observe types of behavior that are much more complex than the convergent behavior towards the minima shown in Fig. 2. In the asymptotic regime, the limit of the sequence of iterations is then not necessarily a point, but can be a set of points. For example, for a certain starting configuration in the former basin of local minimum C, below a critical value of

*p*≈ 0.000138, the algorithm does not converge to local minimum C anymore. Figure 3 shows how the algorithm oscillates between different points in the variable space when we decrease the value for

*p*. For each value of

*p*, we computed 999 iterations. The values of curvature

*c*

_{3}of the last 899 iterations are plotted superimposed as function of

*p*(

*p*decreases along the horizontal axis). Since we are interested in the asymptotic behavior, the first 100 iterations are discarded in the figure in order to avoid transitory features.

*p*

_{1}≈ 0.000138, we observe a so-called pitchfork bifurcation [19]. Minimum C, which was stable for higher values of

*p*, becomes unstable, but a stable pair of points (both of them distinct from C) appears. For

*p*between 0.000138 and 0.000095, the algorithm alternates in the asymptotic regime between the upper and lower branch resulting from the bifurcation, which correspond to two points with different values of the merit function, without ever converging to any of them. This means that we have a periodic attractor consisting of two points. (An attractor is the set of points in the two-dimensional variable space towards which starting configurations in the corresponding basin of attraction approach asymptotically in the course of the outer iteration process.)

*p*= 0.000100 can be discarded.)

*p*is decreased further, the two points bifurcate again into four points at

*p*

_{2}≈ 0.000095 (period of four), then at

*p*

_{3}≈ 0.000086 into eight points (period of eight). In the latter case, only seven out of eight distinct points can be easily distinguished in Fig. 3, because two points in the attracting set have approximately the same value for

*c*

_{3}. Examining the values of curvature

*c*

_{2}shows that these points are distinct. Note that the values of

*p*where the bifurcations take place, become closer and closer to each other, until

*p*reaches a critical value at which a chaotic set of attracting points appears. This behavior is known as the period doubling route to chaos, the most common of several routes to chaos for a nonlinear dynamical system [19].

20. I. Castillo and E. R. Barnes, “Chaotic behavior of the affine scaling algorithm for linear programming,” SIAM J. on Optimization **11**, 781–795 (2000). [CrossRef]

*δ*= 4.6692…) encountered for functions that approach chaos via period doubling [21]. After a range of chaotic behavior, for values of

*p*smaller than approximately 0.000071, the algorithm encounters ray failures and the iterative process is stopped.

*c*

_{2}and

*c*

_{3}are plotted along the vertical and horizontal axis, respectively. The iteration points shown in gray are transients, and local minimum C is shown as a large gray point.

*c*

_{2}as function of the number of iterations, including the transients (gray points). After the transients, Figs. 4(a)-(c) show horizontal lines, and each line corresponds to the

*c*

_{2}value for a point in the periodic attractor. As mentioned above, attracting points that have equal values of

*c*

_{2}cannot be distinguished. For example, two horizontal lines overlap each other in Fig. 4(c). Figure 4(d) shows a remarkably complex pattern, corresponding to the transition region between order (period doubling) and chaos. In Fig. 4(e), the set of attracting points forms a chaotic attractor, which is similar to those studied in nonlinear dynamics [22

22. C. Grebogi, E. Ott, and J. A. Yorke, “Chaos, strange attractors, and fractal basin boundaries in non-linear dynamics,” Science **238**, 632–638 (1987). [CrossRef] [PubMed]

## 4. Escaping from a poor local minimum

*p*. We used a grid of 101 × 101 points, where each grid point is iterated 999 times. Note that the basins of minima A, C, D, and E remain compact. However, the basin of minimum B, which has the largest value of the merit function, completely disappears for

*p*= 0.0006. First, for a variation domain of

*p*including the value

*p*= 0.0009, the algorithm approaches a periodic attractor consisting of two points [the white points

*P*

_{1}and

*P*

_{2}in Fig. 6(a)], which are close to the former point B. After a sufficiently large number of iterations

*n*, the succession of each second iteration converges to

*P*

_{1}(the regions that lead to this point after

*n*large and odd are shown in dark blue) or to

*P*

_{2}(light blue).

*p*, the number of attracting points increases until a chaotic attractor is formed [white points in Fig. 6(b)]. The purple region shows the set of starting configurations that are attracted to the chaotic attractor. When the damping is lowered further, the process iterates over the merit function barrier and converges to local minimum A [Fig. 6(c)–(d)]. In chaos research, one commonly encounters situations called ‘crises’ where, after the control parameter passes through a critical value, the chaotic attractor becomes unstable [22

22. C. Grebogi, E. Ott, and J. A. Yorke, “Chaos, strange attractors, and fractal basin boundaries in non-linear dynamics,” Science **238**, 632–638 (1987). [CrossRef] [PubMed]

23. Y.-C. Lai and C. Grebogi, “Converting transient chaos into sustained chaos by feedback control,” Phys. Rev. E **49**, 1094–1098 (1994). [CrossRef]

*p*= 0.000679 to escape from the chaotic behavior. When we increase the number of iterations, the configurations corresponding the the purple points also reach minimum A. When

*p*becomes sufficiently low (

*p*= 0.0006), all starting configurations in the former basin of minimum B converge within 999 iterations to minimum A [Fig. 6(d)].

*c*

_{2}of the last 699 iteration points are plotted as a function of

*p*. The horizontal lines on the left- and right-hand side of Fig. 7 correspond to the

*c*

_{2}values of minima B and A, respectively.

*p*in the (

*c*

_{3},

*c*

_{2})-space (left), and the values of

*c*

_{2}for the iteration points as function of the number of iterations (right). The iterations shown in gray are considered to be initial transients, and local minimum B is shown as a large gray point.

*p*decreases, these six points become stable and the algorithm continues with oscillations between these six points [Fig. 8(b)].

*p*, the iteration points form a chaotic-like set in the variable space [Fig. 8(d)]. After the ‘crisis’, this set of points becomes an unstable chaotic saddle. The algorithm escapes from it and moves to a different region of the variable space [Fig. 8(e)]. The convergence to local minimum A is illustrated by the horizontal line at the top right of Fig. 8(e). (Certain details are different when we choose another configuration in the former basin of minimum B as starting point.)

23. Y.-C. Lai and C. Grebogi, “Converting transient chaos into sustained chaos by feedback control,” Phys. Rev. E **49**, 1094–1098 (1994). [CrossRef]

*p*after the ‘crisis’.

## 5. Instabilities in conventional damped least-squares optimization

**17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

**17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

**17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

**17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

**17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

**17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

23. Y.-C. Lai and C. Grebogi, “Converting transient chaos into sustained chaos by feedback control,” Phys. Rev. E **49**, 1094–1098 (1994). [CrossRef]

## 6. Conclusion

**17**, 314–328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]

## Acknowledgments

## References and links

1. | G. W. Forbes and A. E. Jones, “Towards global optimization with adaptive simulated annealing,” in |

2. | T. G. Kuper and T. I. Harris, “Global optimization for lens design - an emerging technology,” in Lens and optical system design, H. Zuegge, ed., |

3. | M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, “Lens design: Global optimization with Escape Function,” Optical Review (Japan) |

4. | K. E. Moore, “Algorithm for global optimization of optical systems based on genetic competition,” in |

5. | L. W. Jones, S. H. Al-Sakran, and J. R. Koza, “Automated synthesis of both the topology and numerical parameters for seven patented optical lens systems using genetic programming,” in |

6. | J. P. McGuire, “Designing easily manufactured lenses using a global method,” in |

07. | J. R. Rogers, “Using global synthesis to find tolerance-insensitive design forms,” in |

8. | O. Marinescu and F. Bociort, “Network search method in the design of EUV lithographic objectives,” Appl. Opt. |

9. | D. C. Sinclair, “Optical design software,” in |

10. | M. Laikin, |

11. | A. Serebriakov, F. Bociort, and J. Braat, “Finding new local minima by switching merit functions in optical system optimization,” Opt. Eng. |

12. | H. Gross, H. Zügge, M. Peschka, and F. Blechinger, |

13. | D. Shafer, “How to optimize complex lens designs,” Laser Focus World |

14. | D. Shafer, “Global optimization in optical design,” Computers in Physics |

15. | M. van Turnhout and F. Bociort, “Instabilities and fractal basins of attraction in optical system optimization,” Opt. Express |

16. | C. L. Lawson and R. J. Hanson, |

17. | E. Ott, |

18. | H. E. Nusse and J. A. Yorke, “Basins of attraction,” Science |

19. | S. N. Rasband, |

20. | I. Castillo and E. R. Barnes, “Chaotic behavior of the affine scaling algorithm for linear programming,” SIAM J. on Optimization |

21. | B. Davies, “Period Doubling,” in Encyclopedia of Nonlinear Science, A. Scott, ed. (Routledge, New York, 2004). |

22. | C. Grebogi, E. Ott, and J. A. Yorke, “Chaos, strange attractors, and fractal basin boundaries in non-linear dynamics,” Science |

23. | Y.-C. Lai and C. Grebogi, “Converting transient chaos into sustained chaos by feedback control,” Phys. Rev. E |

**OCIS Codes**

(080.2720) Geometric optics : Mathematical methods (general)

(220.2740) Optical design and fabrication : Geometric optical design

(220.3620) Optical design and fabrication : Lens system design

(080.1753) Geometric optics : Computation methods

**ToC Category:**

Optical Design and Fabrication

**History**

Original Manuscript: February 17, 2009

Revised Manuscript: March 24, 2009

Manuscript Accepted: April 1, 2009

Published: April 2, 2009

**Citation**

Maarten van Turnhout and Florian Bociort, "Chaotic behavior in an algorithm to escape from poor local minima in lens design," Opt. Express **17**, 6436-6450 (2009)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-8-6436

Sort: Year | Journal | Reset

### References

- G. W. Forbes and A. E. Jones, "Towards global optimization with adaptive simulated annealing," Proc. SPIE 1334, 144-153 (1991). [CrossRef]
- T. G. Kuper and T. I. Harris, "Global optimization for lens design - an emerging technology," Proc. SPIE 1780,14-28 (1992).
- M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev. 6, 463-470 (1995).
- K. E. Moore, "Algorithm for global optimization of optical systems based on genetic competition," Proc. SPIE 3780, 40-47 (1999). [CrossRef]
- L. W. Jones, S. H. Al-Sakran, and J. R. Koza, "Automated synthesis of both the topology and numerical parameters for seven patented optical lens systems using genetic programming," Proc. SPIE 5874, 587403 (2005). [CrossRef]
- J. P. McGuire, Jr., "Designing easily manufactured lenses using a global method," Proc SPIE 6342, 63420O (2006). [CrossRef]
- J. R. Rogers, "Using global synthesis to find tolerance-insensitive design forms," Proc SPIE 6342, 63420M (2006). [CrossRef]
- O. Marinescu and F. Bociort, "Network search method in the design of EUV lithographic objectives," Appl. Opt. 46, 8385-8393 (2007). [CrossRef] [PubMed]
- D. C. Sinclair, "Optical design software," in Handbook of Optics, Fundamentals, Techniques, and Design, M. Bass, E. W. Van Stryland, D. R. Williams, and Wolfe W. L., eds., 2nd ed., (McGraw-Hill, New York, 1995) Vol. 1, 34.1-34.26.
- M. Laikin, The Method of Lens Design, Lens design, 4th ed. (CRC Press, Boca Raton, FL, 1996).
- A. Serebriakov, F. Bociort, and J. Braat, "Finding new local minima by switching merit functions in optical system optimization," Opt. Eng. 44, 100,501 (2005). [CrossRef]
- H. Gross, H. Zügge, M. Peschka, and F. Blechinger, Principles of optimization, in Handbook of Optical Systems, (Wiley-VCH, Weinheim, 2007) Vol. 3, 291-370.
- D. Shafer, "How to optimize complex lens designs," Laser Focus World 29, 135-138 (1993).
- D. Shafer, "Global optimization in optical design," Comput. Phys. 8, 188-195 (1994).
- M. van Turnhout and F. Bociort, "Instabilities and fractal basins of attraction in optical system optimization," Opt. Express 17, 314-328 (2009). URL http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-1-314. [CrossRef] [PubMed]
- C. L. Lawson and R. J. Hanson, Solving Least Squares Problems (Prentice-Hall, Englewood Cliffs, NJ, 1974).
- E. Ott, Chaos in dynamical systems, 2nd ed. (Cambridge University Press, Cambridge, 2002).
- H. E. Nusse and J. A. Yorke, "Basins of attraction," Science 271, 1376-1380 (1996). [CrossRef]
- S. N. Rasband, Chaotic dynamics of nonlinear systems (Wiley, New York, 1990).
- I. Castillo and E. R. Barnes, "Chaotic behavior of the affine scaling algorithm for linear programming," SIAM J. Optim. 11, 781-795 (2000). [CrossRef]
- B. Davies, "Period Doubling," in Encyclopedia of Nonlinear Science, A. Scott, ed., (Routledge, New York, 2004).
- C. Grebogi, E. Ott, and J. A. Yorke, "Chaos, strange attractors, and fractal basin boundaries in non-linear dynamics," Science 238, 632-638 (1987). [CrossRef] [PubMed]
- Y.-C. Lai and C. Grebogi, "Converting transient chaos into sustained chaos by feedback control," Phys. Rev. E 49, 1094-1098 (1994). [CrossRef]

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.