Outer limits of subdifferentials for min–max type functions

Abstract

We generalize the outer subdifferential construction suggested by Cánovas, Henrion, López and Parra for max type functions to pointwise minima of regular Lipschitz functions. We also answer an open question about the relation between the outer subdifferential of the support of a regular function and the end set of its subdifferential posed by Li, Meng and Yang.     

Optimality conditions and duality in multiple objective programming involving semilocally convex and related functions

A nonlinear multiple objective programming problem is considered where the functions involved are nondifferentiable. By considering the concept of weak minima, the Fritz John type and Karush-Kuhn- Tucker type necessary optimality conditions and Wolfe and Mond-Weir type duality results are given in terms of the right differentials of the functions. The duality results are stated by using the concepts of generalized semilocally convex functions     

Lipschitz B-Vex Functions and Nonsmooth Programming

In this paper, the equivalence between the class of B-vex functions and that of quasiconvex functions is proved. Necessary and sufficient conditions, under which a locally Lipschitz function is B-vex, are established in terms of the Clarke subdifferential. Regularity of locally Lipschitz B-vex functions is discussed. Furthermore, under appropriate conditions, a necessary optimality condition of the Slater type and a sufficient optimality condition are obtained for a nonsmooth programming problem involving B-vex functions.     

Duality and existence theory for nondifferentiable programming

Necessary and sufficient conditions of optimality are given for a nonlinear nondifferentiable program, where the constraints are defined via closed convex cones and their polars. These results are then used to obtain an existence theorem for the corresponding stationary point problem, under some convexity and regularity conditions on the functions involved, which also guarantee an optimal solution to the programming problem. Furthermore, a dual problem is defined, and a strong duality theorem is obtained under the assumption that the constraint sets of the primal and dual problems are nonempty.     

Order-Preserving Transformations and Applications

In this paper, we study the effects of a linear transformation on the partial order relations that are generated by a closed and convex cone in a finite-dimensional space. Sufficient conditions are provided for a transformation preserving a given order. They are applied to derive the relationship between the efficient set of a set and its image under a linear transformation, to characterize generalized convex vector functions by using order-preserving transformations, to establish some calculus rules for the subdifferential of a convex vector function, and develop an optimality condition for a convex vector problem.     

The q-asymptotic function in c-convex analysis

Abstract

We establish several connections between generalized asymptotic functions and different areas of convexity theory, without coercivity assumptions. Properties and characterizations of abstract subdifferentials, normal cones, conjugates, support functions and optimality conditions for the minimization problem are given. We provide a new result on existence of minimizers for a class of nonconvex functions which is strictly larger than the class of quasiconvex ones.     

New characterizations of weak sharp minima

In this paper, we study the concept of weak sharp minima by using conjugate functions. Not only some well-known results can be obtained in this unified way, but also new characterizations are developed. Finally, under rather weak conditions, we establish the finite termination property for convex programming and variational inequality problem, respectively.     

An algorithm for the estimation of a regression function by continuous piecewise linear functions

The problem of the estimation of a regression function by continuous piecewise linear functions is formulated as a nonconvex, nonsmooth optimization problem. Estimates are defined by minimization of the empirical L ₂ risk over a class of functions, which are defined as maxima of minima of linear functions. An algorithm for finding continuous piecewise linear functions is presented. We observe that the objective function in the optimization problem is semismooth, quasidifferentiable and piecewise partially separable. The use of these properties allow us to design an efficient algorithm for approximation of subgradients of the objective function and to apply the discrete gradient method for its minimization. We present computational results with some simulated data and compare the new estimator with a number of existing ones.     

A unified approach to one-parametric general quadratic programming

A method is proposed for finding local minima to the parametric general quadratic programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The local minimum vector and the local minimum value are determined explicitly as rational functions of the parameter. A numerical example is given.     

Economic equilibrium problems in reflexive Banach spaces

The problem is to minimize a finite collection of objective functions over admissible sets depending on the so-called price vector. The minima in question and the price vector are linked together by a subdifferential governing law. The problem stated as a system of variational–hemivariational inequalities, defined on a nonconvex feasible set, is reduced to one variational–hemivariational inequality involving nonmonotone multivalued mapping. The existence of solutions is examined under the assumption that the constrained functions are positive homogeneous of degree one. The study has been inspired by economic issues and leads to new results concerning the existence of competitive equilibria.     

Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions

We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given. Some numerical results illustrate the behaviour of our approaches.     

Image space approach to penalty methods

In this paper, we introduce a unified framework for the study of penalty concepts by means of the separation functions in the image space (see Ref. 1). Moreover, we establish new results concerning a correspondence between the solutions of the constrained problem and the limit points of the unconstrained minima. Finally, we analyze some known classes of penalty functions and some known classical results about penalization, and we show that they can be derived from our results directly.     

Global Optimization of a Quadratic Functional with Quadratic Equality Constraints, Part 2

In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. It is assumed that the cost functional is positive definite and that the constraints are both feasible and regular (but otherwise they are unrestricted quadratic functions). Thus, the existence of a global constrained minimum is assured. We develop a necessary and sufficient condition that completely characterizes the global minimum cost. Such a condition is of essential importance in iterative numerical methods for solving the constrained minimization problem, because it readily distinguishes between local minima and global minima and thus provides a stopping criterion for the computation. The result is similar to one obtained previously by the authors. In the previous result, we gave a characterization of the global minimum of a constrained quadratic minimization problem in which the cost functional was an arbitrary quadratic functional (as opposed to positive-definite here) and the constraints were at least positive-semidefinite quadratic functions (as opposed to essentially unrestricted here).     

The absolute centre of a graph

The problem of finding the absolute centre of a graph, which arises in e.g. the selection of a site for an emergency-service centre, involves the global minimisation of certain piecewise-linear non-convex continuous functions. By an algebraic characterisation of the local minima of these functions, we can convert the continuous problem into a combinatorial problem, soluble by a procedure related in complexity to a sort-routine.     

Optimality and mixed saddle point criteria in multiobjective optimization

In this paper, higher order strong convexity for Lipschitz functions is introduced and is utilized to derive the optimality conditions for the new concept of strict minimizer of higher order for a multiobjective optimization problem. Variational inequality problem is introduced and its solutions are related to the strict minimizers of higher order for a multiobjective optimization problem. The notion of vector valued partial Lagrangian is also introduced and equivalence of the mixed saddle points of higher order and higher order minima are provided.     

On Conjugations for Functions with Values in Extensions of Ordered Groups

We continue our study of generalized conjugations for functions with values in the canonical enlargement of a complete ordered group, started in [10], which encompass various kinds of known conjugations and polarities. We obtain extensions, to this framework, of some results on d.c. duality theory and subdifferentials, and we give some applications to conjugations and subdifferentials for functions with values in .     

Parametric simplex algorithms for a class of NP-Complete problems whose average number of steps is polynomial

We will show that the average number of steps of parametric simplex algorithms for obtaining global minima of rank-one and rank-two bilinear-programming problems are lower-order polynomial functions of the problem size under the standard assumptions on the distribution of the data imposed in the probabilistic analysis of the simplex method. This means that there exist algorithms for some special class of NP-complete problems, whose average number of arithmetics are polynomial order of the problem size.     

Averaged Subgradient Methods for Constrained Convex Optimization and Nash Equilibria Computation

We consider the problem of finding minima of convex functions under convex inequality constraints as well as the problem of finding Nash equilibria in n -person constant sum games. We prove that both problems can be solved by algorithms whose basic principles consist of representing the original problems as infinite systems of convex inequalities which, in turn, can be approached by outer projection techniques. Experiments showing how one of these algorithms behaves in test cases are presented and, in context, we describe a numerical method for computing subgradients of convex functions.     

A note on weak sharp minima in multicriteria linear programming

In this note, the set of weak Pareto solutions of a multicriteria linear programming problem (MCLP, for short) is proved to be a set of weak sharp minima for another residual function of MCLP, i.e., the minimum of the natural residual functions of finitely many scalarization problems of MCLP, which is less than the natural residual function of MCLP. This can be viewed as a slight improvement of a result due to Deng and Yang. Some examples are given to illustrate these results.     

Test Functions with Variable Attraction Regions for Global Optimization Problems

Functions with local minima and size of their region of attraction known a priori, are often needed for testing the performance of algorithms that solve global optimization problems. In this paper we investigate a technique for constructing test functions for global optimization problems for which we fix a priori: (i) the problem dimension, (ii) the number of local minima, (iii) the local minima points, (iv) the function values of the local minima. Further, the size of the region of attraction of each local minimum may be made large or small. The technique consists of first constructing a convex quadratic function and then systematically distorting selected parts of this function so as to introduce local minima.