## Topic outline

• ### General

Textbook and Optional References

•        Stephen Boyd; Lieven Vandenberghe, Convex Optimization (Textbook!)

•        Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications

•        Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course

•        J. Gallier and J. Quaintance, Algebra, Topology, Dierential Calculus, and Optimization Theory For Computer Science and Engineering

Requirements:

•        4 homework assignments. Homeworks will normally be assigned on Wendsdays and will be due in 2 weeks.

•        Final Exam. The format will be decided depending on the sitation.

Homeworks: 60%. Exam: 40%. These weights are approximate. We reserve the right to change them later. Can be also discussed.

Description

Concentrates on recognizing and solving (using standard packages) convex optimization problems that arise in practice!

•        Convex sets, functions, and optimization problems.

•        Least-squares, linear and quadratic programs.

•        Semidefinite programming (SDP).

•        Minimax, extremal volume, and other problems with geometric interpretation.

•        Optimality conditions, duality theory, theorem of alternatives.

•        Introduction to unconstrained optimization algorithms.

•        Introduction to interior-point methods for constrained optimization.

•        Applications.

Course Objectives

•        to give the tools and training to recognize convex optimization problems that arise in electrical engineering and computer science

•        to present the basic theory of such problems, concentrating on results that are useful in computations

•        to give a thorough understanding of how such problems are solved, and some experience in solving them

•        to give the background required to use the standard methods and software packages (CVX toolbox) in your own research work

•        to give a number of examples of successful application of convex optimization techniques for solving problem in applied mathematics, computer science, statistics, electrical engineering, and science and engineering in general

• Prerequisites

Some general features of convex problems

Example: Aalto Design

What the duality theory is for?

What we will/won't do

How many problems are convex?

• (Vector) Spaces

Matrices

Systems of linear equations

Least squares

Special matrix forms

Eigenvalues and eigenvectors

Eigendecomposition

Singular value decomposition

• Subspace, affine set, convex set, convex cone

Simple examples and properties

Combination and hulls

Ellipsoids, polyhedra, norm balls

Affine and projective transformations

Separating and supporting hyperplanes

Generalized inequalities

• Assignment 1: Convex Sets

• Convex functions

Epigraph

Simple examples, elementary properties

More examples / exercises, more properties

Jensen's inequality

Quasiconvex, quasiconcave functions

Log-convex and log-concave functions

K-convexity

• Assignment 2: Convex Functions

• Solutions to Problems 6 and 7 of Assignment 1 which we didn't finish in the exercise session yesterday.

• Abstract form problem

Standard form problem

Convex optimization problem

Standard form with generalized inequalities

Mulitcriterion optimization

Restriction and relaxation

• Linear programming (LP)

Examples and applications of LP

Linear fractional programming

Examples and applications of QP and QCQP

Semidefinite programming (SDP) format

More applications

• Assignment 3: Convex Problems

• The lecture will be given by a visiting lecturer from Nokia Bell labs. It is necessary for doing Assignment 3.

• Terminology

General descent method

Line search types

Steepest descent method

Newton's method

Convergence analysis

• Brief history of Sequential Unconstrained Minimization Techniques (SUMT) & Interior point (IP) methods

Logarithmic barrier function

Central path

Basic SUMT

• Lagrange dual function

Lagrange dual problem

Strong duality and Slater's condition

Karush-Kuhn-Tucker (KKT) optimality conditions
Sensitivity analysis

Generalized inequalities

• Assignment 4: Optimization Algorithms