Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Torczon, V.: On the convergence of the multidirectional search algorithm. SIAM J. Optim. 1, 123–145 (1991)
Torczon, V.: On the convergence of pattern search algorithms. SIAM J. Optim. 7, 1–25 (1997)
Lewis, R.M., Torczon, V.: Pattern search algorithms for bound constrained minimization. SIAM J. Optim. 9, 1082–1099 (1999)
Lewis, R.M., Torczon, V.: Pattern search methods for linearly constrained minimization. SIAM J. Optim. 10, 917–941 (2000)
Abramson, M.A., Audet, C., Dennis, J.E. Jr.: Generalized pattern searches with derivative information. Math. Program. 100B, 3–25 (2004)
Audet, C.: Convergence results for generalized pattern search algorithms are tight. Optim. Eng. 5, 101–122 (2004)
Audet, C., Dennis, J.E. Jr.: Analysis of generalized pattern searches. SIAM J. Optim. 13, 889–903 (2003)
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)
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)
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)
Barrodale, I., Roberts, F.D.K.: An improved algorithm for discrete L 1–approximation. SIAM J. Numer. Anal. 10, 839–848 (1973)
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)
Coleman, T.F., Li, Y.: A globally and quadratically convergent affine scaling method for linear L 1 problems. Math. Program. 56, 189–222 (1992)
Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
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)
Optimization Toolbox User’s guide, Version 3. The Mathworks, Natick (2004)
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)
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)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by G. Di Pillo.
This work was supported by M.U.R.S.T., Rome, Italy.
Rights and permissions
About this article
Cite this article
Bogani, C., Gasparo, M.G. & Papini, A. Pattern Search Method for Discrete L 1–Approximation. J Optim Theory Appl 134, 47–59 (2007). https://doi.org/10.1007/s10957-007-9204-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-007-9204-2