Higher degree inexact model for optimization problems

Mohammad Alkousa, Fedor Stonyakin, Alexander Gasnikov, Asmaa Abdo and Mohammad Alcheikh

Chaos, Solitons & Fractals, 2024, vol. 186, issue C

Abstract: In this paper, it was proposed a new concept of the inexact higher degree (δ,L,q)-model of a function that is a generalization of the inexact (δ,L)-model (Gasnikov and Tyurin, 2019) (δ,L)-oracle (Devolder et al., 2014) and (δ,L)-oracle of degree q∈[0,2) (Nabou et al., 2024). Some examples were provided to illustrate the proposed new model. Adaptive inexact gradient and fast gradient methods for convex and strongly convex functions were constructed and analyzed using the new proposed inexact model. A universal fast gradient method that allows solving optimization problems with a weaker level of smoothness, among them non-smooth problems was proposed. For convex optimization problems it was proved that the proposed gradient and fast gradient methods could be converged with rates O1k+δkq/2 and O1k2+δk(3q−2)/2, respectively. For the gradient method, the coefficient of δ diminishes with k, and for the fast gradient method, there is no error accumulation for q≥2/3. It proposed a definition of an inexact higher degree oracle for strongly convex functions and a projected gradient method using this inexact oracle. For variational inequalities and saddle point problems, a higher degree inexact model and an adaptive method called Generalized Mirror Prox to solve such class of problems using the proposed inexact model were proposed. Some numerical experiments were conducted to demonstrate the effectiveness of the proposed inexact model, we tested the universal fast gradient method to solve some non-smooth problems with a geometrical nature.

Keywords: Inexact model; Inexact oracle; Adaptive method; Fast gradient method; Universal method; Convex optimization; Saddle point; Variational inequality (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077924008440
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:186:y:2024:i:c:s0960077924008440

DOI: 10.1016/j.chaos.2024.115292

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().