ELEC-E5424 - Convex optimization D, Lecture, 7.9.2022-14.12.2022

Topic outline

• Select topic General

  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, Differential Calculus, and Optimization Theory For Computer Science and Engineering

  Course Requirements and Grading

  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.

  Grading: 

  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

  
  

  • Select activity Announcements

    

    Announcements Forum
  • Select activity Lecture 0: Introductory Lecture

    

    Lecture 0: Introductory Lecture File PDF

    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?

  • Select activity Lecture 1: Some Useful Concepts and Facts from Linear Algebra

    

    Lecture 1: Some Useful Concepts and Facts from Linear Algebra File PDF

    (Vector) Spaces 

    Matrices 

    Systems of linear equations 

    Least squares

    Special matrix forms

    Quadratic and Hermitian forms

    Eigenvalues and eigenvectors

    Eigendecomposition

    Singular value decomposition

  • Select activity Lecture 2: Convex Sets

    

    Lecture 2: Convex Sets File PDF

    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

  • Select activity Assignment 1

    

    Assignment 1

    Assignment 1: Convex Sets
    

  • Select activity Lecture 3: Convex Functions

    

    Lecture 3: Convex Functions File PDF

    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
    

  • Select activity Assignment 2

    

    Assignment 2

    Assignment 2: Convex Functions

  • Select activity Solutions to Problems 6 and 7 of Assignment 1

    

    Solutions to Problems 6 and 7 of Assignment 1 File PDF

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

  • Select activity Lecture 4: Convex Optimization Problems

    

    Lecture 4: Convex Optimization Problems File PDF

    Abstract form problem

    Standard form problem
    

    Convex optimization problem
    

    Standard form with generalized inequalities
    

    Mulitcriterion optimization
    

    Restriction and relaxation
    

  • Select activity Lecture 5: Linear, Quadratic Problems and SDP Format

    

    Lecture 5: Linear, Quadratic Problems and SDP Format File PDF

    Linear programming (LP) 

    Examples and applications of LP

    Linear fractional programming 

    Quadratic optimization problems (QP)

    Quadratically constrained quadratic problems (QCQP) 

    Examples and applications of QP and QCQP

    Semidefinite programming (SDP) format

    More applications

  • Select activity Assignment 3

    

    Assignment 3

    Assignment 3: Convex Problems 

  • Select activity Lecture 6: Introduction to CVX

    

    Lecture 6: Introduction to CVX File PDF

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

  • Select activity Lecture 7: Smooth Unconstrained Minimization Algorithms

    

    Lecture 7: Smooth Unconstrained Minimization Algorithms File PDF

    Terminology

    General descent method

    Line search types

    Gradient method

    Steepest descent method

    Newton's method

    Convergence analysis

  • Select activity Lecture 8: Introduction to Sequential Unconstrained Minimization for Constrained Optimization

    

    Lecture 8: Introduction to Sequential Unconstrained Minimization for Constrained Optimization File PDF

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

    Logarithmic barrier function

    Central path

    Basic SUMT

  • Select activity Lecture 9: Duality (Additional, only if we have time left)

    

    Lecture 9: Duality (Additional, only if we have time left) File PDF

    Lagrange dual function

    Lagrange dual problem
    

    Strong duality and Slater's condition

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

    Generalized inequalities
    

  • Select activity Assignment 4

    

    Assignment 4

    Assignment 4: Optimization Algorithms