iPiasco: Inertial Proximal Algorithm for Strongly Convex Optimization View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-02-19

AUTHORS

Peter Ochs, Thomas Brox, Thomas Pock

ABSTRACT

In this paper, we present a forward–backward splitting algorithm with additional inertial term for solving a strongly convex optimization problem of a certain type. The strongly convex objective function is assumed to be a sum of a non-smooth convex and a smooth convex function. This additional knowledge is used for deriving a worst-case convergence rate for the proposed algorithm. It is proved to be an optimal algorithm with linear rate of convergence. For certain problems this linear rate of convergence is better than the provably optimal worst-case rate of convergence for smooth strongly convex functions. We demonstrate the efficiency of the proposed algorithm in numerical experiments and examples from image processing. More... »

PAGES

171-181

References to SciGraph publications

  • 1993-10. Heavy-ball method in nonconvex optimization problems in COMPUTATIONAL MATHEMATICS AND MODELING
  • 2013-03-23. Performance of first-order methods for smooth convex minimization: a novel approach in MATHEMATICAL PROGRAMMING
  • 2011. Convex Analysis and Monotone Operator Theory in Hilbert Spaces in NONE
  • 2004. Introductory Lectures on Convex Optimization, A Basic Course in NONE
  • 2004-12-29. Smooth minimization of non-smooth functions in MATHEMATICAL PROGRAMMING
  • 2010-09-02. Dualization of Signal Recovery Problems in SET-VALUED AND VARIATIONAL ANALYSIS
  • 2015-10-30. On the ergodic convergence rates of a first-order primal–dual algorithm in MATHEMATICAL PROGRAMMING
  • 2001-03. An Inertial Proximal Method for Maximal Monotone Operators via Discretization of a Nonlinear Oscillator with Damping in SET-VALUED AND VARIATIONAL ANALYSIS
  • 2010-12-21. A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging in JOURNAL OF MATHEMATICAL IMAGING AND VISION
  • 2009. Edge-Based Image Compression with Homogeneous Diffusion in COMPUTER ANALYSIS OF IMAGES AND PATTERNS
  • 2012-12-21. Gradient methods for minimizing composite functions in MATHEMATICAL PROGRAMMING
  • <error retrieving object. in <ERROR RETRIEVING OBJECT
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10851-015-0565-0

    DOI

    http://dx.doi.org/10.1007/s10851-015-0565-0

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Freiburg, Freiburg, Germany", 
              "id": "http://www.grid.ac/institutes/grid.5963.9", 
              "name": [
                "University of Freiburg, Freiburg, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ochs", 
            "givenName": "Peter", 
            "id": "sg:person.011151475055.48", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011151475055.48"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Freiburg, Freiburg, Germany", 
              "id": "http://www.grid.ac/institutes/grid.5963.9", 
              "name": [
                "University of Freiburg, Freiburg, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Brox", 
            "givenName": "Thomas", 
            "id": "sg:person.012443225372.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012443225372.65"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Digital Safety & Security Department, AIT Austrian Institute of Technology GmbH, Donau-City-Stra\u00dfe 1, 1220, Vienna, Austria", 
              "id": "http://www.grid.ac/institutes/grid.4332.6", 
              "name": [
                "Graz University of Technology, Graz, Austria", 
                "Digital Safety & Security Department, AIT Austrian Institute of Technology GmbH, Donau-City-Stra\u00dfe 1, 1220, Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pock", 
            "givenName": "Thomas", 
            "id": "sg:person.015744126036.09", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015744126036.09"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s10851-010-0251-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010318529", 
              "https://doi.org/10.1007/s10851-010-0251-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11228-010-0147-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032025040", 
              "https://doi.org/10.1007/s11228-010-0147-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03767-2_58", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031051955", 
              "https://doi.org/10.1007/978-3-642-03767-2_58"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-004-0552-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030642071", 
              "https://doi.org/10.1007/s10107-004-0552-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1011253113155", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004603933", 
              "https://doi.org/10.1023/a:1011253113155"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4419-8853-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049823794", 
              "https://doi.org/10.1007/978-1-4419-8853-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-012-0629-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000563802", 
              "https://doi.org/10.1007/s10107-012-0629-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-013-0653-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000652377", 
              "https://doi.org/10.1007/s10107-013-0653-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01128757", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019490160", 
              "https://doi.org/10.1007/bf01128757"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-82118-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039359666", 
              "https://doi.org/10.1007/978-3-642-82118-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-015-0957-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012909932", 
              "https://doi.org/10.1007/s10107-015-0957-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4419-9467-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044558790", 
              "https://doi.org/10.1007/978-1-4419-9467-7"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-02-19", 
        "datePublishedReg": "2015-02-19", 
        "description": "In this paper, we present a forward\u2013backward splitting algorithm with additional inertial term for solving a strongly convex optimization problem of a certain type. The strongly convex objective function is assumed to be a sum of a non-smooth convex and a smooth convex function. This additional knowledge is used for deriving a worst-case convergence rate for the proposed algorithm. It is proved to be an optimal algorithm with linear rate of convergence. For certain problems this linear rate of convergence is better than the provably optimal worst-case rate of convergence for smooth strongly convex functions. We demonstrate the efficiency of the proposed algorithm in numerical experiments and examples from image processing.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10851-015-0565-0", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1041815", 
            "issn": [
              "0924-9907", 
              "1573-7683"
            ], 
            "name": "Journal of Mathematical Imaging and Vision", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "53"
          }
        ], 
        "keywords": [
          "convex functions", 
          "non-smooth convex", 
          "smooth convex function", 
          "worst-case convergence rate", 
          "convex optimization problem", 
          "convex objective function", 
          "additional inertial term", 
          "backward splitting algorithm", 
          "convex optimization", 
          "optimization problem", 
          "proximal algorithm", 
          "convergence rate", 
          "worst-case rate", 
          "numerical experiments", 
          "inertial terms", 
          "objective function", 
          "splitting algorithm", 
          "linear rate", 
          "optimal algorithm", 
          "inertial proximal algorithm", 
          "convergence", 
          "certain problems", 
          "algorithm", 
          "problem", 
          "convex", 
          "certain types", 
          "optimization", 
          "function", 
          "image processing", 
          "sum", 
          "additional knowledge", 
          "terms", 
          "efficiency", 
          "experiments", 
          "processing", 
          "types", 
          "rate", 
          "knowledge", 
          "example", 
          "paper"
        ], 
        "name": "iPiasco: Inertial Proximal Algorithm for Strongly Convex Optimization", 
        "pagination": "171-181", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1049874795"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10851-015-0565-0"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10851-015-0565-0", 
          "https://app.dimensions.ai/details/publication/pub.1049874795"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:40", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_655.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10851-015-0565-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/s10851-015-0565-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/s10851-015-0565-0'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10851-015-0565-0'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10851-015-0565-0'


     

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

    163 TRIPLES      21 PREDICATES      76 URIs      56 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10851-015-0565-0 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N19b606df072248e6bba604f4b1a31034
    4 schema:citation sg:pub.10.1007/978-1-4419-8853-9
    5 sg:pub.10.1007/978-1-4419-9467-7
    6 sg:pub.10.1007/978-3-642-03767-2_58
    7 sg:pub.10.1007/978-3-642-82118-9
    8 sg:pub.10.1007/bf01128757
    9 sg:pub.10.1007/s10107-004-0552-5
    10 sg:pub.10.1007/s10107-012-0629-5
    11 sg:pub.10.1007/s10107-013-0653-0
    12 sg:pub.10.1007/s10107-015-0957-3
    13 sg:pub.10.1007/s10851-010-0251-1
    14 sg:pub.10.1007/s11228-010-0147-7
    15 sg:pub.10.1023/a:1011253113155
    16 schema:datePublished 2015-02-19
    17 schema:datePublishedReg 2015-02-19
    18 schema:description In this paper, we present a forward–backward splitting algorithm with additional inertial term for solving a strongly convex optimization problem of a certain type. The strongly convex objective function is assumed to be a sum of a non-smooth convex and a smooth convex function. This additional knowledge is used for deriving a worst-case convergence rate for the proposed algorithm. It is proved to be an optimal algorithm with linear rate of convergence. For certain problems this linear rate of convergence is better than the provably optimal worst-case rate of convergence for smooth strongly convex functions. We demonstrate the efficiency of the proposed algorithm in numerical experiments and examples from image processing.
    19 schema:genre article
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N1c80db2360ac400d8c79218d142cbf45
    22 N74afe375109f43f0b4f3e782e07f6812
    23 sg:journal.1041815
    24 schema:keywords additional inertial term
    25 additional knowledge
    26 algorithm
    27 backward splitting algorithm
    28 certain problems
    29 certain types
    30 convergence
    31 convergence rate
    32 convex
    33 convex functions
    34 convex objective function
    35 convex optimization
    36 convex optimization problem
    37 efficiency
    38 example
    39 experiments
    40 function
    41 image processing
    42 inertial proximal algorithm
    43 inertial terms
    44 knowledge
    45 linear rate
    46 non-smooth convex
    47 numerical experiments
    48 objective function
    49 optimal algorithm
    50 optimization
    51 optimization problem
    52 paper
    53 problem
    54 processing
    55 proximal algorithm
    56 rate
    57 smooth convex function
    58 splitting algorithm
    59 sum
    60 terms
    61 types
    62 worst-case convergence rate
    63 worst-case rate
    64 schema:name iPiasco: Inertial Proximal Algorithm for Strongly Convex Optimization
    65 schema:pagination 171-181
    66 schema:productId N59d38b2e449144a3a1886805400426c5
    67 Nc86c75ddac15421cb50e7021d7e04de7
    68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049874795
    69 https://doi.org/10.1007/s10851-015-0565-0
    70 schema:sdDatePublished 2022-10-01T06:40
    71 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    72 schema:sdPublisher Na37e676d36194674bf6cd9d4c3e253fa
    73 schema:url https://doi.org/10.1007/s10851-015-0565-0
    74 sgo:license sg:explorer/license/
    75 sgo:sdDataset articles
    76 rdf:type schema:ScholarlyArticle
    77 N19b606df072248e6bba604f4b1a31034 rdf:first sg:person.011151475055.48
    78 rdf:rest N369497d3d45846d7ad5f8f681bbc6871
    79 N1c80db2360ac400d8c79218d142cbf45 schema:volumeNumber 53
    80 rdf:type schema:PublicationVolume
    81 N369497d3d45846d7ad5f8f681bbc6871 rdf:first sg:person.012443225372.65
    82 rdf:rest N69a84509651249fd9455cfae446150c8
    83 N59d38b2e449144a3a1886805400426c5 schema:name doi
    84 schema:value 10.1007/s10851-015-0565-0
    85 rdf:type schema:PropertyValue
    86 N69a84509651249fd9455cfae446150c8 rdf:first sg:person.015744126036.09
    87 rdf:rest rdf:nil
    88 N74afe375109f43f0b4f3e782e07f6812 schema:issueNumber 2
    89 rdf:type schema:PublicationIssue
    90 Na37e676d36194674bf6cd9d4c3e253fa schema:name Springer Nature - SN SciGraph project
    91 rdf:type schema:Organization
    92 Nc86c75ddac15421cb50e7021d7e04de7 schema:name dimensions_id
    93 schema:value pub.1049874795
    94 rdf:type schema:PropertyValue
    95 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Mathematical Sciences
    97 rdf:type schema:DefinedTerm
    98 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Numerical and Computational Mathematics
    100 rdf:type schema:DefinedTerm
    101 sg:journal.1041815 schema:issn 0924-9907
    102 1573-7683
    103 schema:name Journal of Mathematical Imaging and Vision
    104 schema:publisher Springer Nature
    105 rdf:type schema:Periodical
    106 sg:person.011151475055.48 schema:affiliation grid-institutes:grid.5963.9
    107 schema:familyName Ochs
    108 schema:givenName Peter
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011151475055.48
    110 rdf:type schema:Person
    111 sg:person.012443225372.65 schema:affiliation grid-institutes:grid.5963.9
    112 schema:familyName Brox
    113 schema:givenName Thomas
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012443225372.65
    115 rdf:type schema:Person
    116 sg:person.015744126036.09 schema:affiliation grid-institutes:grid.4332.6
    117 schema:familyName Pock
    118 schema:givenName Thomas
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015744126036.09
    120 rdf:type schema:Person
    121 sg:pub.10.1007/978-1-4419-8853-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049823794
    122 https://doi.org/10.1007/978-1-4419-8853-9
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-1-4419-9467-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044558790
    125 https://doi.org/10.1007/978-1-4419-9467-7
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-642-03767-2_58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031051955
    128 https://doi.org/10.1007/978-3-642-03767-2_58
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/978-3-642-82118-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039359666
    131 https://doi.org/10.1007/978-3-642-82118-9
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/bf01128757 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019490160
    134 https://doi.org/10.1007/bf01128757
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/s10107-004-0552-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030642071
    137 https://doi.org/10.1007/s10107-004-0552-5
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/s10107-012-0629-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000563802
    140 https://doi.org/10.1007/s10107-012-0629-5
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/s10107-013-0653-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000652377
    143 https://doi.org/10.1007/s10107-013-0653-0
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/s10107-015-0957-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012909932
    146 https://doi.org/10.1007/s10107-015-0957-3
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/s10851-010-0251-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010318529
    149 https://doi.org/10.1007/s10851-010-0251-1
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/s11228-010-0147-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032025040
    152 https://doi.org/10.1007/s11228-010-0147-7
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1023/a:1011253113155 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004603933
    155 https://doi.org/10.1023/a:1011253113155
    156 rdf:type schema:CreativeWork
    157 grid-institutes:grid.4332.6 schema:alternateName Digital Safety & Security Department, AIT Austrian Institute of Technology GmbH, Donau-City-Straße 1, 1220, Vienna, Austria
    158 schema:name Digital Safety & Security Department, AIT Austrian Institute of Technology GmbH, Donau-City-Straße 1, 1220, Vienna, Austria
    159 Graz University of Technology, Graz, Austria
    160 rdf:type schema:Organization
    161 grid-institutes:grid.5963.9 schema:alternateName University of Freiburg, Freiburg, Germany
    162 schema:name University of Freiburg, Freiburg, Germany
    163 rdf:type schema:Organization
     




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


    ...