Generalized Derivatives of Lexicographic Linear Programs

Lexicographic linear programs are fixed-priority multiobjective linear programs that are a useful model of biological systems using flux balance analysis and for goal-programming problems. The objective function values of a lexicographic linear program as a function of its right-hand side are nonsmooth. This work derives generalized derivative information for lexicographic linear programs using lexicographic directional derivatives to obtain elements of the Bouligand subdifferential (limiting Jacobian). It is shown that elements of the limiting Jacobian can be obtained by solving related linear programs. A nonsmooth equation-solving problem is solved to illustrate the benefits of using elements of the limiting Jacobian of lexicographic linear programs.     

Adaptive Smoothing Method,Deterministically Computable Generalized Jacobians,and the Newton Method

In this note, we show that a well-known integral method, which was used by Mayne and Polak to compute an -subgradient, can be exploited to compute deterministically an element of the plenary hull of the Clarke generalized Jacobian of a locally Lipschitz mapping regardless of its structure. In particular, we show that, when a locally Lipschitz mapping is piecewise smooth, we are able to compute deterministically an element of the Clarke generalized Jacobian by the adaptive smoothing method. Consequently, we show that the Newton method based on the plenary hull of the Clarke generalized Jacobian can be implemented in a deterministic way for solving Lipschitz nonsmooth equations.     

Stability of the Solution Set of Perturbed Nonsmooth Inequality Systems and Application

Stability properties of the solution set of generalized inequality systems with locally Lipschitz functions are obtained under a regularity condition on the generalized Jacobian and the Clarke tangent cone. From these results, we derive sufficient conditions for the optimal value function in a nonsmooth optimization problem to be continuous or locally Lipschitz at a given parameter.     

Generalized sensitivity analysis of nonlinear programs using a sequence of quadratic programs

ABSTRACT

Local sensitivity information is obtained for KKT points of parametric NLPs that may exhibit active set changes under parametric perturbations; under appropriate regularity conditions, computationally relevant generalized derivatives of primal and dual variable solutions of parametric NLPs are calculated. Ralph and Dempe obtained directional derivatives of solutions of parametric NLPs exhibiting active set changes from the unique solution of an auxiliary quadratic program. This article uses lexicographic directional derivatives, a newly developed tool in nonsmooth analysis, to generalize the classical NLP sensitivity analysis theory of Ralph and Dempe. By viewing said auxiliary quadratic program as a parametric NLP, the results of Ralph and Dempe are applied to furnish a sequence of coupled QPs, whose unique solutions yield generalized derivative information for the NLP. A practically implementable algorithm is provided. The theory developed here is motivated by widespread applications of nonlinear programming sensitivity analysis, such as in dynamic control and optimization problems.     

The generalized jacobian of the optimal solution in parametric optimization

If a strong sufficient optimality condition of second order together with the Mangasarian-Fromowitz and the constant rank constraint qualifications are: satisfied for a parametric optimization problem, then a local optimal solution is strongly stable in the sense of Kojima and the corresponding optimal solution function is locally Lipschitz continuous. In the article the possibilities for the computation of the generalized Jacobian of this function are discussed. We will give formulae for the guaranteed computation of the entire generalized Jacobian, provided that an additional assumption is satisfied. An example will show its necessity. Unfortunately, this assumption is difficult to be verified. Without it, at least one element of the generalized Jacobian can be computed with non-polynomial complexity in the worst case. Using a uniforrn distribution in the parameter space, a last approach yields one of them with probability one in polynomial time     

Lexicographic differentiation of nonsmooth functions

We present a survey on the results related to the theory of lexicographic differentiation. This theory ensures an efficient computation of generalized (lexicographic) derivative of a nonsmooth function belonging to a special class of lexicographically smooth functions. This class is a linear space which contains all differentiable functions, all convex functions, and which is closed with respect to component-wise composition of the members. In order to define lexicographic derivative in a unique way, it is enough to fix a basis in the space of variables. Lexicographic derivatives can be used in black-box optimization methods. We give some examples of applications of these derivatives in analysis of nonsmooth functions. It is shown that the system of lexicographic derivatives along a fixed basis correctly represents corresponding nonsmooth function (Newton-Leibnitz formula). We present nonsmooth versions of standard theorems on potentiality of nonlinear operators, on differentiation of parametric integrals and on differentiation of functional sequences. Finally, we show that an appropriately defined lexicographic subdifferential ensures a more rigorous selection of a candidate optimal solution than the subdifferential of Clarke. Dedicated to R. T. Rockafellar on his 70th birthday. This paper presents research results of the Belgian Program on Interuniversity Attraction Poles, initiated by the Belgian Federal Science Policy Office. The scientific responsibility rests with its author.     

