nach oben

2014 | Buch

Kapitel lesen Erstes Kapitel lesen

Introduction to Nonsmooth Optimization

Theory, Practice and Software

verfasst von: Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Verlag: Springer International Publishing

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book is the first easy-to-read text on nonsmooth optimization (NSO, not necessarily diﬀerentiable optimization). Solving these kinds of problems plays a critical role in many industrial applications and real-world modeling systems, for example in the context of image denoising, optimal control, neural network training, data mining, economics and computational chemistry and physics. The book covers both the theory and the numerical methods used in NSO and provide an overview of diﬀerent problems arising in the ﬁeld. It is organized into three parts:

1. convex and nonconvex analysis and the theory of NSO;

2. test problems and practical applications;

3. a guide to NSO software.

The book is ideal for anyone teaching or attending NSO courses. As an accessible introduction to the ﬁeld, it is also well suited as an independent learning guide for practitioners already familiar with the basics of optimization.

Inhaltsverzeichnis

Frontmatter

Nonsmooth Analysis and Optimization

Frontmatter

Chapter 1. Theoretical Background

Abstract

In this chapter, we collect some notations and basic results of smooth analysis. We also recall fundamentals from matrix calculus.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 2. Convex Analysis

Abstract

The theory of nonsmooth analysis is based on convex analysis. Thus, we start this chapter by giving basic concepts and results of convexity. We take a geometrical viewpoint by examining the tangent and normal cones of convex sets. Then we generalize the concepts of differential calculus for convex, not necessarily differentiable functions. We define subgradients and subdifferentials and present some basic results. At the end of this chapter, we link these analytical and geometrical concepts together.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 3. Nonconvex Analysis

Abstract

In this chapter, we generalize the convex concepts defined in the previous chapter to nonconvex locally Lipschitz continuous functions. Since the classical directional derivative does not necessarily exist for locally Lipschitz continuous functions, we first define a generalized directional derivative. Then we generalize the subdifferential analogously. We use the approach of Clarke in a finite dimensional case. However, in addition to the Clarke subdifferential, many different generalizations of the concept of a subdifferential for nonconvex nonsmooth functions exist. At the end of this chapter we briefly recall some of them. More specifically we give definitions of the quasidifferential, the codifferential, the basic (limiting) and the singular subdifferentials.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 4. Optimality Conditions

Abstract

We present some results connecting the theories of nonsmooth analysis and optimization. We first define global and local minima of functions. After that, we generalize the classical first order optimality conditions for unconstrained nonsmooth optimization. Furthermore, we define linearizations for locally Lipschitz continuous functions by using subgradient information, and present their basic properties. These linearizations are suitable for function approximation. Finally, we define the notion of a descent direction and show how to find it for a locally Lipschitz continuous function.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 5. Generalized Convexities

Abstract

Convexity plays a crucial role in mathematical optimization theory. Especially, in duality theory and in constructing optimality conditions, convexity has been the most important concept since the basic reference by Rockafellar was published. Different types of generalized convexities have proved to be the main tool when constructing optimality conditions, particularly sufficient conditions for optimality. In this chapter, we analyze the properties of the generalized pseudo- and quasiconvexities for nondifferentiable locally Lipschitz continuous functions. The treatment is based on the Clarke subdifferentials and generalized directional derivatives.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 6. Approximations of Subdifferentials

Abstract

In practice, the computation of subdifferential is not an easy task. In this chapter, we first consider some families of set-valued mappings that can be used to approximate subdifferentials. Then we define the concept of a discrete gradient that can be used as an approximation of the subgradient at a given point. Finally, we introduce the notion of piecewise partially separable functions and study their properties. In particular, we describe how to calculate the discrete gradient for a piecewise partially separable function.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Backmatter

Nonsmooth Problems

Frontmatter

Chapter 7. Practical Problems

Abstract

In this chapter, we briefly describe several kinds of application problems which naturally have nonsmooth characteristics. These kinds of problems arise in computational chemistry and biology, optimal control, and data analysis, to mention but a few. The interested reader can find more details of each class of problem in the Notes and References at the end of the part.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 8. SemiAcademic Problems

Abstract

Using certain important methodologies for solving difficult smooth problems lead directly to the need to solve nonsmooth problems, which are either smaller in dimension or simpler in structure. The examples of this kind of methodological nonsmoothness are Lagrange relaxation, different decompositions, dual formulations, and exact penalty functions. In this chapter, we briefly describe some of these formulations. In addition, we represent the maximum eigenvalue problem that is an important part of many engineering design problems and graph theoretical applications. The interested reader may find more details of each problem class in the Notes and References at the end of Part II.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 9. Academic Problems

Abstract

