Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier
Abstract We present and analyze a new generalized Frank–Wolfe method for the composite optimization problem $$(P): {\min }_{x\in {\mathbb {R}}^n} \; f(\mathsf {A} x) + h(x)$$...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2022
|
| Online Access: | https://hdl.handle.net/1721.1/142541 |
| _version_ | 1811072853030731776 |
|---|---|
| author | Zhao, Renbo Freund, Robert M. |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Zhao, Renbo Freund, Robert M. |
| author_sort | Zhao, Renbo |
| collection | MIT |
| description | Abstract
We present and analyze a new generalized Frank–Wolfe method for the composite optimization problem
$$(P): {\min }_{x\in {\mathbb {R}}^n} \; f(\mathsf {A} x) + h(x)$$
(
P
)
:
min
x
∈
R
n
f
(
A
x
)
+
h
(
x
)
, where f is a
$$\theta $$
θ
-logarithmically-homogeneous self-concordant barrier,
$$\mathsf {A}$$
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((\delta _0 + \theta + R_h)\ln (\delta _0) + (\theta + R_h)^2/\varepsilon )$$
O
(
(
δ
0
+
θ
+
R
h
)
ln
(
δ
0
)
+
(
θ
+
R
h
)
2
/
ε
)
iterations to produce an
$$\varepsilon $$
ε
-approximate solution, where
$$\delta _0$$
δ
0
denotes the initial optimality gap and
$$R_h$$
R
h
is the variation of h on its domain. This result establishes certain intrinsic connections between
$$\theta $$
θ
-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. |
| first_indexed | 2024-09-23T09:17:09Z |
| format | Article |
| id | mit-1721.1/142541 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:17:09Z |
| publishDate | 2022 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1425412023-07-31T17:10:14Z Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier Zhao, Renbo Freund, Robert M. Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Abstract We present and analyze a new generalized Frank–Wolfe method for the composite optimization problem $$(P): {\min }_{x\in {\mathbb {R}}^n} \; f(\mathsf {A} x) + h(x)$$ ( P ) : min x ∈ R n f ( A x ) + h ( x ) , where f is a $$\theta $$ θ -logarithmically-homogeneous self-concordant barrier, $$\mathsf {A}$$ 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((\delta _0 + \theta + R_h)\ln (\delta _0) + (\theta + R_h)^2/\varepsilon )$$ O ( ( δ 0 + θ + R h ) ln ( δ 0 ) + ( θ + R h ) 2 / ε ) iterations to produce an $$\varepsilon $$ ε -approximate solution, where $$\delta _0$$ δ 0 denotes the initial optimality gap and $$R_h$$ R h is the variation of h on its domain. This result establishes certain intrinsic connections between $$\theta $$ θ -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. 2022-05-16T16:11:54Z 2022-05-16T16:11:54Z 2022-05-14 2022-05-15T04:22:37Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/142541 Zhao, Renbo and Freund, Robert M. 2022. "Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier." PUBLISHER_CC en https://doi.org/10.1007/s10107-022-01820-9 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0 The Author(s) application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Zhao, Renbo Freund, Robert M. Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier |
| title | Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier |
| title_full | Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier |
| title_fullStr | Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier |
| title_full_unstemmed | Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier |
| title_short | Analysis of the Frank–Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier |
| title_sort | analysis of the frank wolfe method for convex composite optimization involving a logarithmically homogeneous barrier |
| url | https://hdl.handle.net/1721.1/142541 |
| work_keys_str_mv | AT zhaorenbo analysisofthefrankwolfemethodforconvexcompositeoptimizationinvolvingalogarithmicallyhomogeneousbarrier AT freundrobertm analysisofthefrankwolfemethodforconvexcompositeoptimizationinvolvingalogarithmicallyhomogeneousbarrier |