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

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. G. W. Forbes and A. E. Jones, "Towards global optimization with adaptive simulated annealing," Proc. SPIE 1334, 144-153 (1991).
    [CrossRef]
  2. T. G. Kuper and T. I. Harris, "Global optimization for lens design - an emerging technology," Proc. SPIE 1780,14-28 (1992).
  3. M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev.  6, 463-470 (1995).
  4. K. E. Moore, "Algorithm for global optimization of optical systems based on genetic competition," Proc. SPIE 3780, 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," Proc. SPIE 5874, 587403 (2005).
    [CrossRef]
  6. J. P. McGuire, Jr., "Designing easily manufactured lenses using a global method," Proc SPIE 6342, 63420O (2006).
    [CrossRef]
  7. J. R. Rogers, "Using global synthesis to find tolerance-insensitive design forms," Proc SPIE 6342, 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]
  9. 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.
  10. M. Laikin, The Method of Lens Design, Lens design, 4th ed. (CRC Press, Boca Raton, FL, 1996).
  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]
  12. 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.
  13. D. Shafer, "How to optimize complex lens designs," Laser Focus World 29, 135-138 (1993).
  14. D. Shafer, "Global optimization in optical design," Comput. Phys. 8, 188-195 (1994).
  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]
  16. C. L. Lawson and R. J. Hanson, Solving Least Squares Problems (Prentice-Hall, Englewood Cliffs, NJ, 1974).
  17. E. Ott, Chaos in dynamical systems, 2nd ed. (Cambridge University Press, Cambridge, 2002).
  18. H. E. Nusse and J. A. Yorke, "Basins of attraction," Science 271, 1376-1380 (1996).
    [CrossRef]
  19. S. N. Rasband, Chaotic dynamics of nonlinear systems (Wiley, New York, 1990).
  20. I. Castillo and E. R. Barnes, "Chaotic behavior of the affine scaling algorithm for linear programming," SIAM J. Optim. 11, 781-795 (2000).
    [CrossRef]
  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 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]

2007

2006

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]

2005

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]

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]

2000

I. Castillo and E. R. Barnes, "Chaotic behavior of the affine scaling algorithm for linear programming," SIAM J. Optim. 11, 781-795 (2000).
[CrossRef]

1999

K. E. Moore, "Algorithm for global optimization of optical systems based on genetic competition," Proc. SPIE 3780, 40-47 (1999).
[CrossRef]

1996

H. E. Nusse and J. A. Yorke, "Basins of attraction," Science 271, 1376-1380 (1996).
[CrossRef]

1995

M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev.  6, 463-470 (1995).

1994

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

D. Shafer, "Global optimization in optical design," Comput. Phys. 8, 188-195 (1994).

1993

D. Shafer, "How to optimize complex lens designs," Laser Focus World 29, 135-138 (1993).

1992

T. G. Kuper and T. I. Harris, "Global optimization for lens design - an emerging technology," Proc. SPIE 1780,14-28 (1992).

1991

G. W. Forbes and A. E. Jones, "Towards global optimization with adaptive simulated annealing," Proc. SPIE 1334, 144-153 (1991).
[CrossRef]

1987

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]

Al-Sakran, S. H.

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]

Barnes, E. R.

I. Castillo and E. R. Barnes, "Chaotic behavior of the affine scaling algorithm for linear programming," SIAM J. Optim. 11, 781-795 (2000).
[CrossRef]

Bociort, F.

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

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]

Braat, J.

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]

Castillo, I.

I. Castillo and E. R. Barnes, "Chaotic behavior of the affine scaling algorithm for linear programming," SIAM J. Optim. 11, 781-795 (2000).
[CrossRef]

Forbes, G. W.

G. W. Forbes and A. E. Jones, "Towards global optimization with adaptive simulated annealing," Proc. SPIE 1334, 144-153 (1991).
[CrossRef]

Grebogi, C.

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

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]

Harris, T. I.

T. G. Kuper and T. I. Harris, "Global optimization for lens design - an emerging technology," Proc. SPIE 1780,14-28 (1992).

Hiraga, K.

M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev.  6, 463-470 (1995).

Ishikawa, J.

M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev.  6, 463-470 (1995).

Isshiki, M.

M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev.  6, 463-470 (1995).

Jones, A. E.

G. W. Forbes and A. E. Jones, "Towards global optimization with adaptive simulated annealing," Proc. SPIE 1334, 144-153 (1991).
[CrossRef]

Jones, L. W.

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]

Koza, J. R.

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]

Kuper, T. G.

T. G. Kuper and T. I. Harris, "Global optimization for lens design - an emerging technology," Proc. SPIE 1780,14-28 (1992).

Lai, Y.-C.

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

Marinescu, O.

McGuire, J. P.

J. P. McGuire, Jr., "Designing easily manufactured lenses using a global method," Proc SPIE 6342, 63420O (2006).
[CrossRef]

Moore, K. E.

K. E. Moore, "Algorithm for global optimization of optical systems based on genetic competition," Proc. SPIE 3780, 40-47 (1999).
[CrossRef]

Nakadate, S.

M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev.  6, 463-470 (1995).

