Welcome to Math 582 B ,
Winter 2009
(last updated 3/11/2009)
- Course notes for week 10 are posted below.
- The problem set (as well as the course project) are due on March 16, noon.
- More A and B problems are posted below.
- The course project (due March 16 noon) is posted
here
.
For option 2, the problem data and info for
maxG11 and maxG51 can be found here .
(See the three links: detailed description, description of file format,
and individual problems.)
For option 3, the noisy Barbara image is posted
here . The
original image is here .
- There is a related convex
optimization course (with more emphasis on applications)
this quarter that may be of interest.
It is
AA/EE/ME 578: Optimization in System Sciences ,
meeting on Tues/Thurs 1:30-2:50pm and taught by Maryam Fazel
in EE.
Course Info:
- Instructor:
Paul Tseng
- E-mail:tseng@math.washington.edu
- Office:
Padelford C-344
- Office Hours:
Thursdays 2:00-3:30 or whenever I am free
- Lecture:
M, W, F 9:30-10:20 AM, Room
MOR 219
- Textbook:
No textbook, but lecture notes will be posted here regularly.
Some relevant references:
- A. Ben-Tal, A. Nemirovski, Lectures on Modern Convex Optimization,
MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2001.
-
Y. Nesterov, Introductory Lectures on Convex Optimization,
Kluwer, 2004.
-
S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University
Press, 2004; also available on-line as a PDF file.
- Course Syllabus (pdf)
Prerequisites:
A desire to understand and precise logical reasoning
About this course:
In the last 20 years there has been
great interest in applications (communications, control, combinatorial
optimization) and efficient algorithms (primal-dual interior-point
algorithms, first-order
smoothing algorithms of Nesterov and Nemirovski) for convex (conic) optimization.
In this course, we will study structured convex optimization
problems (semidefinite program, second-order cone program, and others)
and algorithms. Topics include Goemans and Williamson's
.8785-approximation algorithm for MaxCut, deterministic
and randomized techniques for
rank reduction in semidefinite programming relaxation of nonconvex
quadratic optimization, self-concordant log-barrier function for
symmetric cones, O(sqrt{n}*log(1/epsilon)) iteration complexity of
interior-point methods, O(1/epsilon0.5) iteration complexity of accelerated
gradient
methods
for large scale problems. We'll study issues such as
approximation bound,
convergence, complexity, and implementation.
Some background in convex analyis and optimization is helpful, though not
required, as all background materials will be reviewed, starting with
properties of convex sets, cones, functions, etc.
Handouts/Slides (Pdf files)
Problems (Pdf files)
Links of Interest: