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.     

Merit functions for nonsmooth complementarity problems and related descent algorithm

Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.     

Existence and Boundedness of the Kuhn-Tucker Multipliers in Nonsmooth Multiobjective Optimization

Using the idea of upper convexificators, we propose constraint qualifications and study existence and boundedness of the Kuhn-Tucker multipliers for a nonsmooth multiobjective optimization problem with inequality constraints and an arbitrary set constraint. We show that, at locally weak efficient solutions where the objective and constraint functions are locally Lipschitz, the constraint qualifications are necessary and sufficient conditions for the Kuhn-Tucker multiplier sets to be nonempty and bounded under certain semiregularity assumptions on the upper convexificators of the functions.     

A trust region algorithm for minimization of locally Lipschitzian functions

The classical trust region algorithm for smooth nonlinear programs is extended to the nonsmooth case where the objective function is only locally Lipschitzian. At each iteration, an objective function that carries both first and second order information is minimized over a trust region. The term that carries the first order information is an iteration function that may not explicitly depend on subgradients or directional derivatives. We prove that the algorithm is globally convergent. This convergence result extends the result of Powell for minimization of smooth functions, the result of Yuan for minimization of composite convex functions, and the result of Dennis, Li and Tapia for minimization of regular functions. In addition, compared with the recent model of Pang, Han and Rangaraj for minimization of locally Lipschitzian functions using a line search, this algorithm has the same convergence property without assuming positive definiteness and uniform boundedness of the second order term. Applications of the algorithm to various nonsmooth optimization problems are discussed.This author's work was supported in part by the Australian Research Council.This author's work was carried out while he was visiting the Department of Applied Mathematics at the University of New South Wales.     

Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

General constraint qualifications in nondifferentiable programming

We show that a familiar constraint qualification of differentiable programming has nonsmooth counterparts. As a result, necessary optimality conditions of Kuhn—Tucker type can be established for inequality-constrained mathematical programs involving functions not assumed to be differentiable, convex, or locally Lipschitzian. These optimality conditions reduce to the usual Karush—Kuhn—Tucker conditions in the differentiable case and sharpen previous results in the locally Lipschitzian case.     

Necessary optimality conditions for nonsmooth generalized semi-infinite programming problems

This paper is devoted to the study of nonsmooth generalized semi-infinite programming problems in which the index set of the inequality constraints depends on the decision vector and all emerging functions are assumed to be locally Lipschitz. We introduce a constraint qualification which is based on the Mordukhovich subdifferential. Then, we derive a Fritz–John type necessary optimality condition. Finally, interrelations between the new and the existing constraint qualifications such as the Mangasarian–Fromovitz, linear independent, and the Slater are investigated.     

Multiplier methods for optimization problems with Lipschitzian derivatives

Optimization problems for which the objective function and the constraints have locally Lipschitzian derivatives but are not assumed to be twice differentiable are examined. For such problems, analyses of the local convergence and the convergence rate of the multiplier (or the augmented Lagrangian) method and the linearly constraint Lagrangian method are given.     

Superlinearly convergent approximate Newton methods for LC1 optimization problems

In the literature, the proof of superlinear convergence of approximate Newton or SQP methods for solving nonlinear programming problems requires twice smoothness of the objective and constraint functions. Sometimes, the second-order derivatives of those functions are required to be Lipschitzian. In this paper, we present approximate Newton or SQP methods for solving nonlinear programming problems whose objective and constraint functions have locally Lipschitzian derivatives, and establishQ-superlinear convergence of these methods under the assumption that these derivatives are semismooth. This assumption is weaker than the second-order differentiability. The extended linear-quadratic programming problem in the fully quadratic case is an example of nonlinear programming problems whose objective functions have semismooth but not smooth derivatives.This work is supported by the Australian Research Council.This paper is dedicated to Professor O.L. Mangasarian on the occasion of his 60th birthday.     

Necessary optimality conditions for nonsmooth semi-infinite programming problems

In this paper, for a nonsmooth semi-infinite programming problem where the objective and constraint functions are locally Lipschitz, analogues of the Guignard, Kuhn-Tucker, and Cottle constraint qualifications are given. Pshenichnyi-Levin-Valadire property is introduced, and Karush-Kuhn-Tucker type necessary optimality conditions are derived.     

