On Timonov's algorithm for global optimization of univariate Lipschitz functions

Timonov proposes an algorithm for global maximization of univariate Lipschitz functions in which successive evaluation points are chosen in order to ensure at each iteration a maximal expected reduction of the region of indeterminacy, which contains all globally optimal points. It is shown that such an algorithm does not necessarily converge to a global optimum.     

Constraint qualifications for constrained Lipschitz optimization problems and applications to a MPCC

Three constraint qualifications (the weak generalized Robinson constraint qualification, the bounded constraint qualification, and the generalized Abadie constraint qualification), which are weaker than the generalized Robinson constraint qualification (GRCQ) given by Yen (1997) [1], are introduced for constrained Lipschitz optimization problems. Relationships between those constraint qualifications and the calmness of the solution mapping are investigated. It is demonstrated that the weak generalized Robinson constraint qualification and the bounded constraint qualification are easily verifiable sufficient conditions for the calmness of the solution mapping, whereas the proposed generalized Abadie constraint qualification, described in terms of graphical derivatives in variational analysis, is weaker than the calmness of the solution mapping. Finally, those constraint qualifications are written for a mathematical program with complementarity constraints (MPCC), and new constraint qualifications ensuring the C-stationary point condition of a MPCC are obtained.     

非线性Lipschitz算子的Lipschitz对偶算子及其应用

在文山中我们对非线性Ｌｉｐｓｃｈｉｔｚ算子定义了其Ｌｉｐｓｃｈｉｔｚ对偶算子，并证明了任意非线性Ｌｉｐｓｃｈｉｔｚ算子的Ｌｉｐｓｃｈｉｔｚ对偶算子是一个定义在Ｌｉｐｓｃｈｉｔｚ对偶空间上的有界线性算子．本文还进一步证明：设Ｃ为 Ｂａｎａｃｈ空间 Ｘ的闭子集，Ｃ＊Ｌ为Ｃ的 Ｌｉｐｓｃｈｉｔｚ对偶空间，Ｕ为 Ｃ＊Ｌ上的有界线性算子，则当且仅当 Ｕ为 ｗ＊－ｗ＊连续的同态变换时，存在Ｌｉｐｓｃｈｉｔｚ连续算子Ｔ，使Ｕ为Ｔ的Ｌｉｐｓｃｈｉｔｚ对偶算子．这一结论的理论意义在于：它表明一个非线性Ｌｉｐｓｃｈｉｔｚ算子的可逆性问题可转化为有界线性算子的可逆性问题．作为应用，通过引入一个新概念──ＰＸ－对偶算子，在一般框架下给出了非线性算子半群的生成定理．     

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.     

Global optimization of univariate Lipschitz functions: I. Survey and properties

We consider the following global optimization problems for a univariate Lipschitz functionf defined on an interval [a, b]: Problem P: find a globally optimal value off and a corresponding point; Problem P: find a globally-optimal value off and a corresponding point; Problem Q: localize all globally optimal points; Problem Q: find a set of disjoint subintervals of small length whose union contains all globally optimal points; Problem Q: find a set of disjoint subintervals containing only points with a globally-optimal value and whose union contains all globally optimal points.We present necessary conditions onf for finite convergence in Problem P and Problem Q, recall the concepts necessary for a worst-case and an empirical study of algorithms (i.e., those ofpassive and ofbest possible algorithms), summarize and discuss algorithms of Evtushenko, Piyavskii-Shubert, Timonov, Schoen, Galperin, Shen and Zhu, presenting them in a simplified and uniform way, in a high-level computer language. We address in particular the problems of using an approximation for the Lipschitz constant, reducing as much as possible the expected length of the region of indeterminacy which contains all globally optimal points and avoiding remaining subintervals without points with a globally-optimal value. New algorithms for Problems P and Q and an extensive computational comparison of algorithms are presented in a companion paper.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426 and FCAR grant 89EQ4144. We thank N. Paradis for drawing some of the figures.     

Smooth approximation of Lipschitz functions on Riemannian manifolds

We show that for every Lipschitz function f defined on a separable Riemannian manifold M (possibly of infinite dimension), for every continuous , and for every positive number r>0, there exists a C^∞ smooth Lipschitz function such that |f(p)−g(p)|?ε(p) for every p∈M and Lip(g)?Lip(f)+r. Consequently, every separable Riemannian manifold is uniformly bumpable. We also present some applications of this result, such as a general version for separable Riemannian manifolds of Deville-Godefroy-Zizler's smooth variational principle.     

A trust region method for solving linearly constrained locally Lipschitz optimization problems

In this paper, we present a nonsmooth trust region method for solving linearly constrained optimization problems with a locally Lipschitz objective function. Using the approximation of the steepest descent direction, a quadratic approximation of the objective function is constructed. The null space technique is applied to handle the constraints of the quadratic subproblem. Next, the CG-Steihaug method is applied to solve the new approximation quadratic model with only the trust region constraint. Finally, the convergence of presented algorithm is proved. This algorithm is implemented in the MATLAB environment and the numerical results are reported.     

Banach空间的Lipschitz对偶及其应用

