Coleman Thomas F. Large Sparse Numerical Optimization

Springer, 1984. — 111 p.The development of algorithms for large sparse numerical optimization is currently a very active area of research in numerical analysis. The adaptation of efficient methods to the large sparse setting is proving to be a difficult and challenging task. Apparently, it is often impossible to preserve sparsity and attain other desirable properties simultaneously: algorithms must achieve a delicate compromise. An exciting facet of problems in this area is that a full understanding of all algorithmic considerations requires ideas and concepts from many disciplines: eg. linear algebra, real analysis, data structures, graph theory, optimization theory, numerical methods. One of my goals in the design of this course was to emphasize this rich diversity of thought.
Though my personal research is mostly concerned with nonlinear optimization, I thought it best to start the course with a fairly detailed discussion of large sparse linear problems. The reasons are obvious: Firstly, they represent important optimization problems in their own right - there are still many open questions. Secondly, nonlinear problems are often solved via a sequence of linear approximations and therefore it is imperative that the complexity of the 'easy' subproblems be fully appreciated. Chapter 1 is devoted to large square systems of linear equations, Chapter 2 discusses overdetermined linear systems and Chapter 3 deals with large linear programs. The flavour of the first three chapters is somewhat different from the remainder of the notes: Their primary purpose to to provide some linear background to the more research oriented nonlinear chapters. Hence ideas are covered more quickly, almost in the style of a survey. (Nevertheless, I do point out research directions and interesting possibilities from time to time.)
The heart of the course and this manuscript is represented by Chapters 4 and 5. They are concerned with unconstrained nonlinear problems: equations, least squares and unconstrained optimization problems are all discussed with respect to algorithms, theoretical developments and current software. The material is presented unevenly with emphasis on topics and ideas of particular interest to me. I do not apologize for this: These notes are meant to reflect a personal and timely view of recent and current research in a lively field. They are not meant to be a tidy and complete presentation of a mature subject.
Finally, in Chapter 6, some of the issues concerning large quadratic programs are examined. This chapter is even less complete than the others - the intent is to give the reader a taste of the complexity and nature of large scale QP problems. I hope to teach a sequel course, in the near future, that deals with large QP's in
greater depth.