Convexity: convexity and optimization—Part I

Mathematical optimization methods are today used routinely as a tool for economic and industrial planning, in production control and product de- sign, in civil and military logistics, in medical image analysis, etc., and the development in the field of optimization has been tremendous since World War II. In 1945, George Stigler studied a diet problem with 77 foods and 9 constraints without being able to determine the optimal diet today it is possible to solve optimization problems containing hundreds of thousands of variables and constraints. There are two factors that have made this pos sible computers and efficient algorithms. It is the rapid development in the computer area that has been most visible to the common man, but the algorithm development has also been tremendous during the past 70 years, and computers would be of little use without efficient algorithms. Maximization and minimization problems have of course been studied and solved since the beginning of the mathematical analysis, but optimization theory in the modern sense started around 1948 with George Dantzig, who introduced and popularized the concept of linear programming and proposed an efficient solution algorithm, the simplex algorithm, for such problems. The type of optimization problems to be discussed by us are problems that can be formulated as the problem to maximize (or minimize) a given function over a somehow given subset of R. In order to obtain general results of interest we need to make some assumptions about the function and the set, and it is here that convexity enters into the picture. The first part in this series of three on convexity and optimization therefore deals with finite dimensional convexity theory. Since convexity plays an important role in many areas of mathematics, significantly more about convexity is included than is used in the subsequent two parts on optimization, where Part II provides the basic classical theory for linear and convex optimization, and Part III describes Newton's algorithm, self-concordant functions and an interior point method with self-concordant barriers. Parts II and III present a number of algorithms, but the emphasis is al- ways on the mathematical theory, so we do not describe how the algorithms should be implemented numerically. Anyone who is interested in these im- portant aspects should consult specialized literature in the field.