本文引进Banach空间E的一个全新对偶空间概念—Lipschitz对偶空间,并证明：任何Banach空间的Lipschitz对偶空间是某个包含E的Banach空间的线性对偶空间,以所引进的新对偶空间为框架,本文定义了非线性Lipschitz算子的Lipshitz对偶算子,证明：任何非线性Lipschitz算子的Lipschitz对偶算子是有界线性算子．所获结果为推广线性算子理论到非线性情形（特别,运用线性算子理论研究非线性算子的特性）开辟了一条新的途径．作为例证,我们应用所建立的理论证明了若干新的非线性一致Lipschitz映象遍历收敛性定理.     

Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison

We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P: find a globally-optimal value off and a corresponding point; Problem Q: find a set of disjoint subintervals of [a, b] containing only points with a globally-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P. In phase I, this algorithm obtains rapidly a solution which is often globally-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426, FCAR grant 89EQ4144 and partially by AFOSR grant 0066. We thank Nicole Paradis for her help in drawing the figures.     

A global minimization algorithm for Lipschitz functions

The global optimization problem with and f(x) satisfying the Lipschitz condition , is considered. To solve it a region-search algorithm is introduced. This combines a local minimum algorithm with a procedure that at the ith iteration finds a region S _i where the global minimum has to be searched for. Specifically, by making use of the Lipschitz condition, S _i , which is a sequence of intervals, is constructed by leaving out from S _i-1 an interval where the global minimum cannot be located. A convergence property of the algorithm is given. Further, the ratio between the measure of the initial feasible region and that of the unexplored region may be used as stop rule. Numerical experiments are carried out; these show that the algorithm works well in finding and reducing the measure of the unexplored region.     

Efficient domain partitioning algorithms for global optimization of rational and Lipschitz continuous functions

A domain partitioning algorithm for minimizing or maximizing a Lipschitz continuous function is enhanced to yield two new, more efficient algorithms. The use of interval arithmetic in the case of rational functions and the estimates of Lipschitz constants valid in subsets of the domain in the case of others and the addition of local optimization have resulted in an algorithm which, in tests on standard functions, performs well.     

Lipschitz behavior of convex semi-infinite optimization problems: a variational approach

In this paper we make use of subdifferential calculus and other variational techniques, traced out from [Ioffe, A.D.: Metric regularity and subdifferential calculus. Uspekhi Mat. Nauk 55, 3(333), 103–162; Engligh translation Math. Surveys 55, 501–558 (2000); Ioffe, A.D.: On rubustness of the regularity property of maps. Control cybernet 32, 543–554 (2003)], to derive different expressions for the Lipschitz modulus of the optimal set mapping of canonically perturbed convex semi-infinite optimization problems. In order to apply this background for obtaining the modulus of metric regularity of the associated inverse multifunction, we have to analyze the stable behavior of this inverse mapping. In our semi-infinite framework this analysis entails some specific technical difficulties. We also provide a new expression of a global variational nature for the referred regularity modulus.      

New LP bound in multivariate Lipschitz optimization: Theory and applications

Most numerically promising methods for solving multivariate unconstrained Lipschitz optimization problems of dimension greater than two use rectangular or simplicial branch-and-bound techniques with computationally cheap but rather crude lower bounds.Generalizations to constrained problems, however, require additional devices to detect sufficiently many infeasible partition sets. In this article, a new lower bounding procedure is proposed for simplicial methods yielding considerably better bounds at the expense of two linear programs in each iteration. Moreover, the resulting approach can solve easily linearly constrained problems, since in this case infeasible partition sets are automatically detected by the lower bounding procedure.Finally, it is shown that the lower bounds can be further improved when the method is applied to solve systems of inequalities. Implementation issues, numerical experiments, and comparisons are discussed in some detail.The authors are indebted to the Editor-in-Chief of this journal for his valuable suggestions which have considerably improved the final version of this article.     

Applications of Inverse Limits to Extensions of Operators and Approximation of Lipschitz Functions

We consider extensions of linear operators from finite dimensional subspaces. As a corollary of Steenrod's theorem about inverse limits of topological spaces, we obtain new results concerning approximation in tensor product spaces and the stability of the Cauchy functional equation.     

Outer approximation algorithm for nondifferentiable optimization problems

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ⁿ can be expressed as minimizing max{g(x, y)|y X}, whereg is a support function forf[f(x) g(x, y), for ally X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.This research was supported by the Science and Engineering Research Council, UK, and by the National Science Foundation under Grant No. ECS-79-13148.     

Outer approximation algorithm for nondifferentiable optimization problems

Omissions from the list of references of Ref. 1 are corrected.     

Lipschitz properties of the scalarization function and applications

The scalarization functions were used in vector optimization for a long period. Similar functions were introduced and used in economics under the name of shortage function or in mathematical finance under the name of (convex or coherent) measures of risk. The main aim of this article is to study Lipschitz continuity properties of such functions and to give some applications for deriving necessary optimality conditions for vector optimization problems using the Mordukhovich subdifferential.     

On nonconvex optimization problems with separated nonconvex variables

A mathematical programming problem is said to have separated nonconvex variables when the variables can be divided into two groups: x=(x ₁,...,x _n ) and y=( y ₁,...,y _n ), such that the objective function and any constraint function is a sum of a convex function of (x, y) jointly and a nonconvex function of x alone. A method is proposed for solving a class of such problems which includes Lipschitz optimization, reverse convex programming problems and also more general nonconvex optimization problems.