Numerical Optimization

We use the following notation: the working space is ℝ ⁿ , where the scalar product will be denoted indifferently by (x, y) or ‹x, y› or x ^⊤ y (actually, it will be the usual dot-product: \((x,y) = \Sigma _{i = 1}^n{x^i}{y^i}\)); | · | or ∥ · ∥ will denote the associated norm. The gradient (vector of partial derivatives) of a function f: ℝ ⁿ → ℝ will be denoted by ∇ f or f′; the Hessian (matrix of second derivatives) by ∇² f or f″. We will also use continually the notation g(x) = f′(x).

We start with some generalities on the unconstrained optimization problem

The conjugate gradient method is also aimed at accelerating the methods of Chap. 2. Its first motivation is to solve in n iterations a linear system with symmetric positive definite matrix (or, equivalently, to minimize in n iterations a quadratic strongly convex function on ℝ ⁿ ), without storing an additional matrix, without even storing the matrix of the system. In fact, to solve Ax + b = 0 (A symmetric positive definite), the conjugate gradient method just needs a “black box” (a subroutine) which, given the vector u, computes the vector v = Au. Naturally, this becomes particularly interesting when, while n is large, A is sparse and/or enjoys some structure allowing automatic calculations. Typical examples come from the discretization of partial differential equations.

The methods in this chapter, less “universal” than the preceding, are useful in a good number of cases. The first one (trust-region) is actually extremely important, and might supersede line-searches, sooner or later. The other methods deal with the direction; they are either classical (Gauss-Newton) or recent (limited-memory quasi-Newton, truncated Newton) and apply only in some well-defined subclasses of problems.

The aim of this chapter is to review some general theoretical issues concerning the problem where differentiability assumptions are replaced by convexity. We recall the necessary theory for solving (7.1), and give two important examples of non-differentiable functions, namely max-functions and dual functions.

Once a characterization of an optimal point is derived, we are interested in the problem of computing it. We consider in this chapter the main difficulties arising when f is not differentiable, and give a first sample of numerical methods.

None of the black-box methods considered so far are descent schemes. Only the steepest-descent method guarantees a decrease of the objective function at each iteration. However, it requires the complete knowledge of ∂ f, and can be unstable.

One of the most important applications of nonsmooth optimization methods is decomposition. Decomposition techniques are used to solve large-scale (or complex) problems, replacing them by a sequence of reduced-dimensional (or easier) local problems linked by a master program, see Fig. 10.1.

Before entering the subject itself, we recall some basic concepts. For further details, the reader is referred to the books by Fletcher [116, 1987], Ciarlet [74, 1988], Gauvin [128, 129, 1992–95], Hiriart-Urruty and Lemaréhal [171, 1993], and Bonnans and Shapiro [46, 2000]. See also [137] for an online review (in French).

In this chapter, we present and study several local methods for minimizing a nonlinear function subject only to nonlinear equality constraints. This is the problem (P _E ) represented in Figure 12.1: Ω is an open set of ℝ ⁿ , while f : Ω → ℝ and c : Ω → ℝ ^m are differentiable functions. Since we always assume that c is a submersion, which means that c′(x) is surjective (or onto) for all x ∈ Ω, the inequality m < n is natural. Indeed, for the Jacobian of the constraints to be surjective, we must have m ≤ n; but if m = n, any feasible point is isolated, which results in a completely different problem, for which the algorithms presented here are hardly appropriate. Therefore, a good geometrical representation of the feasible set of problem (P _E ) is that of a submanifold M _* of ℝ ⁿ , like the one depicted in Figure 12.1.

In this chapter, we consider the general minimization problem (P _EI ), with equality and inequality nonlinear constraints, which we recall in Figure 13.1.

The algorithms studied in chapters 12 and 13 generate converging sequences if the first iterate is close enough to a regular stationary point (see theorems 12.4, 12.5, 12.7, 13.2, and 13.4). Such an iterate is not necessarily at hand, so it is important to have techniques that allow the algorithms to force convergence, even when the starting point is far from a solution. This is known as the globalization of a local algorithm. The term is a little ambiguous, since it may suggest that it has a link with the search of global minimizers of (P _EI ). This is not at all the case (for an entry point on global optimization, see [178]).

