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.     

An approximate subgradient algorithm for unconstrained nonsmooth,nonconvex optimization

In this paper a new algorithm for minimizing locally Lipschitz functions is developed. Descent directions in this algorithm are computed by solving a system of linear inequalities. The convergence of the algorithm is proved for quasidifferentiable semismooth functions. We present the results of numerical experiments with both regular and nonregular objective functions. We also compare the proposed algorithm with two different versions of the subgradient method using the results of numerical experiments. These results demonstrate the superiority of the proposed algorithm over the subgradient method.      

Global optimization of Hölder functions

We propose a branch-and-bound framework for the global optimization of unconstrained Hölder functions. The general framework is used to derive two algorithms. The first one is a generalization of Piyavskii's algorithm for univariate Lipschitz functions. The second algorithm, using a piecewise constant upper-bounding function, is designed for multivariate Hölder functions. A proof of convergence is provided for both algorithms. Computational experience is reported on several test functions from the literature.     

On generalized weak subdifferentials and some properties

In this article, some characterizations for gw-subdifferentiability of functions from ? ⁿ to ? ^m are stated. Some criteria for gw-subdifferentiability of generalized lower locally Lipschitz functions and positively homogeneous functions are given. Furthermore, it is proved that every Lipschitz function is gw-subdifferentiable at any point in its domain. Finally, the relationship between directional derivative and gw-subdifferential is given and a convexity criteria for Fréchet differentiable function is given by using gw-subdifferential.     

Subvexormal Functions and Subvex Functions

Subvexormal functions and subinvexormal functions are proposed, whose properties are shared commonly by most generalized convex functions and most generalized invex functions, respectively. A necessary and sufficient condition for a subvexormal function to be subinvexormal is given in the locally Lipschitz and regular case. Furthermore, subvex functions and subinvex functions are introduced. It is proved that the class of strictly subvex functions is equivalent to that of functions whose local minima are global and that, in the locally Lipschitz and regular case, both strongly subvex functions and strongly subinvex functions can be characterized as functions whose relatively stationary points (slight extension of stationary points) are global minima.     

Univariate Global Optimization with Multiextremal Non-Differentiable Constraints Without Penalty Functions

This paper proposes a new algorithm for solving constrained global optimization problems where both the objective function and constraints are one-dimensional non-differentiable multiextremal Lipschitz functions. Multiextremal constraints can lead to complex feasible regions being collections of isolated points and intervals having positive lengths. The case is considered where the order the constraints are evaluated is fixed by the nature of the problem and a constraint i is defined only over the set where the constraint i−1 is satisfied. The objective function is defined only over the set where all the constraints are satisfied. In contrast to traditional approaches, the new algorithm does not use any additional parameter or variable. All the constraints are not evaluated during every iteration of the algorithm providing a significant acceleration of the search. The new algorithm either finds lower and upper bounds for the global optimum or establishes that the problem is infeasible. Convergence properties and numerical experiments showing a nice performance of the new method in comparison with the penalty approach are given. This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 04-01-00455-a. The author thanks Prof. D. Grimaldi for proposing the application discussed in the paper. An erratum to this article is available at .     

Polyanalytic Hardy decomposition of higher order Lipschitz functions

This paper is concerned with the problem of decomposing a higher order Lipschitz function on a closed Jordan curve Γ into a sum of two polyanalytic functions in each open domain defined by Γ. Our basic tools are the Hardy projections related to a singular integral operator arising in polyanalytic function theory, which, as it is proved here, represents an involution operator on the higher order Lipschitz classes. Our result generalizes the classical Hardy decomposition of Hölder continuous functions on the boundary of a domain.     

Exact barrier function methods for Lipschitz programs

The purpose of this paper is twofold. First we consider a class of nondifferentiable penalty functions for constrained Lipschitz programs and then we show how these penalty functions can be employed to solve a constrained Lipschitz program. The penalty functions considered incorporate a barrier term which makes their value go to infinity on the boundary of a perturbation of the feasible set. Exploiting this fact it is possible to prove, under mild compactness and regularity assumptions, a complete correspondence between the unconstrained minimization of the penalty functions and the solution of the constrained program, thus showing that the penalty functions are exact according to the definition introduced in [17]. Motivated by these results, we propose some algorithm models and study their convergence properties. We show that, even when the assumptions used to establish the exactness of the penalty functions are not satisfied, every limit point of the sequence produced by a basic algorithm model is an extended stationary point according to the definition given in [8]. Then, based on this analysis and on the one previously carried out on the penalty functions, we study the consequence on the convergence properties of increasingly demanding assumptions. In particular we show that under the same assumptions used to establish the exactness properties of the penalty functions, it is possible to guarantee that a limit point at least exists, and that any such limit point is a KKT point for the constrained problem.This research has been partially supported by the National Research Program on Metodi di Ottimizzazione per le Decisioni, Ministero dell' Università e della Ricerca Scientifica e Tecnologica.     

Differential Inclusions and Monotonicity Conditions for Nonsmooth Lyapunov Functions