Many practical optimization problems involve nonsmooth functions. In this chapter, we give an extensive collection of problems for nonsmooth minimization which can be and have been used to test the nonsmooth optimization software. We use a classification of test problems such that it is easy to pick up those problems that share features in interest. That is, for instance, convexity or nonconvexity, or min-max, piecewise quadratic or general polynomial objective function structure, etc.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Backmatter

Nonsmooth Optimization Methods

Frontmatter

Chapter 10. Subgradient Methods

Abstract

The history of subgradient methods (Kiev methods) starts in the 1960s and they were mainly developed in the Soviet Union. The basic idea behind subgradient methods is to generalize smooth methods by replacing the gradient with an arbitrary subgradient. Due to this simple structure, they are widely used NSO methods, although they may suffer from some serious drawbacks (this is true especially with the simplest versions of subgradient methods). The first method to be considered in this chapter is the cornerstone of NSO, the standard subgradient method. Then the ideas of the more sophisticated subgradient method, the well-known Shor’s r-algorithm are introduced.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 11. Cutting Plane Methods

Abstract

Subgradient methods described in the previous chapter use only one arbitrary subgradient (generalized gradient) at a time, without memory of past iterations. If the information from previous iterations is kept, it is possible to define a model—the so-called cutting plane model—of the objective function. In this way, more information about the local behavior of the function is obtained than what an individual arbitrary subgradient can yield. In this chapter, we first introduce the basic ideas of the standard cutting plane method and then the more advanced cutting plane method with proximity control.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 12. Bundle Methods

Abstract

At the moment, bundle methods are regarded as the most effective and reliable methods for nonsmooth optimization. They are based on the subdifferential theory developed by Rockafellar and Clarke, where the classical differential theory is generalized for convex and locally Lipschitz continuous functions, respectively. The basic idea of bundle methods is to approximate the subdifferential (that is, the set of subgradients) of the objective function by gathering subgradients from previous iterations into a bundle. In this way, more information about the local behavior of the function is obtained than what an individual arbitrary subgradient can yield. In this chapter, we first introduce the most frequently used bundle methods, that is, the proximal bundle and the bundle trust methods, and then we describe the basic ideas of the second order bundle-Newton method.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 13. Gradient Sampling Methods

Abstract

One of the newest approaches in general nonsmooth optimization is to use gradient sampling algorithms developed by Burke, Lewis, and Overton. The gradient sampling method is a method for minimizing an objective function that is locally Lipschitz continuous and smooth on an open dense subset of \(\mathbb {R}^n\). The objective may be nonsmooth and/or nonconvex. Gradient sampling methods may be considered as a stabilized steepest descent algorithm. The central idea behind these techniques is to approximate the subdifferential of the objective function through random sampling of gradients near the current iteration point. In this chapter, we introduce the original gradient sampling algorithm.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 14. Hybrid Methods

Abstract

In this chapter, we describe some methods that can be considered as hybrids of the classical nonsmooth optimization methods described before. The methods to be introduced are the variable metric bundle method and the quasi-secant method for solving general small- and medium-scale nonsmooth optimization problems; the modification of variable metric bundle method for solving large-scale nonsmooth optimization problems, that is, the limited memory bundle method; and the non-Euclidean restricted memory level method for extremely large-scale convex nonsmooth optimization problems.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 15. Discrete Gradient Methods

Abstract

In this chapter, we introduce two discrete gradient methods that can be considered as semi-derivative free methods in a sense that they do not use subgradient information and they do not approximate the subgradient but at the end of the solution process (i.e., near the optimal point). The introduced methods are the original discrete gradient method for small-scale nonsmooth optimization and its limited memory bundle version the limited memory discrete gradient bundle method for medium- and semi-large problems.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 16. Constraint Handling

Abstract

Until now we have mainly considered unconstrained optimization problems. However, many practical optimization problems have restrictions of some kind that can be modeled as constraint functions to the cost function. In this chapter, we introduce some common ways of dealing with nonsmooth constrained optimization. That is, exact penalty formulation and linearization.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Chapter 17. Numerical Comparison of NSO Softwares

Abstract

In this chapter we compare implementations of different nonsmooth optimization methods for solving unconstrained optimization problems. We test and compare different bundle methods and subgradient methods, as well as some methods that may be considered as a hybrid of these two and/or others, and two discrete gradient methods. All the tested methods have been described in the previous chapters. A broad set of nonsmooth optimization test problems is used for the testing purpose. The aim of this chapter is not to foreground one particular method over the others, but to obtain some insight on which method is suitable for certain types of problems.

Adil Bagirov, Napsu Karmitsa, Marko M. Mäkelä

Backmatter

Titel: Introduction to Nonsmooth Optimization
verfasst von: Adil Bagirov
Napsu Karmitsa
Marko M. Mäkelä
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-08114-4
Print ISBN: 978-3-319-08113-7
DOI: https://doi.org/10.1007/978-3-319-08114-4