ELEC-E5424 - Convex optimization D, Lecture, 7.9.2022-14.12.2022
This course space end date is set to 14.12.2022 Search Courses: ELEC-E5424
Topic outline
-
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
-
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
Quadratic and Hermitian 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
Quadratic optimization problems (QP)
Quadratically constrained quadratic problems (QCQP)
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
Gradient method
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 analysisGeneralized inequalities
-
Assignment 4: Optimization Algorithms