ABSTRACT
Nonlinear constrained optimization refers to the problem of minimizing f (x) subject to x ∈ D, where D is a subset of Rn and f is a continuous function from D to R. Thus, an input instance is a specification of D, called the feasible set, and f , called the objective function. The output from an optimization algorithm is either a point x∗ ∈ D, called an optimizer or global optimizer, such that f (x∗) ≤ f (x) for all x ∈ D, or else a statement (preferably accompanied by a certificate) that no such x∗ exists. The termsminimizer and global minimizer are also used. Stated in thismanner, nonlinear optimization encompasses ahuge rangeof scientific andengineer-
ing problems. In fact, this statement of the problem is too general: there are undecidable problems that can naturally fit into the framework of the last paragraph. Thus, most optimization algorithms are limited to some subclass of the general case. Furthermore, most algorithms compute something easier to find than a true global minimizer, like a local minimizer. This chapter focuses on convexprogramming, the subclass of nonlinear optimization inwhich the
setD is convex and the function f is also convex. The term convex is defined in Section 32.2. Convex programming is interesting for three reasons: (a) convex problems arise in many applications, some of which are described in subsequent sections, (b) mathematicians have developed a rich body of theory on the topic of convexity, and (c) there are powerful algorithms for efficiently solving convex
and
problems, which is the topic of most of this chapter. The development of self-concordant barrier functions by Nesterov and Nemirovskii [44] has led to much new research in this field. The purpose of this chapter is to describe some of the fundamentals of convex optimization and sketch some of the recent developments based on self-concordance. At the end of this chapter, some issues concerning general (nonconvex) nonlinear optimization are raised. This chapter does not cover low dimensional convex programming in which the number of unknowns is very small, e.g., less than 10. Such problems arise in computational geometry and are covered in that chapter. The remainder of this chapter is organized as follows. In Section 32.2 we cover the general def-
initions and the principles of convex optimization. In Section 32.3 we cover the ellipsoid method for convex optimization. In Sections 32.4 and 32.5 we describe an interior-point method for convex programming, based on self-concordant barrier functions. In Section 32.6 the interior-point method is specialized to semidefinite programming and Section 32.7 is further specialized to linear programming. In Section 32.8 we discuss some Turing-machine complexity issues for convex optimization. Finally, in Section 32.10 we make some brief remarks on the applications to nonconvex optimization.
