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.     

A Shooting Algorithm for Optimal Control Problems with Singular Arcs

In this article, we propose a shooting algorithm for a class of optimal control problems for which all control variables appear linearly. The shooting system has, in the general case, more equations than unknowns and the Gauss–Newton method is used to compute a zero of the shooting function. This shooting algorithm is locally quadratically convergent, if the derivative of the shooting function is one-to-one at the solution. The main result of this paper is to show that the latter holds whenever a sufficient condition for weak optimality is satisfied. We note that this condition is very close to a second order necessary condition. For the case when the shooting system can be reduced to one having the same number of unknowns and equations (square system), we prove that the mentioned sufficient condition guarantees the stability of the optimal solution under small perturbations and the invertibility of the Jacobian matrix of the shooting function associated with the perturbed problem. We present numerical tests that validate our method.     

An Ulm-Like Cayley Transform Method for Inverse Eigenvalue Problems with Multiple Eigenvalues

We study the convergence of an Ulm-like Cayley transform method for solving inverse eigenvalue problems which avoids solving approximate Jacobian equations. Under the nonsingularity assumption of the relative generalized Jacobian matrices at the solution, a convergence analysis covering both the distinct and multiple eigenvalues cases is provided and the quadratical convergence is proved. Moreover, numerical experiments are given in the last section to illustrate our results.     

Reduced Functions, Gradients and Hessians from Fixed-Point Iterations for State Equations

In design optimization and parameter identification, the objective, or response function(s) are typically linked to the actually independent variables through equality constraints, which we will refer to as state equations. Our key assumption is that it is impossible to form and factor the corresponding constraint Jacobian, but one has instead some fixed-point algorithm for computing a feasible state, given any reasonable value of the independent variables. Assuming that this iteration is eventually contractive, we will show how reduced gradients (Jacobians) and Hessians (in other words, the total derivatives) of the response(s) with respect to the independent variables can be obtained via algorithmic, or automatic, differentiation (AD). In our approach the actual application of the so-called reverse, or adjoint differentiation mode is kept local to each iteration step. Consequently, the memory requirement is typically not unduly enlarged. The resulting approximating Lagrange multipliers are used to compute estimates of the reduced function values that can be shown to converge twice as fast as the underlying state space iteration. By a combination with the forward mode of AD, one can also obtain extra-accurate directional derivatives of the reduced functions as well as feasible state space directions and the corresponding reduced or projected Hessians of the Lagrangian. Our approach is verified by test calculations on an aircraft wing with two responses, namely, the lift and drag coefficient, and two variables, namely, the angle of attack and the Mach number. The state is a 2-dimensional flow field defined as solution of the discretized Euler equation under transonic conditions.     

A New Pareto Optimal Solution in a Lagrange Decomposable Multi-Objective Optimization Problem

In this paper a committee decision-making process of a convex Lagrange decomposable multi-objective optimization problem, which has been decomposed into various subproblems, is studied. Each member of the committee controls only one subproblem and attempts to select the optimal solution of this subproblem most desirable to him, under the assumption that all the constraints of the total problem are satisfied. This procedure leads to a new solution concept of a Lagrange decomposable multi-objective optimization problem, called a preferred equilibrium set. A preferred equilibrium point of a problem, for a committee, may or may not be a Pareto optimal point of this problem. In some cases, a non-Pareto optimal preferred equilibrium point of a problem, for a committee, can be considered as a special type of Pareto optimal point of this problem. This fact leads to a generalization of the Pareto optimality concept in a problem.     

PICARD ITERATION FOR NONSMOOTH EQUATIONS

1. IntroductionConsider the following nonsmooth equationsF(x) = 0 (l)where F: R" - R" is LipsChitz continuous. A lot of work has been done and is bellg doneto deal with (1). It is basicly a genera1ization of the cIassic Newton method [8,10,11,14],Newton-lthe methods[1,18] and quasiNewton methods [6,7]. As it is discussed in [7], the latter,quasiNewton methods, seem to be lindted when aPplied to nonsmooth caJse in that a boundof the deterioration of uPdating matrir can not be maintained w…     

Set-valued approximations and Newton’s methods

n to R^m. Under the assumption of semi-smoothness of the mapping, we prove that the approximation can be obtained through the Clarke generalized Jacobian, Ioffe-Ralph generalized Jacobian, B-subdifferential and their approximations. As an application, we propose a generalized Newton’s method based on the point-based set-valued approximation for solving nonsmooth equations. We show that the proposed method converges locally superlinearly without the assumption of semi-smoothness. Finally we include some well-known generalized Newton’s methods in our method and consolidate the convergence results of these methods. Received October 2, 1995 / Revised version received May 5, 1998 Published online October 9, 1998     