In this paper we address the problem of characterizing the infinitesimal properties of functions which are nonincreasing along all the trajectories of a differential inclusion. In particular, we extend the condition based on the proximal gradient to the case of semicontinuous functions and Lipschitz continuous differential inclusions. Moreover, we show that the same criterion applies also in the case of Lipschitz continuous functions and continuous differential inclusions.     

Probabilistic Proof of Boundary Harnack Principle for α-Harmonic Functions

The boundary Harnack principle for fractional Laplacian is now known to hold in Lipschitz domains [5]. It states that if two nonnegative functions, harmonic with respect to a symmetric stable Lévy process vanish continuously outside a Lipschitz domain, near a part of its boundary, then the ratio of the functions is bounded inside the domain, near this part of the boundary. We give a probabilistic proof of the assertion using elementary properties of the stable process.     

An algorithm for minimizing a class of locally Lipschitz functions

In this paper, we present an algorithm for minimizing a class of locally Lipschitz functions. The method generalized the -smeared method to a class of functions whose Clarke generalized gradients are singleton at almost all differentiable poinst. We analyze the global convergence of the method and report some numerical results.This work was supported by the National Science Foundation of China. The authors would like to thank the referees for their valuable comments, which led to significant improvements in the presentation.     

Parallel global optimization of functions of several variables

On the basis of the method of nonuniform coverings, a parallel method for the global optimization of Lipschitzian functions is developed. This method is implemented in C-MPI for the global minimization of functions whose gradient satisfies the Lipschitz condition. The performance of the algorithm is demonstrated using the calculation of the structure of a protein molecule as an example.     

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.     

Relations between Lipschitz functions and convex functions

We discuss the relationship between Lipschitz functions and convex functions. By these relations, we give a sufficient condition for the set of points where Lipschitz functions on a Hilbert space is Frechet differentiate to be residual.     

Finding the Minimal Root of an Equation with the Multiextremal and Nondifferentiable Left-Hand Part

A problem very often arising in applications is presented: finding the minimal root of an equation with the objective function being multiextremal and nondifferentiable. Applications from the field of electronic measurements are given. Three methods based on global optimization ideas are introduced for solving this problem. The first one uses an a priori estimate of the global Lipschitz constant. The second method adaptively estimates the global Lipschitz constant. The third algorithm adaptively estimates local Lipschitz constants during the search. All the methods either find the minimal root or determine the global minimizers (in the case when the equation under consideration has no roots). Sufficient convergence conditions of the new methods to the desired solution are established. Numerical results including wide experiments with test functions, stability study, and a real-life applied problem are also presented.     

The boundary Harnack inequality for infinity harmonic functions in Lipschitz domains satisfying the interior ball condition

In this note, we give a short proof for the boundary Harnack inequality for infinity harmonic functions in a Lipschitz domain satisfying the interior ball condition. Our argument relies on the use of quasiminima and the notion of comparison with cones.     

Linearly constrained global minimization of functions with concave minorants

In this note, we show how a recent approach for solving linearly constrained multivariate Lipschitz optimization problems and corresponding systems of inequalities can be generalized to solve optimization problems where the objective function is only assumed to possess a concave minorant at each point. This class of functions includes not only Lipschitz functions and some generalizations, such as certain -convex functions and Hölder functions with exponent greater than one, but also all functions which can be expressed as differences of two convex functions (d.c. functions). Thus, in particular, a new approach is obtained for the important problem of minimizing a d.c. function over a polytope.     

Some Remarks on the Class of Continuous (Semi-) Strictly Quasiconvex Functions

We introduce the notion of variational (semi-) strict quasimonotonicity for a multivalued operator T  : X⇉X ^* relative to a nonempty subset A of X which is not necessarily included in the domain of T. We use this notion to characterize the subdifferentials of continuous (semi-) strictly quasiconvex functions. The proposed definition is a relaxation of the standard definition of (semi-) strict quasimonotonicity, the latter being appropriate only for operators with nonempty values. Thus, the derived results are extensions to the continuous case of the corresponding results for locally Lipschitz functions.     

A univariate global search working with a set of Lipschitz constants for the first derivative

In the paper, a global optimization problem is considered where the objective function f (x) is univariate, black-box, and its first derivative f ′(x) satisfies the Lipschitz condition with an unknown Lipschitz constant K. In the literature, there exist methods solving this problem by using an a priori given estimate of K, its adaptive estimates, and adaptive estimates of local Lipschitz constants. Algorithms working with a number of Lipschitz constants for f ′(x) chosen from a set of possible values are not known in spite of the fact that a method working in this way with Lipschitz objective functions, DIRECT, has been proposed in 1993. A new geometric method evolving its ideas to the case of the objective function having a Lipschitz derivative is introduced and studied in this paper. Numerical experiments executed on a number of test functions show that the usage of derivatives allows one to obtain, as it is expected, an acceleration in comparison with the DIRECT algorithm. This research was supported by the RFBR grant 07-01-00467-a and the grant 4694.2008.9 for supporting the leading research groups awarded by the President of the Russian Federation.     

Boundedness for commutators of Bochner-Riesz operators below a critical index

In this paper, the authors obtain a necessary and sufficient condition for the LP bound-edness of commutators generated by Bochner-Riesz operators below a critical index and Lipschitz functions in two dimensional case. The authors also discuss a similar problem for higher dimensions.