Solution Point Characterizations and Convergence Analysis of a Descent Algorithm for Nonsmooth Continuous Complementarity Problems

We consider a nonlinear complementarity problem defined by a continuous but not necessarily locally Lipschitzian map. In particular, we examine the connection between solutions of the problem and stationary points of the associated Fischer–Burmeister merit function. This is done by deriving a new necessary optimality condition and a chain rule formula for composite functions involving continuous maps. These results are given in terms of approximate Jacobians which provide the foundation for analyzing continuous nonsmooth maps. We also prove a result on the global convergence of a derivative-free descent algorithm for solving the complementarity problem. To this end, a concept of directional monotonicity for continuous maps is introduced.     

Convexificators and boundedness of the Kuhn–Tucker multipliers set

In this paper we consider a nonsmooth optimization problem with equality, inequality and set constraints. We propose new constraint qualifications and Kuhn–Tucker type necessary optimality conditions for this problem involving locally Lipschitz functions. The main tool of our approach is the notion of convexificators. We introduce a nonsmooth version of the Mangasarian–Fromovitz constraint qualification and show that this constraint qualification is necessary and sufficient for the Kuhn–Tucker multipliers set to be nonempty and bounded.     

A nonsmooth variant of the Mangasarian-Fromovitz constraint qualification

A unified view on constraint qualifications for nonsmooth equality and inequality constrained programs is presented. A fairly general constraint qualification for programs involving B-differential functions is given. Further specification to piecewise differentiable equality constraints and locally Lipschitz continuous inequality constraints yields a nonsmooth version of the Mangasarian-Fromovitz constraint qualification.This work was supported by the Deutsche Forschungsgemeinschaft, DFG-Grant No. Pa 219/5-1.     

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.     

The Compatibility with Order of Some Subdifferentials

It is well known that elementary subdifferentials which are the simplest and the most precise among known subdifferentials do not enjoy good calculus rules, whereas more elaborated subdifferentials do have calculus rules but are not as precise and, in particular, do not preserve order. This paper explores an order preservation property for the subdifferentials of the second category. This property concerns the case in which a distance function is involved. It emphasizes the crucial role played by such functions in nonsmooth analysis. The result enables one to get in a simple, unified way the passage from the properties of subdifferentials for Lipschitzian functions to the same properties for the case of lower semicontinuous functions.     

On Constraint Qualifications and Sensitivity Analysis for General Optimization Problems via Pseudo-Jacobians

A nonsmooth and nonconvex general optimization problem is considered. Using the idea of pseudo-Jacobians, nonsmooth versions of the Robinson and Mangasarian–Fromovitz constraint qualifications are defined and relationships between them and the local error bound property are investigated. A new necessary optimality condition, based on the pseudo-Jacobians, is derived under the local error bound constraint qualification. These results are applied for computing and estimating the Fréchet and limiting subdifferentials of value functions. Moreover, several examples are provided to clarify the obtained results.     

非光滑方程组牛顿法的全局收敛性分析

通过定义一种新的*-微分,本文给出了局部Lipschitz非光滑方程组的牛顿法,并对其全局收敛性进行了研究.该牛顿法结合了非光滑方程组的局部收敛性和全局收敛性.最后,我们把这种牛顿法应用到非光滑函数的光滑复合方程组问题上,得到了较好的收敛性.     

On solving simple bilevel programs with a nonconvex lower level program

In this paper, we consider a simple bilevel program where the lower level program is a nonconvex minimization problem with a convex set constraint and the upper level program has a convex set constraint. By using the value function of the lower level program, we reformulate the bilevel program as a single level optimization problem with a nonsmooth inequality constraint and a convex set constraint. To deal with such a nonsmooth and nonconvex optimization problem, we design a smoothing projected gradient algorithm for a general optimization problem with a nonsmooth inequality constraint and a convex set constraint. We show that, if the sequence of penalty parameters is bounded then any accumulation point is a stationary point of the nonsmooth optimization problem and, if the generated sequence is convergent and the extended Mangasarian-Fromovitz constraint qualification holds at the limit then the limit point is a stationary point of the nonsmooth optimization problem. We apply the smoothing projected gradient algorithm to the bilevel program if a calmness condition holds and to an approximate bilevel program otherwise. Preliminary numerical experiments show that the algorithm is efficient for solving the simple bilevel program.