Regrets of proximal method of multipliers for online non-convex optimization with long term constraints

Liwei Zhang (), Haoyang Liu () and Xiantao Xiao ()
Additional contact information
Liwei Zhang: Dalian University of Technology
Haoyang Liu: Dalian University of Technology
Xiantao Xiao: Dalian University of Technology

Journal of Global Optimization, 2023, vol. 85, issue 1, No 4, 80 pages

Abstract: Abstract The online optimization problem with non-convex loss functions over a closed convex set, coupled with a set of inequality (possibly non-convex) constraints is a challenging online learning problem. A proximal method of multipliers with quadratic approximations (named as OPMM) is presented to solve this online non-convex optimization with long term constraints. Regrets of the violation of Karush-Kuhn-Tucker conditions of OPMM for solving online non-convex optimization problems are analyzed. Under mild conditions, it is shown that this algorithm exhibits $${{\mathcal {O}}}(T^{-1/8})$$ O ( T - 1 / 8 ) Lagrangian gradient violation regret, $${{\mathcal {O}}}(T^{-1/8})$$ O ( T - 1 / 8 ) constraint violation regret and $${{\mathcal {O}}}(T^{-1/4})$$ O ( T - 1 / 4 ) complementarity residual regret if parameters in the algorithm are properly chosen, where T denotes the number of time periods. For the case that the objective is a convex quadratic function, we demonstrate that the regret of the objective reduction can be established even the feasible set is non-convex. For the case when the constraint functions are convex, if the solution of the subproblem in OPMM is obtained by solving its dual, OPMM is proved to be an implementable projection method for solving the online non-convex optimization problem.

Keywords: Online Non-convex Optimization; Proximal Method of Multipliers with Quadratic Approximations; Lagrangian Gradient Violation Regret; Constraint Violation Regret; Complementarity Residual Regret (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01196-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jglopt:v:85:y:2023:i:1:d:10.1007_s10898-022-01196-2

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01196-2

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().