Remarks on strict efficiency in scalar and vector optimization

The aim of this paper is to study optimality conditions for strict local minima to constrained mathematical problems governed by scalar and vectorial mappings. Unlike other papers in literature dealing with strict efficiency, we work here with mappings defined on infinite dimensional normed vector spaces. Firstly, we (mainly) consider the case of nonsmooth scalar mappings and we use the Fréchet and Mordukhovich subdifferentials in order to provide optimality conditions. Secondly, we present some methods to reduce the study of strict vectorial minima to the case of strict scalar minima by means of some scalarization techniques. In this vectorial framework we treat separately the case where the ordering cone has non-empty interior and the case where it has empty interior.     

The Structure of the Set of Local Minima of Functions in Various Spaces

Siberian Mathematical Journal - We study the topological properties and cardinalities of the sets of strict local minima of functions on f-quasimetric and topological spaces.     

A Note on First-Order Sufficient Optimality Conditions for Pareto Problems

We take into consideration the first-order sufficient conditions, established by Jiménez and Novo (Numer. Funct. Anal. Optim. 2002; 23:303–322) for strict local Pareto minima. We give here a more operative condition for a strict local Pareto minimum of order 1.     

A Comparison of Global Optimization Methods for the Design of a High-speed Civil Transport

The conceptual design of aircraft often entails a large number of nonlinear constraints that result in a nonconvex feasible design space and multiple local optima. The design of the high-speed civil transport (HSCT) is used as an example of a highly complex conceptual design with 26 design variables and 68 constraints. This paper compares three global optimization techniques on the HSCT problem and two test problems containing thousands of local optima and noise: multistart local optimizations using either sequential quadratic programming (SQP) as implemented in the design optimization tools (DOT) program or Snyman's dynamic search method, and a modified form of Jones' DIRECT global optimization algorithm. SQP is a local optimizer, while Snyman's algorithm is capable of moving through shallow local minima. The modified DIRECT algorithm is a global search method based on Lipschitzian optimization that locates small promising regions of design space and then uses a local optimizer to converge to the optimum. DOT and the dynamic search algorithms proved to be superior for finding a single optimum masked by noise of trigonometric form. The modified DIRECT algorithm was found to be better for locating the global optimum of functions with many widely separated true local optima.     

Absence of Critical Mass Densities for a Vibrating Membrane

We study the dependence of the eigenvalues of a N-dimensional vibrating membrane upon variation of the mass density. We prove that the elementary symmetric functions of the eigenvalues depend real-analytically on the mass density and that such functions have no critical points with constant mass constraint. In particular, the elementary symmetric functions of the eigenvalues, hence all simple eigenvalues, have no local maxima or minima on the set of those mass densities with a prescribed total mass.     

Exact penalty functions in nonlinear programming

It is shown that the existence of a strict local minimum satisfying the constraint qualification of [16] or McCormick's [12] second order sufficient optimality condition implies the existence of a class of exact local penalty functions (that is ones with a finite value of the penalty parameter) for a nonlinear programming problem. A lower bound to the penalty parameter is given by a norm of the optimal Lagrange multipliers which is dual to the norm used in the penalty function.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and by the National Science Foundation under Grant No. MCS74-20584 A02.     

An improved univariate global optimization algorithm with improved linear lower bounding functions

Recently linear lower bounding functions (LLBF's) were proposed and used to find -global minima. Basically an LLBF over an interval is a linear function which lies below a given function over the interval and matches the function value at one end point. By comparing it with the best function value found, it can be used to eliminate subregions which do not contain -global minima. To develop a more efficient LLBF algorithm, two important issues need to be addressed: how to construct a better LLBF and how to use it efficiently. In this paper, an improved LLBF for factorable functions overn-dimensional boxes is derived, in the sense that the new LLBF is always better than those in [3] for continuously differentiable functions. Exploration of the properties of the LLBF enables us to develop a new LLBF-based univariate global optimization algorithm, which is again better than those in [3]. Numerical results on some standard test functions indicate the high potential of our algorithm.This work was supported in part by VLSI Technology Inc. and Tyecin Systems Inc. through the University of California MICRO proram with grant number 92-024.     

Sufficient Conditions of Isolated Minimizers for Constrained Programming Problems

In this article, sufficient optimality conditions for nonsmooth programming problems with inequality constraints are studied. When the objective and constraint functions are ?-stable at some point, a first-order sufficient optimality condition for an isolated local minimizer of order 1 is established. A second-order sufficient optimality condition for an isolated local minimizer of order 2 is obtained in terms of the lower Dini second-order directional derivatives of the Lagrangian function. The obtained results extend and improve the ones found by Ward [21 D.E. Ward ( 1994 ). Characterizations of strict local minima and nacessary conditions for weak sharp minima . Journal of Optimization Theory and Applications 80 : 551 – 571 .[Crossref], [Web of Science ®] , [Google Scholar]].     

Global Optimization: Local Minima and Transition Points

We consider the minimization of smooth functions of the Euclidean space with a finite number of stationary points having moderate asymptotic behavior at infinity. The crucial role of transition points of first order (i.e., saddle points of index 1) is emphasized. It is shown that (generically) any two local minima can be connected via an alternating sequence of local minima and transition points of first order. In particular, the graph with local minima as its nodes and first order transition points representing the edges turns out to be connected (Theorem A). On the other hand, any connected (finite) graph can be realized in the above sense by means of a smooth function of three variables having a minimal number of stationary points (Theorem B).     

GOSH: derivative-free global optimization using multi-dimensional space-filling curves

Global optimization is a field of mathematical programming dealing with finding global (absolute) minima of multi-dimensional multiextremal functions. Problems of this kind where the objective function is non-differentiable, satisfies the Lipschitz condition with an unknown Lipschitz constant, and is given as a “black-box” are very often encountered in engineering optimization applications. Due to the presence of multiple local minima and the absence of differentiability, traditional optimization techniques using gradients and working with problems having only one minimum cannot be applied in this case. These real-life applied problems are attacked here by employing one of the mostly abstract mathematical objects—space-filling curves. A practical derivative-free deterministic method reducing the dimensionality of the problem by using space-filling curves and working simultaneously with all possible estimates of Lipschitz and Hölder constants is proposed. A smart adaptive balancing of local and global information collected during the search is performed at each iteration. Conditions ensuring convergence of the new method to the global minima are established. Results of numerical experiments on 1000 randomly generated test functions show a clear superiority of the new method w.r.t. the popular method DIRECT and other competitors.     

Optimality conditions under relaxed quasiconvexity assumptions using star and adjusted subdifferentials

A set-constrained optimization problem and a mathematical programming problem are considered. We assume that the sublevel sets of the involving functions are convex only at the point under question and hence these functions are not assumed quasiconvex. Using the two star subdifferentials and the adjusted subdifferential, we establish optimality conditions for usual minima and strict minima. Our results contain and improve some recent ones in the literature. Examples are provided to explain the advantages of each of our results.     

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.     

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.     

Error estimates for the numerical approximation of Neumann control problems governed by a class of quasilinear elliptic equations

We study the numerical approximation of Neumann boundary optimal control problems governed by a class of quasilinear elliptic equations. The coefficients of the main part of the operator depend on the state function, as a consequence the state equation is not monotone. We prove that strict local minima of the control problem can be approximated uniformly by local minima of discrete control problems and we also get an estimate of the rate of this convergence. One of the main issues in this study is the error analysis of the discretization of the state and adjoint state equations. Some difficulties arise due to the lack of uniqueness of solution of the discrete equations. The theoretical results are illustrated by numerical tests.     

Une caractérisation complète des minima locaux en programmation quadratique

Résumé Dans ce travail, on se propose de démontrer que, dans le cas des programmes quadratiques, les conditions du second ordre pour la caractérisation des minima locaux deviennent symétriques, c'est à dire, que la condition nécessaire de minimum local est, en fait, suffisante, et, d'autre part, que la condition suffisante de minimum local isolé est, en fait, nécessaire.Dans le cas particulier où le programme quadratique ne comporte que des contraintes en égalité, on retrouve les résultats de A. Orden [7] pour la caractérisation des minima globaux de ces programmes.Les résultats obtenus son démontrés de façon directe, et comparés avec différents résultats que l'on trouve dans la littérature.

---

A complete characterization of local minima in quadratic programming

Summary In this work, the general second order conditions for the characterization of local minima are shown to be necessary and sufficient in the case of a quadratic objective function subject to linear constraints. Specifically, it is shown that the well known second order necessary condition for a local minimum is, actually, sufficient and, on the other hand, that the well known second order sufficient condition for an isolated local minimum is, actually, necessary. These results are proved from scratch and include several existing ones. In the particular case of equality constrained quadratic problems, Orden's second order conditions for global minima [7] are recovered.

     

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.     

A search technique for global optimization in a chaotic environment

We describe a new algorithm which uses the trajectories of a discrete dynamical system to sample the domain of an unconstrained objective function in search of global minima. The algorithm is unusually adept at avoiding nonoptimal local minima and successfully converging to a global minimum. Trajectories generated by the algorithm for objective functions with many local minima exhibit chaotic behavior, in the sense that they are extremely sensitive to changes in initial conditions and system parameters. In this context, chaos seems to have a beneficial effect: failure to converge to a global minimum from a given initial point can often be rectified by making arbitrarily small changes in the system parameters.     

On a Class of Functionals Whose Local Minima are Global

In this note we introduce a suitable class of functionals, including the class of integral functionals, and prove that any (strict) local minimum of a functional of this class, defined on a decomposable space, is a (strict) global minimum. So, the recent result obtained by Giner in [1] is specified and extended.     

On the geometric form of solutions of a free boundary problem involving galvanization

In [6], T. I. Vogel studied a free boundary problem originating in the galvanization process. He showed that if the given boundary Γ* is starlike or convex, then so is the free boundary solution Γ. Our purpose is to generalize Vogel's second result by showing (under certain assumptions) that Γ cannot have more (local) maxima or minima (relative to a given direction) than Γ*; also that Γ cannot have more inflection points or greater total curvature than Γ*. The author has already proven analogous results for the Bernoulli free boundary problem in [1], [2] and [3].     

Higher-order necessary and sufficient conditions for strict local pareto minima in terms of Studniarski's derivatives

In this article, we establish higher-order necessary and sufficient conditions for strict local Pareto minima of nonsmooth multiobjective programing problems in terms of Studniarski's derivatives of higher order.