Existence theorems for saddle points of vector-valued maps

In this paper, we prove some new existence theorems for loose saddle points and for saddle points of set-valued maps or vector-valued functions. These theorems generalize the corresponding results of Tanaka and those of Luc and Vargas via different proofs.The authors would like to thank two referees for their careful reading of the paper and helpful comments.     

Lagrange Multipliers and saddle points in multiobjective programming

In this paper, we present several conditions for the existence of a Lagrange multiplier or a weak saddle point in multiobjective optimization. Relations between a Lagrange multiplier and a weak saddle point are established. A sufficient condition is also given for the equivalence of the Benson proper efficiency and the Borwein proper efficiency.This research was supported by NSFC under Grant No. 78900011 and by BMADIS. The authors are grateful to two referees for supplying valuable comments and pointing out detailed corrections to the draft paper. The authors also wish to thank Dr. P. L. Yu for valuable comments and suggestions.The revised version of this paper was completed while the second author visited the Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands.     

Minimax theorems and cone saddle points of uniformly same-order vector-valued functions

This paper is concerned with minimax theorems in vectorvalued optimization. A class of vector-valued functions which includes separated functionsf(x, y)=u(x)+v(y) as its proper subset is introduced. Minimax theorems and cone saddle-point theorems for this class of functions are investigated.The authors would like to thank two anonymous referees for helpful comments.     

Generalized quasiconvexities,cone saddle points,and minimax theorem for vector-valued functions

We establish the following theorems: (i) an existence theorem for weak type generalized saddle points; (ii) an existence theorem for strong type generalized saddle points; (iii) a generalized minimax theorem for a vector-valued function. These theorems are generalizations and extensions of the author's recent results. For such extensions, we propose new concepts of convexity and continuity of vector-valued functions, which are weaker than ordinary ones. Some of the proofs are based on a few key observations and also on the Browder coincidence theorem or the Tychonoff fixed-point theorem. Also, the minimax theorem follows from the existence theorem for weak type generalized saddle points. The main spaces with mathematical structures considered are real locally convex spaces and real ordered topological vector spaces.This paper is dedicated to Professor Kensuke Tanaka on his sixtieth birthday.This paper was written when the author was a visitor at the Department of Mathematical Science, Graduate School of Science and Technology, Niigata University, Niigata, Japan. The author is indebted to Prof. K. Tanaka for suggesting this work.The author is very grateful to Prof. P. L. Yu for his useful encouragement and suggestions and to the referees for their valuable suggestions and comments.     

Loose saddle points of set-valued maps in topological vector spaces

We give a new existence theorem for loose saddle point of set-valued map having values in a partially ordered topological vector space which is based on continuity and quasiconvexity- quasiconcavity of its scalarized maps. Moreover, we prove a new saddle point theorem for vector-valued functions in locally convex topological vector spaces under weak condition that is the semicontinuity of two function scalarization.     

Properties of the Augmented Lagrangian in Nonlinear Semidefinite Optimization

We study the properties of the augmented Lagrangian function for nonlinear semidefinite programming. It is shown that, under a set of sufficient conditions, the augmented Lagrangian algorithm is locally convergent when the penalty parameter is larger than a certain threshold. An error estimate of the solution, depending on the penalty parameter, is also established.The first author was partially supported by Singapore-MIT Alliance and by the National University of Singapore under Grants RP314000-028/042/057-112. The second author was partially supported by the Funds of the Ministry of Education of China for PhD Units under Grant 20020141013 and the National Natural Science Foundation of China under Grant 10471015.     

Updating the Multipliers Associated with Inequality Constraints in an Augmented Lagrangian Multiplier Method

This paper contributes to the development of the field of augmented Lagrangian multiplier methods for general nonlinear programming by introducing a new update for the multipliers corresponding to inequality constraints. The update maintains naturally the nonnegativity of the multipliers without the need for a positive-orthant projection, as a result of the verification of the first-order necessary conditions for the minimization of a modified augmented Lagrangian penalty function.In the new multiplier method, the roles of the multipliers are interchanged: the multipliers corresponding to the inequality constraints are updated explicitly, whereas the multipliers corresponding to the equality constraints are approximated implicitly. It is shown that the basic properties of local convergence of the traditional multiplier method are valid also for the proposed method.     

On the twice differentiable cubic augmented Lagrangian

Rockafellar's quadratic augmented Lagrangian for inequality constrained minimization is not twice differentiable. To eliminate this drawback, several quite complicated Lagrangians have been proposed. We exhibit a simple cubic Lagrangian that is twice differentiable. It stems from the recent work of Eckstein and Teboulle on Bregmanrelated Lagrangians.This research was supported by the State Committee for Scientific Research under Grant 8S50502206.     

Validation of an Augmented Lagrangian Algorithm with a Gauss-Newton Hessian Approximation Using a Set of Hard-Spheres Problems

An Augmented Lagrangian algorithm that uses Gauss-Newton approximations of the Hessian at each inner iteration is introduced and tested using a family of Hard-Spheres problems. The Gauss-Newton model convexifies the quadratic approximations of the Augmented Lagrangian function thus increasing the efficiency of the iterative quadratic solver. The resulting method is considerably more efficient than the corresponding algorithm that uses true Hessians. A comparative study using the well-known package LANCELOT is presented.     

On stationary points of the implicit Lagrangian for nonlinear complementarity problems

Mangasarian and Solodov have recently introduced an unconstrained optimization problem whose global minima are solutions of the nonlinear complementarity problem (NCP). In this paper, we show that, if the mapping involved in NCP has a positive-definite Jacobian, then any stationary point of the optimization problem actually solves NCP. We also discuss a descent method for solving the unconstrained optimization problem.The authors are indebted to a referee for a helpful suggestion that led them to develop the descent method described in Section 3. They are grateful to Professor F. Facchinei, who kindly pointed out an error in the proof of Theorem 2.3 in an earlier version of the paper. The also thank Professor P. Tseng for a discussion on Theorem 3.1.     