There is no guarantee that the local algorithms in chapters 12 and 13 will converge when they are started at a point x ₁ far from a solution x _* to problem (P _E ) or (P _EI ). They can generate erratic sequences, which may by chance enter the neighborhood of a solution and then converge to it; but most often, the sequences will not converge. There exist several ways of damping this uncoordinated behavior and modifying the computation of the iterates so as to force their convergence. Two classes of techniques can be distinguished among them: line-search and trust-region. The former is presented in this chapter.

In this chapter we discuss the quasi-Newton versions of the algorithms presented in chapters 12, 13 and 15. Just as in the case of unconstrained problems (see § 4.4), the quasi-Newton approach is useful when one does not want to compute second order derivatives of the functions defining the optimization problem to solve. This may be motivated by various reasons, which are actually the same as in unconstrained optimization: computing second derivatives may demand too much human investment, or their computing time may be too important, or the problem dimensions may not allow the storage of Hessian matrices (in the latter case, limited-memory quasi-Newton methods will be appropriate). Generally speaking, quasi-Newton methods require more iterations to converge, but each iteration is faster (at least for equality constrained problems).

This chapter recalls some theoretical results on linearly constrained optimization with convex objective function. In the case of a linear or quadratic objective, we show existence of an optimal solution whenever the value of the problem is finite, as well as existence of a basic solution in the linear case. Lagrangian duality theory is presented. In the linear case, existence of a strictly complementary solutions is obtained whenever the optimal value of the problem is finite. Finally, the simplex algorithm is introduced in the last part of the chapter.

We develop the theoretical tools necessary for the algorithms to follow. The logarithmic penalty technique allows the introduction of the central path. In the case of linear or quadratic optimization, the optimality system and the central path are suitably cast into the framework of linear monotone complementarity problems.

The analysis of linear monotone complementarity problems starts with some results of global nature, involving the partition of variables, standard and canonical forms. Then comes a discussion on the magnitude of the variables in a neighborhood of the central path. We introduce two families of vector fields associated with the central path: the affine and centralization directions. The magnitude of the components of these fields are analyzed in detail. We also discuss the convergence of the differential system obtained by a convex combination of the affine and centralization directions.

Since the results stated here are motivated by the analysis of algorithms presented afterwards, a quick reading is sufficient for a first step. Besides, a large part of the technical difficulties are due to the modified field theory, useful for problems without strict complementarity. A reader interested mainly by linear optimization (where strict complementarity always holds) can therefore skip this part .

Path-following algorithms take as direction of displacement the Newton direction associated with the central-path equation. They use a parameter μ, measuring the violation of the complementarity conditions. The algorithm’s complexity is evaluated by the number of operations necessary to compute a point associated with the target measure μ _∞.

Let us study the resolution of the linear monotone complementarity problem without assuming the knowledge of a starting point in a given neighborhood of the central path. The algorithm is based on solving by Newton’s method the central path equations, starting from a non-feasible point. Implementing the algorithm is as simple as in the feasible case.

In the predictor-corrector algorithms studied so far, the moves aimed at improving centralization are clearly separated from those allowing a reduction of the parameter μ. It is tempting to consider algorithmic families in which the same move reduces μ while controlling centralization.

The aim of complexity theory is to evaluate the minimal number of operations required to compute a solution of a given problem (and to determine the corresponding algorithm). This theory is far from being closed, since the answer is not known even for solving a linear system Ax = b, with A a matrix n × n invertible: classical factorization methods have an O(n ³) complexity but certain fast algorithms have an O(n ^α ) complexity, with α < 2.5; the minimal value of α (proved to be larger than 2) is still unknown (see Coppersmith and Winograd [82]).

The algorithm of Karmarkar [179] is important from a historical point of view. In fact, it raised an impetus of research which ended in the path-following algorithms presented here. It is therefore interesting to have an idea of it.