×

zbMATH — the first resource for mathematics

Pattern search method for discrete \(L_{1}\)-approximation. (English) Zbl 1129.49043
Summary: We propose a pattern search method to solve a classical nonsmooth optimization problem. In a deep analogy with pattern search methods for linear constrained optimization, the set of search directions at each iteration is defined in such a way that it conforms to the local geometry of the set of points of nondifferentiability near the current iterate. This is crucial to ensure convergence. The approach presented here can be extended to wider classes of nonsmooth optimization problems. Numerical experiments seem to be encouraging.

MSC:
49N90 Applications of optimal control and differential games
68T10 Pattern recognition, speech recognition
90C30 Nonlinear programming
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Torczon, V.: On the convergence of the multidirectional search algorithm. SIAM J. Optim. 1, 123–145 (1991) · Zbl 0752.90076 · doi:10.1137/0801010
[2] Torczon, V.: On the convergence of pattern search algorithms. SIAM J. Optim. 7, 1–25 (1997) · Zbl 0884.65053 · doi:10.1137/S1052623493250780
[3] Lewis, R.M., Torczon, V.: Pattern search algorithms for bound constrained minimization. SIAM J. Optim. 9, 1082–1099 (1999) · Zbl 1031.90047 · doi:10.1137/S1052623496300507
[4] Lewis, R.M., Torczon, V.: Pattern search methods for linearly constrained minimization. SIAM J. Optim. 10, 917–941 (2000) · Zbl 1031.90048 · doi:10.1137/S1052623497331373
[5] Abramson, M.A., Audet, C., Dennis, J.E. Jr.: Generalized pattern searches with derivative information. Math. Program. 100B, 3–25 (2004) · Zbl 1146.90524
[6] Audet, C.: Convergence results for generalized pattern search algorithms are tight. Optim. Eng. 5, 101–122 (2004) · Zbl 1085.90053 · doi:10.1023/B:OPTE.0000033370.66768.a9
[7] Audet, C., Dennis, J.E. Jr.: Analysis of generalized pattern searches. SIAM J. Optim. 13, 889–903 (2003) · Zbl 1053.90118 · doi:10.1137/S1052623400378742
[8] Audet, C., Dennis, J.E. Jr.: Mesh adaptive direct search algorithms for constrained optimization. Technical Report G-2004-04, Les Cahiers du GERAD, MontrĂ©al, Quebec, Canada (2004) · Zbl 1166.90366
[9] Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45, 385–482 (2003) · Zbl 1059.90146 · doi:10.1137/S003614450242889
[10] Lewis, R.M., Torczon, V.: Rank ordering and positive basis in pattern search algorithms. Technical Report TR-96-71, ICASE, NASA Langley Research Center (1996)
[11] Barrodale, I., Roberts, F.D.K.: An improved algorithm for discrete L 1–approximation. SIAM J. Numer. Anal. 10, 839–848 (1973) · Zbl 0266.65016 · doi:10.1137/0710069
[12] Bartels, R.H., Conn, A.R., Sinclair, J.W.: Minimization techniques for piecewise differentiable functions: The L 1 solution to an overdetermined linear system. SIAM J. Numer. Anal. 15, 224–241 (1978) · Zbl 0376.65018 · doi:10.1137/0715015
[13] Coleman, T.F., Li, Y.: A globally and quadratically convergent affine scaling method for linear L 1 problems. Math. Program. 56, 189–222 (1992) · Zbl 0760.90069 · doi:10.1007/BF01580899
[14] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[15] Abramson, M.A., Brezhneva, O.A., Dennis, J.E. Jr.: Pattern search methods in the presence of degeneracy. Technical Report TR03-09, Rice University, Department of Computational and Applied Mathematics (2005)
[16] Optimization Toolbox User’s guide, Version 3. The Mathworks, Natick (2004)
[17] Byrd, R.H., Gould, N.I.M., Nocedal, J., Waltz, R.A.: An algorithm for nonlinear optimization using linear programming and equality constrained subproblems. Math. Program. 100B, 27–48 (2004) · Zbl 1146.90513
[18] Duff, I.S., Nocedal, J., Reid, J.K.: The use of linear programming for the solution of sparse sets of nonlinear equations. SIAM J. Sci. Stat. Comput. 8, 99–108 (1987) · Zbl 0636.65053 · doi:10.1137/0908024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.