Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zh. Vychisl. Mat. Mat. Fiz., 2019, Volume 59, Number 6, Pages 961–971 (Mi zvmmf10907)  

Duality gap estimates for weak Chebyshev greedy algorithms in banach spaces

S. V. Mironov, S. P. Sidorov

Saratov State University, Saratov, 410012 Russia

Abstract: The paper studies weak greedy algorithms for finding sparse solutions of convex optimization problems in Banach spaces. We consider the concept of duality gap, the values of which are implicitly calculated at the step of choosing the direction of the fastest descent at each iteration of the greedy algorithm. We show that these values give upper bounds for the difference between the values of the objective function in the current state and the optimal point. Since the value of the objective function at the optimal point is not known in advance, the current values of the duality gap can be used, for example, in the stopping criteria for the greedy algorithm. In the paper, we find estimates of the duality gap values depending on the number of iterations for the weak greedy algorithms under consideration.

Key words: nonlinear optimization, greedy algorithms, sparse solution.

DOI: https://doi.org/10.1134/S0044466919060115


English version:
Computational Mathematics and Mathematical Physics, 2019, 59:6, 904–914

Bibliographic databases:

UDC: 517.518.86
Received: 13.03.2018
Revised: 28.01.2019
Accepted:08.02.2019

Citation: S. V. Mironov, S. P. Sidorov, “Duality gap estimates for weak Chebyshev greedy algorithms in banach spaces”, Zh. Vychisl. Mat. Mat. Fiz., 59:6 (2019), 961–971; Comput. Math. Math. Phys., 59:6 (2019), 904–914

Citation in format AMSBIB
\Bibitem{MirSid19}
\by S.~V.~Mironov, S.~P.~Sidorov
\paper Duality gap estimates for weak Chebyshev greedy algorithms in banach spaces
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2019
\vol 59
\issue 6
\pages 961--971
\mathnet{http://mi.mathnet.ru/zvmmf10907}
\crossref{https://doi.org/10.1134/S0044466919060115}
\elib{https://elibrary.ru/item.asp?id=37462914}
\transl
\jour Comput. Math. Math. Phys.
\yr 2019
\vol 59
\issue 6
\pages 904--914
\crossref{https://doi.org/10.1134/S0965542519060113}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000473489900005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85068573944}


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf10907
  • http://mi.mathnet.ru/eng/zvmmf/v59/i6/p961

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • ∆урнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:53

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021