Lipschitzian optimization without the Lipschitz constant

We present a new algorithm for finding the global minimum of a multivariate function subject to simple bounds. The algorithm is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. This is done by carrying out simultaneous searches using all possible constants from zero to infinity. On nine standard test functions, the new algorithm converges in fewer function evaluations than most competing methods.The motivation for the new algorithm stems from a different way of looking at the Lipschitz constant. In particular, the Lipschitz constant is viewed as a weighting parameter that indicates how much emphasis to place on global versus local search. In standard Lipschitzian methods, this constant is usually large because it must equal or exceed the maximum rate of change of the objective function. As a result, these methods place a high emphasis on global search and exhibit slow convergence. In contrast, the new algorithm carries out simultaneous searches using all possible constants, and therefore operates at both the global and local level. Once the global part of the algorithm finds the basin of convergence of the optimum, the local part of the algorithm quickly and automatically exploits it. This accounts for the fast convergence of the new algorithm on the test functions.     

Optimal algorithms for global optimization in case of unknown Lipschitz constant

We consider the global optimization problem for d-variate Lipschitz functions which, in a certain sense, do not increase too slowly in a neighborhood of the global minimizer(s). On these functions, we apply optimization algorithms which use only function values. We propose two adaptive deterministic methods. The first one applies in a situation when the Lipschitz constant L is known. The second one applies if L is unknown. We show that for an optimal method, adaptiveness is necessary and that randomization (Monte Carlo) yields no further advantage. Both algorithms presented have the optimal rate of convergence.     

On the Lipschitz constant of the RSK correspondence

We view the RSK correspondence as associating to each permutation π∈Sn a Young diagram λ=λ(π), i.e. a partition of n. Suppose now that π is left-multiplied by t transpositions, what is the largest number of cells in λ that can change as a result? It is natural refer to this question as the search for the Lipschitz constant of the RSK correspondence.We show upper bounds on this Lipschitz constant as a function of t. For t=1, we give a construction of permutations that achieve this bound exactly. For larger t we construct permutations which come close to matching the upper bound that we prove.     

Estimation of the Lipschitz constant of a function

A number of global optimisation algorithms rely on the value of the Lipschitz constant of the objective function. In this paper we present a stochastic method for estimating the Lipschitz constant. We show that the largest slope in a fixed size sample of slopes has an approximate Reverse Weibull distribution. Such a distribution is fitted to the largest slopes and the location parameter used as an estimator of the Lipschitz constant. Numerical results are presented.     

Semigroups of mappings with rigid Lipschitz constant

It is shown that two well-known uniformly fixed point free lipschitzian semigroups of mappings have minimal Lipschitz constant on the positive part of the unit ball of . This implies that a question raised by T. Kuczumow has a negative answer.

     

An explicit Lipschitz constant for the joint spectral radius

In 2002, Wirth has proved that the joint spectral radius of irreducible compact sets of matrices is locally Lipschitz continuous as a function of the matrix set. In the paper, an explicit formula for the related Lipschitz constant is obtained.     

Lipschitz constant for bi-Lipschitz automorphism on Moran-like sets

This paper proves that if F⊂R¹ is a complete set equipped with some suitable Moran-like structure, then there is a constant c₀>1 such that for any bi-Lipschitz bijection ,

     

A Lipschitz constant associated with lemke's closest-point principle

We give the very simple proof of the Lipschitzian behavior of the solution of a steepestascent problem.     

Sharp Lipschitz constant of bi-Lipschitz automorphism on Cantor set

Suppose C _r = (r C _r ) ∪ (r C _r + 1 − r) is a self-similar set with r ∈ (0, 1/2), and Aut(C _r ) is the set of all bi-Lipschitz automorphisms on C _r . This paper proves that there exists f* ∈ Aut(C _r ) such that

Team optimization problems with Lipschitz continuous strategies

Sufficient conditions for the existence and Lipschitz continuity of optimal strategies for static team optimization problems are studied. Revised statements and proofs of some results appeared in the literature are presented. Their extensions are discussed. As an example of application, optimal production in a multidivisional firm is considered.     

