Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. A Newton Frank-Wolfe method for constrained self-concordant minimization
 
research article

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

Liu, Deyi
•
Cevher, Volkan  orcid-logo
•
Tran-Dinh, Quoc  
2022
Journal Of Global Optimization

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 O(epsilon-(1+nu)) LMO's, where epsilon is the desired accuracy, and nu is an element of(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.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s10898-021-01105-z
Web of Science ID

WOS:000720582500001

Author(s)
Liu, Deyi
Cevher, Volkan  orcid-logo
Tran-Dinh, Quoc  
Date Issued

2022

Publisher

SPRINGER

Published in
Journal Of Global Optimization
Volume

83

Start page

273

End page

299

Subjects

Operations Research & Management Science

•

Mathematics, Applied

•

Mathematics

•

frank-wolfe method

•

inexact projected newton scheme

•

self-concordant function

•

constrained convex optimization

•

oracle complexity

•

conditional gradient-method

•

convergence

•

algorithm

•

designs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Available on Infoscience
December 4, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/183564
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés