11. Nonsmooth Problems
Society for Industrial and Applied Mathematics eBooks · 2000
In this chapter, we turn to the case where ƒ(x) is continuous but not necessarily smooth. In fact, we shall study a narrower class of problems, namely, those that are locally Lipschitz continuous and regular in the region of interest. We recall from Section 3.1.2 that a function ƒ is locally Lipschitz continuous on if there are strictly positive values γ(x) and ϵ(x) for which |ƒ (z)−ƒ (x) |≤γ (x) ‖z−x‖ for all and all . It is regular (Section 3.1.4) if its one-sided directional derivative exists for all x and and the one-sided and generalized directional derivatives agree, that is, if ƒ d ′ (x) = ƒ d o (x) . While this is inevitably a restriction, it does cover a number of practically important classes of problems, namely, those that involve convex functions or those composed of convex and differentiable functions. In particular, if c is a continuously differentiable function from to , it allows us to consider the problems of minimizing ∥c(x)∥ or ∥ max[c(x), 0]∥ for any monotonic norm, which includes all the norms. Thus we are able to find the minimum-norm solution to a system of equations (we will consider this problem in a variety of different norms in Sections 16.1 and 16.2), or to find the least infeasible point to a system of inequalities , and hence to find feasible points to such systems, or even to minimize composite functions like ƒ(x) + ∥ min[c(x), 0]∥, which has implications for constrained optimization (see Chapter 15). It also allows us to cover slightly more general nonconvex functions like ƒ (x) = x3 −3 x2 +2x+1if x≥0,− x3 −3 x2 −2x+1if x<0, 11.0.1 which we illustrate in Figure 11.0.1. We shall give a number of important examples in Section 11.4. For future reference, we formally assume the following.