Analysis and optimization of Lipschitz continuous mappings

In this paper, four fundamental theorems for continuously differentiable mappings (the multiplier rule for equality constraints of Carathéodory, the inverse mapping theorem, the implicit mapping theorem, and the general multiplier rule for inequality and equality constraints of Mangasarian and Fromovitz) are shown to have natural extensions valid when the mappings are only Lipschitz continuous. Involved in these extensions is a compact, convex set of linear mappings called the generalized derivative, which can be assigned to any Lipschitz continuous mapping and point of its (open) domain and which reduces to the usual derivative whenever the mapping is continuously differentiable. After a brief calculus for this generalized derivative is presented in Part I, the connection between the ranks of the linear mappings in the generalized derivative and theinteriority of the given mapping is explored in Parts II and IV; this relationship is used in Parts III and IV to prove the extensions of the theorems mentioned above.This paper is lovingly dedicated to the author's wife, Nancy Arneson Pourciau.Each section of this paper has benefited from the consistently accurate advice and unflagging enthusiasm of the author's teacher, Professor Hubert Halkin.     

Lipschitz regularity for minima without strict convexity of the Lagrangian

We give, in a non-smooth setting, some conditions under which (some of) the minimizers of among the functions in W^1,1(Ω) that lie between two Lipschitz functions are Lipschitz. We weaken the usual strict convexity assumption in showing that, if just the faces of the epigraph of a convex function are bounded and the boundary datum u₀ satisfies a generalization of the Bounded Slope Condition introduced by A. Cellina then the minima of on , whenever they exist, are Lipschitz. A relaxation result follows.     

On using estimates of Lipschitz constants in global optimization

Several authors have proposed estimating Lipschitz constants in global optimization by a multiple of the largest slope (in absolute value) between successive evaluation points. A class of univariate functions is exhibited for which the global optimum will be missed when using such a procedure, even if the multiple is arbitrarily large.Research of the first and third authors was supported by AFOSR Grants 0271 and 0066 to Rutgers University. Research of the second author was supported by NSERC Grant GP0036426 and FCAR Grant 90NC0305.This research was done while the first author was Professor and the third author was Graduate Student at RUTCOR, Rutgers University.     

Equivalent Lipschitz surrogates for zero-norm and rank optimization problems

This paper proposes a mechanism to produce equivalent Lipschitz surrogates for zero-norm and rank optimization problems by means of the global exact penalty for their equivalent mathematical programs with an equilibrium constraint (MPECs). Specifically, we reformulate these combinatorial problems as equivalent MPECs by the variational characterization of the zero-norm and rank function, show that their penalized problems, yielded by moving the equilibrium constraint into the objective, are the global exact penalization, and obtain the equivalent Lipschitz surrogates by eliminating the dual variable in the global exact penalty. These surrogates, including the popular SCAD function in statistics, are also difference of two convex functions (D.C.) if the function and constraint set involved in zero-norm and rank optimization problems are convex. We illustrate an application by designing a multi-stage convex relaxation approach to the rank plus zero-norm regularized minimization problem.     

Sard theorems for Lipschitz functions and applications in optimization

We establish a “preparatory Sard theorem” for smooth functions with a partially affine structure. By means of this result, we improve a previous result of Rifford [17, 19] concerning the generalized (Clarke) critical values of Lipschitz functions defined as minima of smooth functions. We also establish a nonsmooth Sard theorem for the class of Lipschitz functions from R^d to R^p that can be expressed as finite selections of C^k functions (more generally, continuous selections over a compact countable set). This recovers readily the classical Sard theorem and extends a previous result of Barbet–Daniilidis–Dambrine [1] to the case p > 1. Applications in semi-infinite and Pareto optimization are given.     

An algorithm for global optimization of Lipschitz continuous functions

An algorithm is presented which locates the global minimum or maximum of a function satisfying a Lipschitz condition. The algorithm uses lower bound functions defined on a partitioned domain to generate a sequence of lower bounds for the global minimum. Convergence is proved, and some numerical results are presented.