A Newton Frank–Wolfe method for constrained self-concordant minimization

Deyi Liu (), Volkan Cevher () and Quoc Tran-Dinh ()
Additional contact information
Deyi Liu: The University of North Carolina at Chapel Hill
Volkan Cevher: Laboratory for Information and Inference Systems, EPFL
Quoc Tran-Dinh: The University of North Carolina at Chapel Hill

Journal of Global Optimization, 2022, vol. 83, issue 2, No 6, 273-299

Abstract: Abstract We develop a new Newton Frank–Wolfe algorithm to solve a class of constrained self-concordant minimization problems using linear minimization oracles (LMO). Unlike L-smooth convex functions, where the Lipschitz continuity of the objective gradient holds globally, the class of self-concordant functions only has local bounds, making it difficult to estimate the number of linear minimization oracle (LMO) calls for the underlying optimization algorithm. Fortunately, we can still prove that the number of LMO calls of our method is nearly the same as that of the standard Frank-Wolfe method in the L-smooth case. Specifically, our method requires at most $${\mathcal {O}}\big (\varepsilon ^{-(1 + \nu )}\big )$$ O ( ε - ( 1 + ν ) ) LMO’s, where $$\varepsilon $$ ε is the desired accuracy, and $$\nu \in (0, 0.139)$$ ν ∈ ( 0 , 0.139 ) is a given constant depending on the chosen initial point of the proposed algorithm. Our intensive numerical experiments on three applications: portfolio design with the competitive ratio, D-optimal experimental design, and logistic regression with elastic-net regularizer, show that the proposed Newton Frank–Wolfe method outperforms different state-of-the-art competitors.

Keywords: Frank–Wolfe method; Inexact projected Newton scheme; Self-concordant function; Constrained convex optimization; Oracle complexity; 90C25; 90-08 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01105-z 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:83:y:2022:i:2:d:10.1007_s10898-021-01105-z

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

DOI: 10.1007/s10898-021-01105-z

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 ().