2E5213/5B5746 Optimization for Control and Signal Processing 

PhD course given jointly by Department of Mathematics and Department of Signals, Sensors and Systems

May-June 2001

Credits: 3 credits for hand in problems and exam, 2 additional credits for project. 

Schedule: starts Monday week 19 and runs for 7 weeks according to the table below. The time and venue for the lectures are 10.15-12.00 and room 3721, Lindstedtsvägen 25, respectively. 

Course Material: There is no book available that fully covers the course. Therefore we will hand out material in addition to reading parts of chapters 2, 3, 4, 6, 8, 9, 10, 11, 13, and 14 in "Handbook of Semidefinite Programming: Theory, Algorithms, and Applications", edited by H. Wolkowicz, R. Saigal, and L. Vandenberghe, Kluwer Academic Publishers, 2000, ISBN 0-7923-7771-0. It is recommended that you borrow or purchase the book  

Registration: send an E-mail to our administrator Monica Ringheim in which you give the following information: name, address, phone, E-mail, and your Swedish social security number (personnummer).  

Deadlines: Hand in problems should be completed within one week. Project report should be handed in no later than August 15.

Outline:

The lectures will be given by several different people at KTH. Anders Hansson, Division of Automatic Control, and Anders Forsgren and Ulf Jönsson, Division of Optimization and Systems Theory share the main responsibility for the course and will take care of hand in problems, projects, and examination. Mats Bengtsson, Division of Signal Processing will give one lecture. There will also be three invited lecturers from outside KTH: Lieven Vandenberghe, UCLA, Anders Helmersson, LiTH, and Sven Nordebo, University of Karlskrona/Ronneby. Course plan and abstracts of the lectures are given below.

Exam

GO GET IT

Hand in problems

hand in problem 2 (due May 30)

hand in problem 3 (due June 11) solutions

Software

Course Plan

Contents

1. Introduction

This lecture will give an outline of the course. Applications in control and signal processing where different optimization techniques are useful will be reviewed. Some of the basic tools such as ellipsoids and LMIs will be introduced.

2. Controller Synthesis using LMIs

The elimination lemma is introduced as a tool for controller synthesis. The discussion will then be focused around two problems

1. State feedback synthesis

2. H-infinity controller synthesis

The second problem is perhaps the most famous problem in robust control and it turns out that it can be solved solved in an elegant manner using the elimination lemma. The resulting controller parameters can be obtained from the solution of a linear matrix inequality.

3. Optimization 1

This lecture gives a background on optimization relevant to linear and nonlinear programming is given. Fundamental issues, such as convexity, duality, local and global optimality, are covered. Optimality conditions and separating hyperplanes are discussed.

4. Optimization 2

Linear matrix inequalities/semidefinite programming is introduced as a generalization of nonlinear programming. Computational complexity with respect to local and global minimization is discussed. Relaxations, in particular Lagrangian relaxation, are discussed.

5. The S-Procedure in Systems Analysis

The S-Procedure is a special case of Lagrange relaxation which has ample application in control and systems theory. It is used for relaxation of a large class nonconvex quadratic optimization problems into linear matrix inequalities. The main theoretical result is that the S-procedure under certain conditions is nonconservative. Application of the S-procedure to ellipsoidal approximation, stability analysis of uncertain systems, and some performance problems for linear systems will be discussed.

6. LPV/LFT Analysis and Synthesis

Linear parameter varying systems can be modeled with linear fractional transformations. The time-varying parameters are extracted from the system into a separate block while the remaining system is considered as linear time-invariant system. This LFT model can be used for closed loop analysis and controller synthesis. The closed loop analysis can be performed using small-gain theorem, mu-analysis and integral quadratic constraints. Various parameter properties can be considered. e.g. constant parameters, time-varying parameters with bounded rate of change. The analysis problem can usually be formulated as an LMI problem. The synthesis problem treats how to find a controller that yields a specified closed loop performance, if attainable. Here we will discuss various techniques, all based on LMIs. Since the complexity of the LPV/LFT model affects the computational effort required to solve the analysis and synthesis problems, we will also briefly discuss LPV/LFT model reduction.

7. Optimal Downlink Beamforming using Semidefinite Optimization

The application scenario in mind is a cellular system where each base station is equipped with an antenna array. Each base station serves one or more mobiles that share the same frequency band. When transmitting to one mobile, the base station will also cause interference at all other mobiles in the surroundings. The problem is to design the beamformers, i.e. the complex valued weights for each antenna element such that all mobiles get an acceptable signal to interference situation, keeping the total transmitted power as low as possible. This can be formulated as a convex quadratic cost function with a non-convex quadratic constraint for each mobile. This is one of the few examples where a Lagrangian relaxation provides the exact solution of the original problem. We also show how to extend the method to also find the optimal allocation of mobiles to base stations.

8. Optimization 3

Interior methods for nonlinear and semidefinite programming are described. Particular emphasis is put on primal-dual methods. Linear-algebraic issues with respect to the Newton iterations are discussed, as well as extensions to nonconvex problems.

9. Optimization 4

Issues related to large-scale structured problems are discussed. An alternative to interior methods for solving a semidefinite programming may be to use nondifferentiable optimization. Bundle methods have recently been introduced for solving large-scale semidefinite problems. Such methods are described in the lecture.

10. On the Convergence of Dual Nested Complex Approximation

The convergence of the Dual Nested Complex Approximation (DNCA) algorithm is justified by theoretical arguments. The complex approximation problem is formulated as a semi-infinite linear or quadratic program. The corresponding Kuhn-Tucker conditions are stated and the finiteness of the related Lagrange multipliers are justified by an application of the Caratheodory's dimensionality theorem. The primal and dual versions of the semi-infinite programming problem are formulated and discussed, and the interpretation of the DNCA algorithm as a dual method is established. The convergence of the DNCA algorithm is justified by using arguments from the theory of strong duality. Application examples are given in the area of digital and analog filter design.

11. Model Predictive Control

In this lecture stability of Model Predictive Controllers (MPCs) using a Lyapunov function approach is discussed. The approach unifies many existing ideas. Key ingredients are appropriate terminal state weights, terminal state constraint sets, and preliminary stabilizing feedbacks. It is also investigated how to solve the corresponding optimization problem efficiently. To this end a Riccati recursion technique is employed.

12. Efficient Optimization Routines for LMIs derived from the KYP Lemma

In this lecture is discussed how to implement an efficient interior-point algorithm for the linear matrix inequalities that result from integral quadratic constraints. The algorithm is a primal-dual potential reduction method, and the computational effort is dominated by a least-squares system that has to be solved in each iteration. The key to an efficient implementation is to utilize iterative methods and the specific structure of integral quadratic constraints.

13. Interior-point methods for convex optimization problems in signal processing and control - Part I.

In these two lectures, we discuss direct (non-iterative) techniques for exploiting problem structure in interior-point methods for large scale convex optimization. In part 1, we describe the basic principles and some general examples. We then apply these ideas to robust linear programming problems that arise in optimal control. We show that in some important cases the robust version of an LP can be solved at a cost that is not much higher than the corresponding non-robust LP.

14. Interior-point methods for convex optimization problems in signal processing and control - Part II

In this lecture we outline an alternative approach to exploiting problem structure in LMI constraints derived from the KYP lemma. For a specific example (the constraint that a vector of variables is a finite autocorrelation sequence) we show that the efficiency of primal, dual, or primal-dual interior-point methods can be increased by orders of magnitude by exploiting problem structure. We will also discuss several applications and extensions.