Journal article
Analysis of the FrankâWolfe method for convex composite optimization involving a logarithmically-homogeneous barrier
Mathematical programming, Vol.199(1-2), pp.123-163
05/01/2023
DOI: 10.1007/s10107-022-01820-9
Abstract
We present and analyze a new generalized FrankâWolfe method for the composite optimization problem
(
P
)
:
min
x
â
R
n
f
(
A
x
)
+
h
(
x
)
, where
f
is a
θ
-logarithmically-homogeneous self-concordant barrier,
A
is a linear operator and the function
h
has a bounded domain but is possibly non-smooth. We show that our generalized FrankâWolfe method requires
O
(
(
δ
0
+
θ
+
R
h
)
ln
(
δ
0
)
+
(
θ
+
R
h
)
2
/
ε
)
iterations to produce an
ε
-approximate solution, where
δ
0
denotes the initial optimality gap and
R
h
is the variation of
h
on its domain. This result establishes certain intrinsic connections between
θ
-logarithmically homogeneous barriers and the FrankâWolfe method. When specialized to the
D
-optimal design problem, we essentially recover the complexity obtained by Khachiyan (Math Oper Res 21 (2): 307â320, 1996) using the FrankâWolfe method with exact line-search. We also study the (Fenchel) dual problem of (
P
), and we show that our new method is equivalent to an adaptive-step-size mirror descent method applied to the dual problem. This enables us to provide iteration complexity bounds for the mirror descent method despite the fact that the dual objective function is non-Lipschitz and has unbounded domain. In addition, we present computational experiments that point to the potential usefulness of our generalized FrankâWolfe method on Poisson image de-blurring problems with TV regularization, and on simulated PET problem instances.
Details
- Title: Subtitle
- Analysis of the FrankâWolfe method for convex composite optimization involving a logarithmically-homogeneous barrier
- Creators
- Renbo Zhao - MIT Operations Research CenterRobert M. Freund - MIT Sloan School of Management
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.199(1-2), pp.123-163
- DOI
- 10.1007/s10107-022-01820-9
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Publisher
- Springer Berlin Heidelberg
- Grant note
- FA9550-19-1-0240 / AFOSR
- Language
- English
- Date published
- 05/01/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984446523202771
Metrics
24 Record Views