Moreau–Yosida regularization of Lagrangian-dual functions for a class of convex optimization problems

In this paper, we consider the Lagrangian dual problem of a class of convex optimization problems, which originates from multi-stage stochastic convex nonlinear programs. We study the Moreau–Yosida regularization of the Lagrangian-dual function and prove that the regularized function η is piecewise C ², in addition to the known smoothness property. This property is then used to investigate the semismoothness of the gradient mapping of the regularized function. Finally, we show that the Clarke generalized Jacobian of the gradient mapping is BD-regular under some conditions.      

The non-interior continuation methods for solving theP0 function nonlinear complementarity problem

In this paper, we propose a new smooth function that possesses a property not satisfied by the existing smooth functions. Based on this smooth function, we discuss the existence and continuity of the smoothing path for solving theP ₀ function nonlinear complementarity problem ( NCP). Using the characteristics of the new smooth function, we investigate the boundedness of the iteration sequence generated by the non-interior continuation methods for solving theP ₀ function NCP under the assumption that the solution set of the NCP is nonempty and bounded. We show that the assumption that the solution set of the NCP is nonempty and bounded is weaker than those required by a few existing continuation methods for solving the NCP     

A Nonsmooth L-M Method for Solving the Generalized Nonlinear Complementarity Problem over a Polyhedral Cone

In this paper the generalized nonlinear complementarity problem (GNCP) defined on a polyhedral cone is reformulated as a system of nonsmooth equations. Based on this reformulation, the famous Levenberg-Marquardt (L-M) algorithm is employed to obtain its solution. Theoretical results that relate the stationary points of the merit function to the solution of the GNCP are presented. Under mild assumptions, we show that the L-M algorithm is both globally and superlinearly convergent. Moreover, a method to calculate a generalized Jacobian is given and numerical experimental results are presented.     

Note on inventory model with a mixture of back orders and lost sales

Competitiveness is an important means of determining whether a company will prosper. Business organizations compete with one another in a variety of ways. Among these competitive methods are time and cost factors. The purpose of this paper is to examine the inventory models presented by Padmanabhan and Vrat [International Journal of Systems Sciences 21 (1990) 1721] with a mixture of back orders and lost sales. We develop the criterion for the optimal solution for the total cost function. If the criterion is not satisfied, this model will degenerate into one cycle inventory model with a finite inventory period. This implies an extension of shortage period as long as possible to produce lower cost. However, we know that time is another important factor in company competitiveness. Customers will not indefinitely wait for back orders. A tradeoff will be made between the two most important factors; time and cost. The minimum total cost is evaluated under the diversity cycle time and illustrations are applied to explain the calculation process. This work provides a reference for decision-makers.     

Pointwise convergence of Fourier regularization for smoothing data

The classical smoothing data problem is analyzed in a Sobolev space under the assumption of white noise. A Fourier series method based on regularization endowed with generalized cross validation is considered to approximate the unknown function. This approximation is globally optimal, i.e., the mean integrated squared error reaches the optimal rate in the minimax sense. In this paper the pointwise convergence property is studied. Specifically, it is proved that the smoothed solution is locally convergent but not locally optimal. Examples of functions for which the approximation is subefficient are given. It is shown that optimality and superefficiency are possible when restricting to more regular subspaces of the Sobolev space.     

Convergence rates in ℓ1-regularization when the basis is not smooth enough

Sparsity promoting regularization is an important technique for signal reconstruction and several other ill-posed problems. Theoretical investigation typically bases on the assumption that the unknown solution has a sparse representation with respect to a fixed basis. We drop this sparsity assumption and provide error estimates for nonsparse solutions. After discussing a result in this direction published earlier by one of the authors and co-authors, we prove a similar error estimate under weaker assumptions. Two examples illustrate that this set of weaker assumptions indeed covers additional situations which appear in applications.     

Generalized Derivatives for Solutions of Parametric Ordinary Differential Equations with Non-differentiable Right-Hand Sides