On constraint qualifications in terms of approximate Jacobians for nonsmooth continuous optimization problems

Constraint qualifications in terms of approximate Jacobians are investigated for a nonsmooth constrained optimization problem, in which the involved functions are continuous but not necessarily locally Lipschitz. New constraint qualifications in terms of approximate Jacobians, weaker than the generalized Robinson constraint qualification (GRCQ) in Jeyakumar and Yen [V. Jeyakumar, N.D. Yen, Solution stability of nonsmooth continuous systems with applications to cone-constrained optimization, SIAM J. Optim. 14 5 (2004) 1106-1127], are introduced and some examples are provided to show the utility of constrained qualifications introduced. Since the calmness condition is regarded as the basic condition for optimality conditions, the relationships between the constraint qualifications proposed and the calmness of solution mapping are also studied.     

参数非光滑优化的微分稳定性

本文研究了含有向量参数的非光滑优化问题的极值函数或叫做边缘函数的连续性及某种意义下的微分性质。给出了目标函数及不等式约束为李普希兹函数,等式约束为连续可微函数,并且带有闭凸约束集C的非凸非光滑问题的最优值函数的几种方向导数的界,把[4],[1]中关于一个参数的单边扰动推广到向量参数的扰动,亦可认为是把[2]由光滑函数类推广到李普希兹函数类。     

On Minty variational principle for nonsmooth vector optimization problems with generalized approximate convexity

In this paper, we consider a nonsmooth vector optimization problem involving locally Lipschitz generalized approximate convex functions and find some relations between approximate convexity and generalized approximate convexity. We establish relationships between vector variational inequalities and nonsmooth vector optimization problem using the generalized approximate convexity as a tool.     

On necessary and sufficient optimality conditions for multicriterial optimization problems

In this paper we derive first order necessary and sufficient optimality conditions for nonsmooth optimization problems with multiple criteria. These conditions are given for different optimality notions (i.e. weak, Pareto- and proper minimality) and for different types of derivatives of nonsmooth objective functions (locally Lipschitz continuous and quasidifferentiable) mappings. The conditions are given, if possible, in terms of a derivative and a subdifferential of those mappings.     

The application of the nonsmooth critical point theory to the stationary electrorheological fluids

In this paper, we prove the existence of variational solutions to systems modeling electrorheological fluids in the stationary case. Our method of proof is based on the nonsmooth critical point theory for locally Lipschitz functional and the properties of the generalized Lebesgue–Sobolev space.     

Nonsmooth Semi-infinite Multiobjective Optimization Problems

We apply some advanced tools of variational analysis and generalized differentiation to establish necessary conditions for (weakly) efficient solutions of a nonsmooth semi-infinite multiobjective optimization problem (SIMOP for brevity). Sufficient conditions for (weakly) efficient solutions of a SIMOP are also provided by means of introducing the concepts of (strictly) generalized convex functions defined in terms of the limiting subdifferential of locally Lipschitz functions. In addition, we propose types of Wolfe and Mond–Weir dual problems for SIMOPs, and explore weak and strong duality relations under assumptions of (strictly) generalized convexity. Examples are also designed to analyze and illustrate the obtained results.     

Convex composite non–Lipschitz programming