Nusse, H. E.

H. E. Nusse and J. A. Yorke, "Basins of attraction," Science 271, 1376-1380 (1996).
[CrossRef]

Ono, H.

M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev.  6, 463-470 (1995).

Ott, E.

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]

Rogers, J. R.

J. R. Rogers, "Using global synthesis to find tolerance-insensitive design forms," Proc SPIE 6342, 63420M (2006).
[CrossRef]

Serebriakov, A.

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]

Shafer, D.

D. Shafer, "Global optimization in optical design," Comput. Phys. 8, 188-195 (1994).

D. Shafer, "How to optimize complex lens designs," Laser Focus World 29, 135-138 (1993).

Yorke, J. A.

H. E. Nusse and J. A. Yorke, "Basins of attraction," Science 271, 1376-1380 (1996).
[CrossRef]

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]

Appl. Opt.

Comput. Phys.

D. Shafer, "Global optimization in optical design," Comput. Phys. 8, 188-195 (1994).

Laser Focus World

D. Shafer, "How to optimize complex lens designs," Laser Focus World 29, 135-138 (1993).

Opt. Eng.

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]

Opt. Rev.

M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, "Lens design: Global optimization with Escape Function," Opt. Rev.  6, 463-470 (1995).

Phys. Rev. E

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

Proc SPIE

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]

Proc. SPIE

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]

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).

Science

H. E. Nusse and J. A. Yorke, "Basins of attraction," Science 271, 1376-1380 (1996).
[CrossRef]

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]

SIAM J. Optim.

I. Castillo and E. R. Barnes, "Chaotic behavior of the affine scaling algorithm for linear programming," SIAM J. Optim. 11, 781-795 (2000).
[CrossRef]

Other

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

S. N. Rasband, Chaotic dynamics of nonlinear systems (Wiley, New York, 1990).

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.

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).

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).

Supplementary Material (1)

» Media 1: AVI (87 KB)     

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (10)

Fig. 1.
Fig. 1.

Five local minima for a simple two-dimensional monochromatic doublet optimization problem. The control of edge thickness violation was disabled in order to eliminate the constraints from the list of possible causes of the peculiar behavior described in what follows.

Fig. 2.
Fig. 2.

Basins of attraction for the five local minima in Fig. 1, obtained with damping parameter p = 0.002 on a grid of 101 × 101 points. Each grid point is iterated 999 times. The starting point ‘S’ will be used in Sec. 4.

Fig. 3.
Fig. 3.

Period doubling route to chaos. Curvature c 3 of the points in the asymptotic regime for a starting configuration in the basin of doublet local minimum C (see Fig. 2) is shown as function of the damping parameter p.

Fig. 4.
Fig. 4.

Figures on the left: Iteration trajectories in the two-dimensional variable space (c 3,c 2) of a monochromatic doublet for five different values of the damping parameter p. The starting configuration is in the former basin of local minimum C (see Fig. 2). The large gray point corresponds to local minimum C (obtained with sufficient damping), and the iterations shown in gray are considered as initial transients. Figures on the right: The evolution of curvature c 2 as function of the number of iterations. (a) p = 0.0001, (b) p = 0.00009, (c) p = 0.0000854, (d) p = 0.0000833, (e) p = 0.0000777.

Fig. 5.
Fig. 5.

Merit function (MF) values (in relative units) for the points shown in Fig. 3.

Fig. 6.
Fig. 6.

Basins of attraction obtained for different values of the damping parameter p on a grid of 101 × 101 points. Each grid point is iterated 999 times. (a) p = 0.0009, (b) p = 0.00075, (c) p = 0.000679, and (d) p = 0.0006. The black lines starting close to point O in Figs. 6(b) and (c) will be explained in Sec. 5.

Fig. 7.
Fig. 7.

Attracting points for the starting configuration S in the basin of local minimum B (see Fig. 2). The first 300 iterations have been discarded. Curvature c 2 of the iterations between 301 and 999 has been plotted as function of p.

Fig. 8.
Fig. 8.

Figures on the left: Iteration trajectories in the two-dimensional variable space (c 3,c 2) of a monochromatic doublet for five different values of the damping parameter p. The starting configuration is point S in the former basin of local minimum B (see Fig. 2). The large gray point corresponds to local minimum B (obtained with sufficient damping), and the iterations shown in gray are considered as initial transients. Figures on the right: The evolution of curvature c 2 as function of the number of iterations. (a) p = 0.000784, (b) p = 0.000776, (c) p = 0.000768, (d) p = 0.000730, (e) p = 0.000679.

Fig. 9.
Fig. 9.

Merit function (MF) values (in relative units) for the points shown in Fig. 7.

Fig. 10.
Fig. 10.

(Media 1). Iteration history obtained with CODE V data of a set of starting points that are very close to each other. The merit function equimagnitude contours (i.e. the contours along which the merit function remains constant) are shown in gray, and the history of earlier trajectories is shown in green.

Equations (3)

Equations on this page are rendered with MathJax. Learn more.

( J λ k I ) X k = f ,
λ k = p S 1 10 ( k 1 ) / a ,
δ = p 2 p 1 p 3 p 2 4.78

Metrics