Sensitivity analysis provides useful information for equation-solving, optimization, and post-optimality analysis. However, obtaining useful sensitivity information for systems with nonsmooth dynamic systems embedded is a challenging task. In this article, for any locally Lipschitz continuous mapping between finite-dimensional Euclidean spaces, Nesterov’s lexicographic derivatives are shown to be elements of the plenary hull of the (Clarke) generalized Jacobian whenever they exist. It is argued that in applications, and in several established results in nonsmooth analysis, elements of the plenary hull of the generalized Jacobian of a locally Lipschitz continuous function are no less useful than elements of the generalized Jacobian itself. Directional derivatives and lexicographic derivatives of solutions of parametric ordinary differential equation (ODE) systems are expressed as the unique solutions of corresponding ODE systems, under Carathéodory-style assumptions. Hence, the scope of numerical methods for nonsmooth equation-solving and local optimization is extended to systems with nonsmooth parametric ODEs embedded.     

Bundle Trust-Region Algorithm for Bilinear Bilevel Programming

The bilevel programming problem (BLPP) is equivalent to a two-person Stackelberg game in which the leader and follower pursue individual objectives. Play is sequential and the choices of one affect the choices and attainable payoffs of the other. The purpose of this paper is to investigate an extension of the linear BLPP where the objective functions of both players are bilinear. To overcome certain discontinuities in the master problem, a regularized term is added to the follower objective function. Using ideas from parametric programming, the generalized Jacobian and the pseudodifferential of the regularized follower solution function are computed. This allows us to develop a bundle trust-region algorithm. Convergence analysis of the proposed methodology is given.     

An Objective Penalty Function of Bilevel Programming

Penalty methods are very efficient in finding an optimal solution to constrained optimization problems. In this paper, we present an objective penalty function with two penalty parameters for inequality constrained bilevel programming under the convexity assumption to the lower level problem. Under some conditions, an optimal solution to a bilevel programming defined by the objective penalty function is proved to be an optimal solution to the original bilevel programming. Moreover, based on the objective penalty function, an algorithm is developed to obtain an optimal solution to the original bilevel programming, with its convergence proved under some conditions.     

Analog of the Liouville Equation and BBGKY Hierarchy for a System of Hard Spheres with Inelastic Collisions

Dynamics of a system of hard spheres with inelastic collisions is investigated. This system is a model for granular flow. The map induced by a shift along the trajectory does not preserve the volume of the phase space, and the corresponding Jacobian is different from one. A special distribution function is defined as the product of the usual distribution function and the squared Jacobian. For this distribution function, the Liouville equation with boundary condition is derived. A sequence of correlation functions is defined for canonical and grand canonical ensemble. The generalized BBGKY hierarchy and boundary condition are deduced for correlation functions. __________ Published in Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 6, pp. 818–839, June, 2005.     

Predictor-Corrector Smoothing Methods for Monotone LCP

In this paper, we analyze the global and local convergence properties of two predictor-corrector smoothing methods, which are based on the framework of the method in [1], for monotone linear complementarity problems (LCPs). The difference between the algorithm in [1] and our algorithms is that the neighborhood of smoothing central path in our paper is different to that in [1]. In addition, the difference between Algorithm 2.1 and the algorithm in [1] exists in the calculation of the predictor step. Comparing with the results in [1],the global and local convergence of the two methods can be obtained under very mild conditions. The global convergence of the two methods do not need the boundness of the inverse of the Jacobian. The superlinear convergence of Algorithm 2.1‘ is obtained under the assumption of nonsingularity of generalized Jacobian of Φ(x,y) at the limit point and Algorithm 2.1 obtains superlinear convergence under the assumption of strict complementarity at the solution. The efficiency of the two methods is tested by numerical experiments.     

Generalized Jacobian for Functions with Infinite Dimensional Range and Domain

In this paper, locally Lipschitz functions acting between infinite dimensional normed spaces are considered. When the range is a dual space and satisfies the Radon–Nikodym property, Clarke’s generalized Jacobian will be extended to this setting. Characterization and fundamental properties of the extended generalized Jacobian are established including the nonemptiness, the β-compactness, the β-upper semicontinuity, and a mean-value theorem. A connection with known notions is provided and chain rules are proved using key results developed. This included the vectorization and restriction theorem, and the extension theorem. Therefore, the generalized Jacobian introduced in this paper is proved to enjoy all the properties required of a derivative like-set. Research of the first author is supported by the Hungarian Scientific Research Fund (OKTA) under grant K62316. Research of the second author is supported by the National Science Foundation under grant DMS-0306260.     

An approximate Newton method for non-smooth equations with finite max functions

A new version of finite difference approximation of the generalized Jacobian for a finite max function is constructed. Numerical results are reported for the generalized Newton methods using this approximation.