Skip to main content
SpringerLink
Log in

Worst case complexity of direct search under convexity

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper we prove that the broad class of direct-search methods of directional type, based on imposing sufficient decrease to accept new iterates, exhibits the same worst case complexity bound and global rate of the gradient method for the unconstrained minimization of a convex and smooth function. More precisely, it will be shown that the number of iterations needed to reduce the norm of the gradient of the objective function below a certain threshold is at most proportional to the inverse of the threshold. It will be also shown that the absolute error in the function values decay at a sublinear rate proportional to the inverse of the iteration counter. In addition, we prove that the sequence of absolute errors of function values and iterates converges r-linearly in the strongly convex case.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Cartis, C., Gould, N.I.M., Toint, P.L.: On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization. SIAM J. Optim. 20, 2833–2852 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  2. Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part II. Math. Program. 130, 295–319 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  3. Cartis, C., Gould, N.I.M., Toint, P.L.: On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization. SIAM J. Optim. 22, 66–86 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  4. Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2009)

    Book  Google Scholar 

  5. Dolan, E.D., Lewis, R.M., Torczon, V.: On the local convergence of pattern search. SIAM J. Optim. 14, 567–583 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  6. Duchi, J.C., Jordan, M.I., Wainwright, M.J., Wibisono, A.: Optimal rates for zero-order convex optimization: the power of two function evaluations (2014). arXiv:1312.2139v2

  7. Garmanjani, R., Vicente, L.N.: Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization. IMA J. Numer. Anal. 33, 1008–1028 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  8. Gould, N.I.M., Orban, D., Toint, P.L.: CUTEr, a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29, 373–394 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  9. Gratton, S., Sartenaer, A., Toint, P.L.: Recursive trust-region methods for multiscale nonlinear optimization. SIAM J. Optim. 19, 414–444 (2008)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  11. Nesterov, Y.: Introductory Lectures on Convex Optimization. Kluwer Academic Publishers, Dordrecht (2004)

    Book  MATH  Google Scholar 

  12. Nesterov, Y.: Random gradient-free minimization of convex functions. Technical Report 2011/1, CORE (2011)

  13. Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22, 341–362 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  14. Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton’s method and its global performance. Math. Program. 108, 177–205 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  15. Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, Berlin (2006)

    MATH  Google Scholar 

  16. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    Book  MATH  Google Scholar 

  17. Vicente, L.N.: Worst case complexity of direct search. EURO J. Comput. Optim. 1, 143–153 (2013)

    Article  MATH  Google Scholar 

Download references

Acknowledgments

We would like to thank one anonymous referee for the numerous insightful observations which led to a much improved version of the paper. We thank also Zaikun Zhang for several interesting discussions.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Coimbra, 3001-501, Coimbra, Portugal

    M. Dodangeh

  2. CMUC, Department of Mathematics, University of Coimbra, 3001-501, Coimbra, Portugal

    L. N. Vicente

Authors
  1. M. Dodangeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. L. N. Vicente
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to L. N. Vicente.

Additional information

M. Dodangeh: Support for this author was provided by FCT under the scholarship SFRH/BD/51168/2010.

L. N. Vicente: Support for this research was provided by FCT under Grants PTDC/MAT/116736/2010 and PEst-C/MAT/UI0324/2011.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dodangeh, M., Vicente, L.N. Worst case complexity of direct search under convexity. Math. Program. 155, 307–332 (2016). https://doi.org/10.1007/s10107-014-0847-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-014-0847-0

Keywords

Mathematics Subject Classification

Search

Navigation