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.     

群零模正则化问题的等价Lipschitz优化模型

针对群零模正则化问题, 从零模函数的变分刻画入手, 将其等价地表示为带有 互补约束的数学规划问题(简称MPCC问题), 然后证明将互补约束直接罚到MPCC的目标函数而得到的罚问题是MPCC问题的全局精确罚. 此精确罚问题的目标函数不仅在可行集上全局Lipschitz连续而且还具有满意的双线性结构, 为设计群零模正则化问题的序列凸松弛算法提供了满意的等价Lipschitz优化模型.     

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.     

Simplicial Endomorphisms

The monoids of simplicial endomorphisms, i.e., the monoids of endomorphisms in the simplicial category, are submonoids of monoids one finds in Temperley–Lieb algebras, and as the monoids of Temperley–Lieb algebras are linked to situations where an endofunctor is adjoint to itself, so the monoids of simplicial endomorphisms are linked to arbitrary adjoint situations. This link is established through diagrams of the kind found in Temperley–Lieb algebras. Results about these matters, which were previously prefigured up to a point, are here surveyed and reworked. A presentation of monoids of simplicial endomorphisms by generators and relations has been given a long time ago. Here a closely related presentation is given, with completeness proved in a new and self-contained manner.     

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.