A convergence analysis of the method of codifferential descent View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-12

AUTHORS

M. V. Dolgopolik

ABSTRACT

This paper is devoted to a detailed convergence analysis of the method of codifferential descent (MCD) developed by professor V.F. Demyanov for solving a large class of nonsmooth nonconvex optimization problems. We propose a generalization of the MCD that is more suitable for applications than the original method, and that utilizes only a part of a codifferential on every iteration, which allows one to reduce the overall complexity of the method. With the use of some general results on uniformly codifferentiable functions obtained in this paper, we prove the global convergence of the generalized MCD in the infinite dimensional case. Also, we propose and analyse a quadratic regularization of the MCD, which is the first general method for minimizing a codifferentiable function over a convex set. Apart from convergence analysis, we also discuss the robustness of the MCD with respect to computational errors, possible step size rules, and a choice of parameters of the algorithm. In the end of the paper we estimate the rate of convergence of the MCD for a class of nonsmooth nonconvex functions that arise, in particular, in cluster analysis. We prove that under some general assumptions the method converges with linear rate, and it convergence quadratically, provided a certain first order sufficient optimality condition holds true. More... »

PAGES

1-35

References to SciGraph publications

  • 2018-12. Application of the hypodifferential descent method to the problem of constructing an optimal control in OPTIMIZATION LETTERS
  • 2013. Calculus Without Derivatives in NONE
  • 2012-12. Inhomogeneous convex approximations of nonsmooth functions in RUSSIAN MATHEMATICS
  • 2003-01. A Solution Method for a Special Class of Nondifferentiable Unconstrained Optimization Problems in COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
  • 1993. Convex Analysis and Minimization Algorithms I, Fundamentals in NONE
  • 2011-03. Codifferential calculus in normed spaces in JOURNAL OF MATHEMATICAL SCIENCES
  • 2007-01. Globally convergent limited memory bundle method for large-scale nonsmooth optimization in MATHEMATICAL PROGRAMMING
  • 1988. Continuous Generalized Gradients for Nonsmooth Functions in OPTIMIZATION, PARALLEL PROCESSING AND APPLICATIONS
  • 2002-05. A method of truncated codifferential with application to some problems of cluster analysis in JOURNAL OF GLOBAL OPTIMIZATION
  • 1992. Does the Special Choice of Quasidifferentials Influence Necessary Minimum Conditions? in ADVANCES IN OPTIMIZATION
  • 1972-02. On the rate of convergence of certain methods of centers in MATHEMATICAL PROGRAMMING
  • 2013-09. A derivative-free approximate gradient sampling algorithm for finite minimax problems in COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
  • 2011-05. Codifferential method for minimizing nonsmooth DC functions in JOURNAL OF GLOBAL OPTIMIZATION
  • 1996. Quasidifferentiability and Nonsmooth Modelling in Mechanics, Engineering and Economics in NONE
  • 2002. Pairs of Compact Convex Sets, Fractional Arithmetic with Convex Sets in NONE
  • 2000. Numerical Methods for Minimizing Quasidifferentiable Functions: A Survey and Comparison in QUASIDIFFERENTIABILITY AND RELATED TOPICS
  • 1989. Smoothness of Nonsmooth Functions in NONSMOOTH OPTIMIZATION AND RELATED TOPICS
  • 1995-07. Exact barrier function methods for Lipschitz programs in APPLIED MATHEMATICS & OPTIMIZATION
  • 2000. Continuous Approximations, Codifferentiable Functions and Minimization Methods in QUASIDIFFERENTIABILITY AND RELATED TOPICS
  • 2002-12. On the Convergence of Descent Algorithms in COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
  • 2008-05. Discrete Gradient Method: Derivative-Free Method for Nonsmooth Optimization in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 2013-10. Nonsmooth optimization via quasi-Newton methods in MATHEMATICAL PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10589-018-0024-0

    DOI

    http://dx.doi.org/10.1007/s10589-018-0024-0

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1105830438


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institute of Problems of Mechanical Engineering", 
              "id": "https://www.grid.ac/institutes/grid.462405.1", 
              "name": [
                "Saint Petersburg State University, Saint Petersburg, Russia", 
                "Institute of Problems of Mechanical Engineering, Russian Academy of Sciences, Saint Petersburg, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dolgopolik", 
            "givenName": "M. V.", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1001774846", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-4113-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001774846", 
              "https://doi.org/10.1007/978-1-4615-4113-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-4113-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001774846", 
              "https://doi.org/10.1007/978-1-4615-4113-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01584544", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001866556", 
              "https://doi.org/10.1007/bf01584544"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01584544", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001866556", 
              "https://doi.org/10.1007/bf01584544"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10556780290027828", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002327785"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10589-013-9547-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005050363", 
              "https://doi.org/10.1007/s10589-013-9547-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10556788.2010.526116", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006075580"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.3103/s1066369x12120043", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007209325", 
              "https://doi.org/10.3103/s1066369x12120043"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-006-0728-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009500410", 
              "https://doi.org/10.1007/s10107-006-0728-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-006-0728-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009500410", 
              "https://doi.org/10.1007/s10107-006-0728-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-51682-5_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010960085", 
              "https://doi.org/10.1007/978-3-642-51682-5_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-46631-1_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013935206", 
              "https://doi.org/10.1007/978-3-642-46631-1_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0041-5553(81)90031-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015483810"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-6019-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018434308", 
              "https://doi.org/10.1007/978-1-4757-6019-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331930902943483", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019123081"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331938608843131", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019756461"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01189901", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020617396", 
              "https://doi.org/10.1007/bf01189901"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.cam.2013.08.010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021877069"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-012-0514-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022763272", 
              "https://doi.org/10.1007/s10107-012-0514-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331934.2013.840625", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024670082"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1026756433", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-02796-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026756433", 
              "https://doi.org/10.1007/978-3-662-02796-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-02796-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026756433", 
              "https://doi.org/10.1007/978-3-662-02796-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10556780290027837", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027345027"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-3137-8_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027651812", 
              "https://doi.org/10.1007/978-1-4757-3137-8_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1029389749", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-015-9920-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029389749", 
              "https://doi.org/10.1007/978-94-015-9920-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-015-9920-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029389749", 
              "https://doi.org/10.1007/978-94-015-9920-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1021854116784", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029894598", 
              "https://doi.org/10.1023/a:1021854116784"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1020570126636", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030732939", 
              "https://doi.org/10.1023/a:1020570126636"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-3137-8_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032487502", 
              "https://doi.org/10.1007/978-1-4757-3137-8_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331934.2013.869811", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032608780"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10898-010-9569-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035348266", 
              "https://doi.org/10.1007/s10898-010-9569-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331939108843708", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036017163"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10957-007-9335-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036150122", 
              "https://doi.org/10.1007/s10957-007-9335-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331939108843697", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036629616"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10556788.2012.714781", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036718976"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10958-011-0259-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036759296", 
              "https://doi.org/10.1007/s10958-011-0259-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331934.2010.534166", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046130635"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1014075113874", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048199048", 
              "https://doi.org/10.1023/a:1014075113874"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4614-4538-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048511240", 
              "https://doi.org/10.1007/978-1-4614-4538-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4614-4538-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048511240", 
              "https://doi.org/10.1007/978-1-4614-4538-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331930500096171", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050448979"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331930500096171", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050448979"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/01630563.2014.922097", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050598754"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1051/cocv/2014010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056951998"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/030601296", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842754"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/090748408", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062855965"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/090754595", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062856181"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10556788.2017.1378652", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1092078264"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11590-017-1222-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093058938", 
              "https://doi.org/10.1007/s11590-017-1222-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9780898718768", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098556221"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-12", 
        "datePublishedReg": "2018-12-01", 
        "description": "This paper is devoted to a detailed convergence analysis of the method of codifferential descent (MCD) developed by professor V.F. Demyanov for solving a large class of nonsmooth nonconvex optimization problems. We propose a generalization of the MCD that is more suitable for applications than the original method, and that utilizes only a part of a codifferential on every iteration, which allows one to reduce the overall complexity of the method. With the use of some general results on uniformly codifferentiable functions obtained in this paper, we prove the global convergence of the generalized MCD in the infinite dimensional case. Also, we propose and analyse a quadratic regularization of the MCD, which is the first general method for minimizing a codifferentiable function over a convex set. Apart from convergence analysis, we also discuss the robustness of the MCD with respect to computational errors, possible step size rules, and a choice of parameters of the algorithm. In the end of the paper we estimate the rate of convergence of the MCD for a class of nonsmooth nonconvex functions that arise, in particular, in cluster analysis. We prove that under some general assumptions the method converges with linear rate, and it convergence quadratically, provided a certain first order sufficient optimality condition holds true.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10589-018-0024-0", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1042206", 
            "issn": [
              "0926-6003", 
              "1573-2894"
            ], 
            "name": "Computational Optimization and Applications", 
            "type": "Periodical"
          }
        ], 
        "name": "A convergence analysis of the method of codifferential descent", 
        "pagination": "1-35", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "db33a4ad86c56ddac322a16dc18fd7ec9edd43aa5c68adfd46325ede3e96db6f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10589-018-0024-0"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1105830438"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10589-018-0024-0", 
          "https://app.dimensions.ai/details/publication/pub.1105830438"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T01:01", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8697_00000485.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s10589-018-0024-0"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10589-018-0024-0'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10589-018-0024-0'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10589-018-0024-0'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10589-018-0024-0'


     

    This table displays all metadata directly associated to this object as RDF triples.

    212 TRIPLES      21 PREDICATES      71 URIs      17 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10589-018-0024-0 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author Nb629f3d91cfb435088de921be10451b8
    4 schema:citation sg:pub.10.1007/978-1-4614-4538-8
    5 sg:pub.10.1007/978-1-4615-4113-4
    6 sg:pub.10.1007/978-1-4757-3137-8_14
    7 sg:pub.10.1007/978-1-4757-3137-8_2
    8 sg:pub.10.1007/978-1-4757-6019-4_6
    9 sg:pub.10.1007/978-3-642-46631-1_3
    10 sg:pub.10.1007/978-3-642-51682-5_17
    11 sg:pub.10.1007/978-3-662-02796-7
    12 sg:pub.10.1007/978-94-015-9920-7
    13 sg:pub.10.1007/bf01189901
    14 sg:pub.10.1007/bf01584544
    15 sg:pub.10.1007/s10107-006-0728-2
    16 sg:pub.10.1007/s10107-012-0514-2
    17 sg:pub.10.1007/s10589-013-9547-6
    18 sg:pub.10.1007/s10898-010-9569-x
    19 sg:pub.10.1007/s10957-007-9335-5
    20 sg:pub.10.1007/s10958-011-0259-0
    21 sg:pub.10.1007/s11590-017-1222-x
    22 sg:pub.10.1023/a:1014075113874
    23 sg:pub.10.1023/a:1020570126636
    24 sg:pub.10.1023/a:1021854116784
    25 sg:pub.10.3103/s1066369x12120043
    26 https://app.dimensions.ai/details/publication/pub.1001774846
    27 https://app.dimensions.ai/details/publication/pub.1026756433
    28 https://app.dimensions.ai/details/publication/pub.1029389749
    29 https://doi.org/10.1016/0041-5553(81)90031-8
    30 https://doi.org/10.1016/j.cam.2013.08.010
    31 https://doi.org/10.1051/cocv/2014010
    32 https://doi.org/10.1080/01630563.2014.922097
    33 https://doi.org/10.1080/02331930500096171
    34 https://doi.org/10.1080/02331930902943483
    35 https://doi.org/10.1080/02331934.2010.534166
    36 https://doi.org/10.1080/02331934.2013.840625
    37 https://doi.org/10.1080/02331934.2013.869811
    38 https://doi.org/10.1080/02331938608843131
    39 https://doi.org/10.1080/02331939108843697
    40 https://doi.org/10.1080/02331939108843708
    41 https://doi.org/10.1080/10556780290027828
    42 https://doi.org/10.1080/10556780290027837
    43 https://doi.org/10.1080/10556788.2010.526116
    44 https://doi.org/10.1080/10556788.2012.714781
    45 https://doi.org/10.1080/10556788.2017.1378652
    46 https://doi.org/10.1137/030601296
    47 https://doi.org/10.1137/090748408
    48 https://doi.org/10.1137/090754595
    49 https://doi.org/10.1137/1.9780898718768
    50 schema:datePublished 2018-12
    51 schema:datePublishedReg 2018-12-01
    52 schema:description This paper is devoted to a detailed convergence analysis of the method of codifferential descent (MCD) developed by professor V.F. Demyanov for solving a large class of nonsmooth nonconvex optimization problems. We propose a generalization of the MCD that is more suitable for applications than the original method, and that utilizes only a part of a codifferential on every iteration, which allows one to reduce the overall complexity of the method. With the use of some general results on uniformly codifferentiable functions obtained in this paper, we prove the global convergence of the generalized MCD in the infinite dimensional case. Also, we propose and analyse a quadratic regularization of the MCD, which is the first general method for minimizing a codifferentiable function over a convex set. Apart from convergence analysis, we also discuss the robustness of the MCD with respect to computational errors, possible step size rules, and a choice of parameters of the algorithm. In the end of the paper we estimate the rate of convergence of the MCD for a class of nonsmooth nonconvex functions that arise, in particular, in cluster analysis. We prove that under some general assumptions the method converges with linear rate, and it convergence quadratically, provided a certain first order sufficient optimality condition holds true.
    53 schema:genre research_article
    54 schema:inLanguage en
    55 schema:isAccessibleForFree true
    56 schema:isPartOf sg:journal.1042206
    57 schema:name A convergence analysis of the method of codifferential descent
    58 schema:pagination 1-35
    59 schema:productId N3c9ec8b8220a470480fb88e65942b814
    60 N84440b08735e4e2aafdf6496c33780a6
    61 Nbad1e7ef22a24daba407884148cfe3d7
    62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105830438
    63 https://doi.org/10.1007/s10589-018-0024-0
    64 schema:sdDatePublished 2019-04-11T01:01
    65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    66 schema:sdPublisher N928367d9003b47a4a6ed1701571ceffa
    67 schema:url http://link.springer.com/10.1007/s10589-018-0024-0
    68 sgo:license sg:explorer/license/
    69 sgo:sdDataset articles
    70 rdf:type schema:ScholarlyArticle
    71 N3c9ec8b8220a470480fb88e65942b814 schema:name dimensions_id
    72 schema:value pub.1105830438
    73 rdf:type schema:PropertyValue
    74 N68c41944cddd4aa492fc1d1f02bbbf05 schema:affiliation https://www.grid.ac/institutes/grid.462405.1
    75 schema:familyName Dolgopolik
    76 schema:givenName M. V.
    77 rdf:type schema:Person
    78 N84440b08735e4e2aafdf6496c33780a6 schema:name doi
    79 schema:value 10.1007/s10589-018-0024-0
    80 rdf:type schema:PropertyValue
    81 N928367d9003b47a4a6ed1701571ceffa schema:name Springer Nature - SN SciGraph project
    82 rdf:type schema:Organization
    83 Nb629f3d91cfb435088de921be10451b8 rdf:first N68c41944cddd4aa492fc1d1f02bbbf05
    84 rdf:rest rdf:nil
    85 Nbad1e7ef22a24daba407884148cfe3d7 schema:name readcube_id
    86 schema:value db33a4ad86c56ddac322a16dc18fd7ec9edd43aa5c68adfd46325ede3e96db6f
    87 rdf:type schema:PropertyValue
    88 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Mathematical Sciences
    90 rdf:type schema:DefinedTerm
    91 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Numerical and Computational Mathematics
    93 rdf:type schema:DefinedTerm
    94 sg:journal.1042206 schema:issn 0926-6003
    95 1573-2894
    96 schema:name Computational Optimization and Applications
    97 rdf:type schema:Periodical
    98 sg:pub.10.1007/978-1-4614-4538-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048511240
    99 https://doi.org/10.1007/978-1-4614-4538-8
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/978-1-4615-4113-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001774846
    102 https://doi.org/10.1007/978-1-4615-4113-4
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/978-1-4757-3137-8_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027651812
    105 https://doi.org/10.1007/978-1-4757-3137-8_14
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/978-1-4757-3137-8_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032487502
    108 https://doi.org/10.1007/978-1-4757-3137-8_2
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/978-1-4757-6019-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018434308
    111 https://doi.org/10.1007/978-1-4757-6019-4_6
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/978-3-642-46631-1_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013935206
    114 https://doi.org/10.1007/978-3-642-46631-1_3
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/978-3-642-51682-5_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010960085
    117 https://doi.org/10.1007/978-3-642-51682-5_17
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/978-3-662-02796-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026756433
    120 https://doi.org/10.1007/978-3-662-02796-7
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-94-015-9920-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029389749
    123 https://doi.org/10.1007/978-94-015-9920-7
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/bf01189901 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020617396
    126 https://doi.org/10.1007/bf01189901
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/bf01584544 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001866556
    129 https://doi.org/10.1007/bf01584544
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/s10107-006-0728-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009500410
    132 https://doi.org/10.1007/s10107-006-0728-2
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/s10107-012-0514-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022763272
    135 https://doi.org/10.1007/s10107-012-0514-2
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/s10589-013-9547-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005050363
    138 https://doi.org/10.1007/s10589-013-9547-6
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/s10898-010-9569-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1035348266
    141 https://doi.org/10.1007/s10898-010-9569-x
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/s10957-007-9335-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036150122
    144 https://doi.org/10.1007/s10957-007-9335-5
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/s10958-011-0259-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036759296
    147 https://doi.org/10.1007/s10958-011-0259-0
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/s11590-017-1222-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1093058938
    150 https://doi.org/10.1007/s11590-017-1222-x
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1023/a:1014075113874 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048199048
    153 https://doi.org/10.1023/a:1014075113874
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1023/a:1020570126636 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030732939
    156 https://doi.org/10.1023/a:1020570126636
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1023/a:1021854116784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029894598
    159 https://doi.org/10.1023/a:1021854116784
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.3103/s1066369x12120043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007209325
    162 https://doi.org/10.3103/s1066369x12120043
    163 rdf:type schema:CreativeWork
    164 https://app.dimensions.ai/details/publication/pub.1001774846 schema:CreativeWork
    165 https://app.dimensions.ai/details/publication/pub.1026756433 schema:CreativeWork
    166 https://app.dimensions.ai/details/publication/pub.1029389749 schema:CreativeWork
    167 https://doi.org/10.1016/0041-5553(81)90031-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015483810
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1016/j.cam.2013.08.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021877069
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1051/cocv/2014010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056951998
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1080/01630563.2014.922097 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050598754
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1080/02331930500096171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050448979
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1080/02331930902943483 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019123081
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1080/02331934.2010.534166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046130635
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1080/02331934.2013.840625 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024670082
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1080/02331934.2013.869811 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032608780
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1080/02331938608843131 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019756461
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1080/02331939108843697 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036629616
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1080/02331939108843708 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036017163
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1080/10556780290027828 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002327785
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1080/10556780290027837 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027345027
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1080/10556788.2010.526116 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006075580
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1080/10556788.2012.714781 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036718976
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1080/10556788.2017.1378652 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092078264
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1137/030601296 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842754
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1137/090748408 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062855965
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1137/090754595 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062856181
    206 rdf:type schema:CreativeWork
    207 https://doi.org/10.1137/1.9780898718768 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098556221
    208 rdf:type schema:CreativeWork
    209 https://www.grid.ac/institutes/grid.462405.1 schema:alternateName Institute of Problems of Mechanical Engineering
    210 schema:name Institute of Problems of Mechanical Engineering, Russian Academy of Sciences, Saint Petersburg, Russia
    211 Saint Petersburg State University, Saint Petersburg, Russia
    212 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...