Topological pressure via saddle points

Let be a compact locally maximal invariant set of a - diffeomorphism on a smooth Riemannian manifold . In this paper we study the topological pressure (with respect to the dynamical system ) for a wide class of Hölder continuous potentials and analyze its relation to dynamical, as well as geometrical, properties of the system. We show that under a mild non-uniform hyperbolicity assumption the topological pressure of is entirely determined by the values of on the saddle points of in . Moreover, it is enough to consider saddle points with ``large' Lyapunov exponents. We also introduce a version of the pressure for certain non-continuous potentials and establish several variational inequalities for it. Finally, we deduce relations between expansion and escape rates and the dimension of . Our results generalize several well-known results to certain non-uniformly hyperbolic systems.

     

Existence theorems for cone saddle points of vector-valued functions in infinite-dimensional spaces

For vector-valued functions, cone saddle points are defined, and some existence theorems for them are established in infinite-dimensional spaces. Most of our results rely on Condition 2.1, which has been given by Sterna-Karwat. In particular, it shows that the scalarization of vector-valued functions plays an important role for the condition. Some interesting examples in infinite-dimensional spaces are presented. Moreover, necessary conditions for the existence of cone saddle points are investigated.The author would like to thank the referees for their valuable suggestions on the original draft.     

A note on the existence of saddle points of p-th power Lagrangian for constrained nonconvex optimization

Li and Sun [D. Li and X.L. Sun, Existence of a saddle point in nonconvex constrained optimization, J. Global Optim. 21 (2001), pp. 39--50; D. Li and X.L. Sun, Convexification and existence of saddle point in a p-th-power reformulation for nonconvex constrained optimization, Nonlinear Anal. 47 (2001), pp. 5611--5622], present the existence of a global saddle point of the p-th power Lagrangian functions for constrained nonconvex optimization, under second-order sufficiency conditions and additional conditions that the feasible set is compact and the global solution of the primal problem is unique. In this article, it is shown that the same results can be obtained under additional assumptions that do not require the compactness of the feasible set and the uniqueness of global solution of the primal problem.     

Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function

An algorithm for nonlinear programming problems with equality constraints is presented which is globally and superlinearly convergent. The algorithm employs a recursive quadratic programming scheme to obtain a search direction and uses a differentiable exact augmented Lagrangian as line search function to determine the steplength along this direction. It incorporates an automatic adjustment rule for the selection of the penalty parameter and avoids the need to evaluate second-order derivatives of the problem functions. Some numerical results are reported.     

Augmented Lagrangians with Adaptive Precision Control for Quadratic Programming with Equality Constraints: Corrigendum and Addendum

In this paper we give corrections to our paper on an augmented Lagrangian type algorithm for strictly convex quadratic programming problems with equality constraints.     

Augmented Lagrangians with Adaptive Precision Control for Quadratic Programming with Equality Constraints

In this paper we introduce an augmented Lagrangian type algorithm for strictly convex quadratic programming problems with equality constraints. The new feature of the proposed algorithm is the adaptive precision control of the solution of auxiliary problems in the inner loop of the basic algorithm. Global convergence and boundedness of the penalty parameter are proved and an error estimate is given that does not have any term that accounts for the inexact solution of the auxiliary problems. Numerical experiments illustrate efficiency of the algorithm presented     

Lagrange multipliers theorem and saddle point optimality criteria in mathematical programming

We prove a version of Lagrange multipliers theorem for nonsmooth functionals defined on normed spaces. Applying these results, we extend some results about saddle point optimality criteria in mathematical programming.     

On generalized equilibrium points

Generalizations of the usual definition of saddle point and equilibrium point are introduced in this paper. The existence of these points is shown to be related to a class of functions that we call perturbed convex functions. First and second order conditions regarding the existence of these points are also proved.     

An optimal algorithm for a class of equality constrained quadratic programming problems with bounded spectrum

The implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for the solution of large convex equality constrained quadratic programming problems is considered. It is proved that if the auxiliary problems are approximately solved by the conjugate gradient method, then the algorithm finds an approximate solution of the class of problems with uniformly bounded spectrum of the Hessian matrix at O(1) matrix–vector multiplications. If applied to the class of problems with the Hessian matrices that are in addition either sufficiently sparse or can be expressed as a product of such sparse matrices, then the cost of the solution is proportional to the dimension of the problems. Theoretical results are illustrated by numerical experiments. This research is supported by grants of the Ministry of Education No. S3086102, ET400300415 and MSM 6198910027.     

A local min-orthogonal method for finding multiple saddle points

The purpose of this paper is twofold. The first is to remove a possible ill-posedness related to a local minimax method developed in SIAM J. Sci. Comput. 23 (2001) 840-865, SIAM J. Sci. Comput. 24 (2002) 840-865 and the second is to provide a local characterization for nonminimax type saddle points. To do so, a local L-⊥ selection is defined and a necessary and sufficient condition for a saddle point is established, which leads to a min-orthogonal method. Those results exceed the scope of a minimax principle, the most popular approach in critical point theory. An example is given to illustrate the new theory. With this local characterization, the local minimax method in SIAM J. Sci. Comput. 23 (2001) 840-865, SIAM J. Sci. Comput. 24 (2002) 840-865 is generalized to a local min-orthogonal method for finding multiple saddle points. In a subsequent paper, this approach is applied to define a modified pseudo gradient (flow) of a functional for finding multiple saddle points in Banach spaces.