# Tutte seminar - Yurii Nesterov

Friday, December 7, 2007 — 3:30 PM to 4:30 PM EST

## Gradient Methods for Minimizing Composite Objective Function

Speaker: Yurii Nesterov Catholic University of Louvain Mathematics & Computer Building (MC) 5158

### Abstract:

In this talk we present several methods for solving optimization problems with the objective function formed as a sum of two convex terms: one is smooth and given by a black-box oracle, and another is general but simple and its structure is known. It appears that, despite to the bad properties of the sum, such problems can be solved with efficiency typical for the good part of the objective. For these problems, we consider primal and dual variants of the gradient method (converges as $O\left({1 \over k}\right)$), and an accelerated multistep version, which converges as $O\left({1 \over k2}\right)$, where $k$ is the iteration counter. For all methods, we present very efficient "line search" procedures and show that the additional computational work necessary for estimating the unknown problem class parameters can only double the complexity of each iteration.

Location
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1

### September 2021

S M T W T F S
29
30
31
1
2
4
5
6
7
8
11
12
14
15
16
18
19
21
22
23
25
26
28
29
1
2
1. 2021 (90)
1. October (2)
2. September (12)
3. August (7)
4. July (10)
5. June (12)
6. May (7)
7. April (9)
8. March (13)
9. February (8)
10. January (10)
2. 2020 (119)
1. December (5)
2. November (12)
3. October (12)
4. September (12)
5. August (11)
6. July (17)
7. June (11)
8. May (6)
9. March (11)
10. February (11)
11. January (11)
3. 2019 (167)
4. 2018 (136)
5. 2017 (103)
6. 2016 (137)
7. 2015 (136)
8. 2014 (88)
9. 2013 (48)
10. 2012 (39)
11. 2011 (36)
12. 2010 (40)
13. 2009 (40)
14. 2008 (39)
15. 2007 (15)