Generalized derivatives and nonsmooth optimization, a finite dimensional tour

During the early 1960’s there was a growing realization that a large number of optimization problems which appeared in applications involved minimization of non-differentiable functions. One of the important areas where such problems appeared was optimal control. The subject of nonsmooth analysis arose out of the need to develop a theory to deal with the minimization of nonsmooth functions. The first impetus in this direction came with the publication of Rockafellar’s seminal work titledConvex Analysis which was published by the Princeton University Press in 1970. It would be impossible to overstate the impact of this book on the development of the theory and methods of optimization. It is also important to note that a large part of convex analysis was already developed by Werner Fenchel nearly twenty years earlier and was circulated through his mimeographed lecture notes titledConvex Cones, Sets and Functions, Princeton University, 1951. In this article we trace the dramatic development of nonsmooth analysis and its applications to optimization in finite dimensions. Beginning with the fundamentals of convex optimization we quickly move over to the path breaking work of Clarke which extends the domain of nonsmooth analysis from convex to locally Lipschitz functions. Clarke was the second doctoral student of R.T. Rockafellar. We discuss the notions of Clarke directional derivative and the Clarke generalized gradient and also the relevant calculus rules and applications to optimization. While discussing locally Lipschitz optimization we also try to blend in the computational aspects of the theory wherever possible. This is followed by a discussion of the geometry of sets with nonsmooth boundaries. The approach to develop the notion of the normal cone to an arbitrary set is sequential in nature. This approach does not rely on the standard techniques of convex analysis. The move away from convexity was pioneered by Mordukhovich and later culminated in the monographVariational Analysis by Rockafellar and Wets. The approach of Mordukhovich relied on a nonconvex separation principle called theextremal principle while that of Rockafellar and Wets relied on various convergence notions developed to suit the needs of optimization. We then move on to a parallel development in nonsmooth optimization due to Demyanov and Rubinov called Quasidifferentiable optimization. They study the class of directionally differentiable functions whose directional derivatives can be represented as a difference of two sublinear functions. On other hand the directional derivative of a convex function and also the Clarke directional derivatives are sublinear functions of the directions. Thus it was thought that the most useful generalizations of directional derivatives must be a sublinear function of the directions. Thus Demyanov and Rubinov made a major conceptual change in nonsmooth optimization. In this section we define the notion of a quasidifferential which is a pair of convex compact sets. We study some calculus rules and their applications to optimality conditions. We also study the interesting notion of Demyanov difference between two sets and their applications to optimization. In the last section of this paper we study some second-order tools used in nonsmooth analysis and try to see their relevance in optimization. In fact it is important to note that unlike the classical case, the second-order theory of nonsmoothness is quite complicated in the sense that there are many approaches to it. However we have chosen to describe those approaches which can be developed from the first order nonsmooth tools discussed here. We shall present three different approaches, highlight the second order calculus rules and their applications to optimization.     

Directional derivatives of difference functions of nonsmooth max-functions

In this paper, we give an upper estimate for the Clarke-Rockafellar directional derivatives of a function of the form f - g, where f, g are max-functions defined by locally Lipschitz but not necessarily differentiable functions on a closed convex set in a Euclidean space. As an application, we give a sufficient condition for f - g to have an error bound.     

Abstract cone approximations and generalized differentiability in nonsmooth optimization

In the present paper a connection between cone approximations of sets and generalized differentiability notions will be given. Using both conceptions we present an approach to derive necessary optimality conditions for optimization problems with inequality constraints. Moreover, several constraint qualifications are proposed to get Kuhn-Tucker-type-conditions.     

Second-order optimality conditions in set-valued optimization via asymptotic derivatives

In this article we give new second-order optimality conditions in set-valued optimization. We use the second-order asymptotic tangent cones to define second-order asymptotic derivatives and employ them to give the optimality conditions. We extend the well-known Dubovitskii–Milutin approach to set-valued optimization to express the optimality conditions given as an empty intersection of certain cones in the objective space. We also use some duality arguments to give new multiplier rules. By following the more commonly adopted direct approach, we also give optimality conditions in terms of a disjunction of certain cones in the image space. Several particular cases are discussed.     

First-order optimality conditions in set-valued optimization

A a set-valued optimization problem min _C F(x), x ∈X ₀, is considered, where X ₀ ⊂ X, X and Y are normed spaces, F: X ₀ ⊂ Y is a set-valued function and C ⊂ Y is a closed cone. The solutions of the set-valued problem are defined as pairs (x ⁰,y ⁰), y ⁰ ∈F(x ⁰), and are called minimizers. The notions of w-minimizers (weakly efficient points), p-minimizers (properly efficient points) and i-minimizers (isolated minimizers) are introduced and characterized through the so called oriented distance. The relation between p-minimizers and i-minimizers under Lipschitz type conditions is investigated. The main purpose of the paper is to derive in terms of the Dini directional derivative first order necessary conditions and sufficient conditions a pair (x ⁰, y ⁰) to be a w-minimizer, and similarly to be a i-minimizer. The i-minimizers seem to be a new concept in set-valued optimization. For the case of w-minimizers some comparison with existing results is done.     

Lagrange optimality system for a class of nonsmooth convex optimization

In this paper, we revisit the augmented Lagrangian method for a class of nonsmooth convex optimization. We present the Lagrange optimality system of the augmented Lagrangian associated with the problems, and establish its connections with the standard optimality condition and the saddle point condition of the augmented Lagrangian, which provides a powerful tool for developing numerical algorithms: we derive a Lagrange–Newton algorithm for the nonsmooth convex optimization, and establish the nonsingularity of the Newton system and the local convergence of the algorithm.     