In this paper necessary, and sufficient optimality conditions are established without Lipschitz continuity for convex composite continuous optimization model problems subject to inequality constraints. Necessary conditions for the special case of the optimization model involving max-min constraints, which frequently arise in many engineering applications, are also given. Optimality conditions in the presence of Lipschitz continuity are routinely obtained using chain rule formulas of the Clarke generalized Jacobian which is a bounded set of matrices. However, the lack of derivative of a continuous map in the absence of Lipschitz continuity is often replaced by a locally unbounded generalized Jacobian map for which the standard form of the chain rule formulas fails to hold. In this paper we overcome this situation by constructing approximate Jacobians for the convex composite function involved in the model problem using ε-perturbations of the subdifferential of the convex function and the flexible generalized calculus of unbounded approximate Jacobians. Examples are discussed to illustrate the nature of the optimality conditions. Received: February 2001 / Accepted: September 2001?Published online February 14, 2002     

A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems

We prove a new local upper Lipschitz stability result and the associated local error bound for solutions of parametric Karush–Kuhn–Tucker systems corresponding to variational problems with Lipschitzian base mappings and constraints possessing Lipschitzian derivatives, and without any constraint qualifications. This property is equivalent to the appropriately extended to this nonsmooth setting notion of noncriticality of the Lagrange multiplier associated to the primal solution, which is weaker than second-order sufficiency. All this extends several results previously known only for optimization problems with twice differentiable data, or assuming some constraint qualifications. In addition, our results are obtained in the more general variational setting.     

An Uniparametric Secant–Type Method for Nonsmooth Generalized Equations

We are concerned with the problem of approximating a locally unique solution of a nonsmooth generalized equation in Banach spaces using an uniparametric Secant–type method. We provide a local convergence analysis under ω–conditioned divided difference which generalizes the usual Lipschitz continuous and Hölder continuous conditions used in [14].     

基于向量Liapunov函数不连续系统的稳定性研究

基于局部Lipschitz连续且正则(Clarke意义下)的向量Liapunov函数,讨论不连续自治系统的稳定性(Filippov解意义下)．通过定义一类新的向量Liapunov函数的“集值导数”,给出了关于不连续系统的广义比较原理．基于Lipschitz连续且正则的向量Liapunov函数,进一步的给出不连续自治系统的Liapunov稳定性定理．     

Characterizing the Single-Valuedness of Multifunctions

We characterize the local single-valuedness and continuity of multifunctions (set-valued mappings) in terms of their premonotonicity and lower semicontinuity. This result completes the well-known fact that lower semicontinuous, monotone multifunctions are single-valued and continuous. We also show that a multifunction is actually a Lipschitz single-valued mapping if and only if it is premonotone and has a generalized Lipschitz property called Aubin continuity. The possible single-valuedness and continuity of multifunctions is at the heart of some of the most fundamental issues in variational analysis and its application to optimization. We investigate the impact of our characterizations on several of these issues; discovering exactly when certain generalized subderivatives can be identified with classical derivatives, and determining precisely when solutions to generalized variational inequalities are locally unique and Lipschitz continuous. As an application of our results involving generalized variational inequalities, we characterize when the Karush–Kuhn–Tucker pairs associated with a parameterized optimization problem are locally unique and Lipschitz continuous.     

Optimality Conditions for Bilevel Vector Optimization Problems with a Variable Ordering Structure

The article is concerned with the optimistic formulation of a multiobjective bilevel optimization problem with locally Lipschitz continuous inclusion constraints. Using a variable ordering structure defined by a Bishop–Phelps cone, we investigate necessary optimality conditions for locally weakly nondominated solutions. Reducing the problem into a one-level nonlinear and nonsmooth program, we use the extremal principle by Mordukhovich to get fuzzy optimality conditions. More explicit conditions with the initial data are obtained using both the Ekeland’s variational principle and the support function. Fortunately, the Lipschitz property of a set-valued mapping is conserved for its support function. An appropriate regularity condition is given to help us discern the Lagrange-Kuhn-Tucker multipliers.     

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.     

EXISTENCE OF PERIODIC SOLUTIONS FOR A DIFFERENTIAL INCLUSION SYSTEMS INVOLVING THE p（t）-LAPLACIAN

We study a nonlinear periodic problem driven by the p(t)-Laplacian and having a nonsmooth potential (hemivariational inequalities). Using a variational method based on nonsmooth critical point theory for locally Lipschitz functions, we first prove the existence of at least two nontrivial solutions under the generalized subquadratic and then establish the existence of at least one nontrivial solution under the generalized superquadratic.