Approximate first-order and second-order directional derivatives of a marginal function in convex optimization

Given a convex functionf: ^p × ^q (–, +], the marginal function is defined on ^p by (x)=inf{f(x, y)|y ^q }. Our purpose in this paper is to express the approximate first-order and second-order directional derivatives of atx ₀ in terms of those off at (x ₀,y ₀), wherey ₀ is any element for which (x ₀)=f(x ₀,y ₀).The author is indebted to one referee for pointing out an inaccuracy in an earlier version of Theorem 4.1.     

Necessary optimality conditions in an abnormal optimization problem with equality constraints

An abnormal minimization problem with equality constraints and a finite-dimensional image is examined. Second-order necessary conditions for this problem are given that strengthen previously known results.     

Generalized second-order directional derivatives and optimization with C1,1 functions

In this paper, a new generalized second-order directional derivative and a set-valued generalized Hessian are introudced for C¹,¹ functions in real Banach spaces. It is shown that this set-valued generalized Hessian is single-valued at a point if and only if the function is twice weakly Gãteaux differentiable at the point and that the generalized second-order directional derivative is upper semi-continuous under a regularity condition. Various generalized calculus rules are also given for C^1,1 functions. The generalized second-order directional derivative is applied to derive second-order necessary optirnality conditions for mathematical programming problems.     

Separate Necessary and Sufficient Conditions for the Local Minimum of a Function

This paper develops two necessary conditions for a local minimum of an arbitrary extended real-valued function (Theorem 2.2) and, quite separately, two conditions, each sufficient for such a function to have a strict local minimum (Theorem 2.3).This work was supported by the National Science Foundation of China, Grant 10171034, and the Natural Science Foundation of the Department of Education of Guangdong Province, Grant 820138.The author thanks the referees for helpful comments.     

First and second order sufficient conditions for strict minimality in nonsmooth vector optimization

In this paper we present first and second order sufficient conditions for strict local minima of orders 1 and 2 to vector optimization problems with an arbitrary feasible set and a twice directionally differentiable objective function. With this aim, the notion of support function to a vector problem is introduced, in such a way that the scalar case and the multiobjective case, in particular, are contained. The obtained results extend the multiobjective ones to this case. Moreover, specializing to a feasible set defined by equality, inequality, and set constraints, first and second order sufficient conditions by means of Lagrange multiplier rules are established.     

Multiple subgradient descent bundle method for convex nonsmooth multiobjective optimization

The aim of this paper is to propose a new multiple subgradient descent bundle method for solving unconstrained convex nonsmooth multiobjective optimization problems. Contrary to many existing multiobjective optimization methods, our method treats the objective functions as they are without employing a scalarization in a classical sense. The main idea of this method is to find descent directions for every objective function separately by utilizing the proximal bundle approach, and then trying to form a common descent direction for every objective function. In addition, we prove that the method is convergent and it finds weakly Pareto optimal solutions. Finally, some numerical experiments are considered.     

Unsupervised and supervised data classification via nonsmooth and global optimization

We examine various methods for data clustering and data classification that are based on the minimization of the so-called cluster function and its modications. These functions are nonsmooth and nonconvex. We use Discrete Gradient methods for their local minimization. We consider also a combination of this method with the cutting angle method for global minimization. We present and discuss results of numerical experiments. This research was supported by the Australian Research Council.     

CONE-DIRECTED CONTINGENT DERIVATIVES AND GENERALIZED PREINVEX SET-VALUED OPTIMIZATION

By using cone-directed contingent derivatives, the unified necessary and suffi-cient optimality conditions are given for weakly and strongly minimal elements respectively in generalized preinvex set valued optimization.     

一类非光滑多目标规划问题的最优性条件

研究了一类非光滑多目标规划问题.这类多目标规划问题的目标函数为锥凸函数与可微函数之和,其约束条件是Euclidean空间中的锥约束.在满足广义Abadie约束规格下,利用广义Farkas引理和多目标函数标量化,给出了这一类多目标规划问题的锥弱有效解最优性必要条件.     

求解非光滑凸规划的一种混合束方法

提出一种求解非光滑凸规划问题的混合束方法. 该方法通过对目标函数增加迫近项, 且对可行域增加信赖域约束进行迭代, 做为迫近束方法与信赖域束方法的有机结合, 混合束方法自动在二者之间切换, 收敛性分析表明该方法具有全局收敛性. 最后的数值算例验证了算法的有效性．     

Second-Order Optimality Conditions in Set Optimization

In this paper, we propose second-order epiderivatives for set-valued maps. By using these concepts, second-order necessary optimality conditions and a sufficient optimality condition are given in set optimization. These conditions extend some known results in optimization.The authors are grateful to the referees for careful reading and helpful remarks.     

Optimality conditions for nonsmooth mathematical programs with equilibrium constraints,using convexificators

In this paper, we deal with constraint qualifications, stationary concepts and optimality conditions for a nonsmooth mathematical program with equilibrium constraints (MPEC). The main tool in our study is the notion of convexificator. Using this notion, standard and MPEC Abadie and several other constraint qualifications are proposed and a comparison between them is presented. We also define nonsmooth stationary conditions based on the convexificators. In particular, we show that GS-stationary is the first-order optimality condition under generalized standard Abadie constraint qualification. Finally, sufficient conditions for global or local optimality are derived under some MPEC generalized convexity assumptions.     

Second-order optimality conditions for minimizing a max-function

We study Chaney's and Ben-Tal-Zowe's second-order directional derivatives with applications in minimization problem for max-functions of the formh(x): = max {f(x, τ); τ ∈T},where T is a compact metricspace. We improve Kawasaki's result on necessary condition for such functions in the minimization problem.