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.     

Heuristic reliability optimization by tabu search

A new heuristic algorithm, based on the tabu search methodology, is proposed for constrained redundancy optimization in series and in complex systems. It has the advantage of not being blocked as soon as a local optimum is found. Results given by the new method are compared with those of previous heuristics on a series of examples.We are grateful to R. Bulfin for making the code for reliability optimization of series systems he wrote with C.-Y. Liu available to us.Work of the first author was supported by NSERC Grant No. GP0105574, FCAR Grant No. 92EQ1048 and AFOSR Grant No. 90-0008 to Rutgers University.Work of the second author was partly supported by AFOSR Grant No. 90-0008 to Rutgers University while he was a graduate student.     

An analytical approach to global optimization

Global optimization problems with a few variables and constraints arise in numerous applications but are seldom solved exactly. Most often only a local optimum is found, or if a global optimum is detected no proof is provided that it is one. We study here the extent to which such global optimization problems can be solved exactly using analytical methods. To this effect, we propose a series of tests, similar to those of combinatorial optimization, organized in a branch-and-bound framework. The first complete solution of two difficult test problems illustrates the efficiency of the resulting algorithm. Computational experience with the programbagop, which uses the computer algebra systemmacsyma, is reported on. Many test problems from the compendiums of Hock and Schittkowski and others sources have been solved.The research of the first and the third authors has been supported by AFOSR grants #0271 and #0066 to Rutgers University. Research of the second author has been supported by NSERC grant #GP0036426 and FCAR grants #89EQ4144 and #90NC0305.     

Cutting planes and column generation techniques with the projective algorithm

The problem studied is that of solving linear programs defined recursively by column generation techniques or cutting plane techniques using, respectively, the primal projective method or the dual projective method.This research has been supported in part by FCAR of Quebec, Grant Nos. CE-130 and EQ-3078, by NSERC of Canada, Grant No. A4152, and by the Fonds National Suisse de la Recherche Scientifique, Grant No. 1.467.0.86.     

Preventive maintenance scheduling of power generating units

The problem of preventive maintenance planning of electric power generating units can be formulated as a mixed-integer linear optimization problem. An extension of the model is presented to deal with more realistic assumptions about utilization of power resource. We propose a heuristic iterative exchange procedure to solve these problems. We introduce two methods to prevent jamming situations outside the feasible domain or at a local optimum. The first method is a recursive exchange procedure called multiple exchanges method and the second relies on Lagrangian relaxation. Furthermore, we compare these procedures with a tabu search.This research was supported by NSERC (Grant A8312) and FCAR (Grant ER-0289).Michèle Charest had an NSERC Scholarship to work on this project.     

On the convergence of projection methods: Application to the decomposition of affine variational inequalities

In this paper, we first discuss the global convergence of symmetric projection methods for solving nonlinear monotone variational inequalities under a cocoercivity assumption. A similar analysis is applied to asymmetric projection methods, when the mapping is affine and monotone. Under a suitable choice of the projection matrix, decomposition can be achieved. It is proved that this scheme achieves a linear convergence rate, thus enhancing results previously obtained by Tseng (Ref. 1) and by Luo and Tseng (Ref. 2).The research of the first author was supported by NSERC Grant A5789 and DND-FUHBP. The research of the second author was supported by NSERC Grant OGP-0157735.The authors are indebted to the referees and Associate Editor P. Tseng for their constructive comments.     

Clustering via minimum volume ellipsoids

We propose minimum volume ellipsoids (MVE) clustering as an alternative clustering technique to k-means for data clusters with ellipsoidal shapes and explore its value and practicality. MVE clustering allocates data points into clusters in a way that minimizes the geometric mean of the volumes of each cluster’s covering ellipsoids. Motivations for this approach include its scale-invariance, its ability to handle asymmetric and unequal clusters, and our ability to formulate it as a mixed-integer semidefinite programming problem that can be solved to global optimality. We present some preliminary empirical results that illustrate MVE clustering as an appropriate method for clustering data from mixtures of “ellipsoidal” distributions and compare its performance with the k-means clustering algorithm as well as the MCLUST algorithm (which is based on a maximum likelihood EM algorithm) available in the statistical package R. Research of the first author was supported in part by a Discovery Grant from NSERC and a research grant from Faculty of Mathematics, University of Waterloo. Research of the second author was supported in part by a Discovery Grant from NSERC and a PREA from Ontario, Canada.     

The Global Convergence of Self-Scaling BFGS Algorithm with Nonmonotone Line Search for Unconstrained Nonconvex Optimization Problems

The self-scaling quasi-Newton method solves an unconstrained optimization problem by scaling the Hessian approximation matrix before it is updated at each iteration to avoid the possible large eigenvalues in the Hessian approximation matrices of the objective function. It has been proved in the literature that this method has the global and superlinear convergence when the objective function is convex （or even uniformly convex）. We propose to solve unconstrained nonconvex optimization problems by a self-scaling BFGS algorithm with nonmonotone linear search. Nonmonotone line search has been recognized in numerical practices as a competitive approach for solving large-scale nonlinear problems. We consider two different nonmonotone line search forms and study the global convergence of these nonmonotone self-scale BFGS algorithms. We prove that, under some weaker condition than that in the literature, both forms of the self-scaling BFGS algorithm are globally convergent for unconstrained nonconvex optimization problems.     

An application of discrete-event theory to truck dispatching

This article focuses on the dispatching problem of an oilsand excavation process subject to production objectives and specifications. Herein, we cast the truck dispatching task in a decision-making framework for determining solutions and helping a dispatcher to make decisions. In this paper, we apply the discrete-event formalism to investigate the dispatching of a large truck fleet. For this purpose, we examine the capabilities and limitations of two distinct theories: discrete-event system (DES) and vector discrete-event system (VDES). Despite their differences, both theories can be used to model the logical structure of the dispatching process. These theories also provide techniques for implementing specifications and representing solutions in a compact manner. The results of this paper demonstrate that current procedures and tools available for DES allow a broader range of techniques to be applied, thus increasing the likelihood of finding a suitable solution. This work was supported, in part, by the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canadian Foundation for Innovation and PRECARN and associates. In addition, the first author was supported by NSERC, Fonds pour la formation de Chercheurs et l’Aide a la Recherche (FCAR), and Ontario Graduate Scholarships (OGS).     

On the congruence lattice of a Scott-domain

We prove that the congruence lattice of a Scott-domain can be characterized as a complete lattice.Presented by V. Trnkova.The research of the first author was supported by the NSERC of Canada.The research of the second author was supported by the Hungarian National Foundation for Scientific Research, under Grant No. 1903.     

Invariance and efficiency of convex representations

We consider two notions for the representations of convex cones G-representation and lifted-G-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones are invariant under one notion of representation but not the other. In particular, we prove that lifted-G-representation is closed under duality when the representing cone is self-dual. We also prove that strict complementarity of a convex optimization problem in conic form is preserved under G-representations. Then we move to study efficiency measures for representations. We evaluate the representations of homogeneous convex cones based on the “smoothness” of the transformations mapping the central path of the representation to the central path of the represented optimization problem. Research of the first author was supported in part by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC. Research of the second author was supported in part by a Discovery Grant from NSERC and a PREA from Ontario, Canada.     

Maximal chains inωω and ultrapowers of the integers

Summary Various questions posed by P. Nyikos concerning ultrafilters on and chains in the partial order (, <^*) are answered. The main tool is the oracle chain condition and variations of it.The first author is partially supported by the basic research fund of the Israeli Academy. The second author is partially supported by NSERC and was a guest of Rutgers University while the research on this paper was being done. The authors would also like to thank P. Nyikos for his valuable comments on early versions of this paper. This is number 465 on the first author's list of publications     

Complete solution of a family of quartic Thue equations

This paper evolved from a visit of the first author to the University of Debrecen, Hungary, which was supported by the Austrian-Hungarian Science Cooperation project Nr. 10-U-3. Research of the second author was partially supported by Hungarian National Foundation for Scientific Research Grant 1641/90.     

A constructive method for starlike harmonic mappings

Summary The idea initiated by Opfer for constructing conformal mappings from the disk onto starlike domains is generalized for univalent harmonic mappings. This is of some interest, since such mappings are not characterized by analytic means.This work was supported in partsby a Promotion of Research Grant from the TECHNION, Haifaby an Undergraduate Student Research A ward from the NSERCby grants from the NSERC and the FCAR     

Topological spaces and quasi-varieties

We describe Top ^op and Sob ^op as quasi-varieties by means of suitable schizophrenic objects.Research of the first author supported by grants from the NSERC of Canada and the FCAR du Québec. Research of the second author supported by the Topology grant 40% and by the NATO grant CRG 941330.     

Holey self-orthogonal Latin squares with symmetric orthogonal mates

We improve the existence results for holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) and show that the necessary conditions for the existence of a HSOLSSOM of typeh ⁿ are also sufficient with at most 28 pairs (h, n) of possible exceptions. Research supported in part by NSERC Grant A-5320 for the first author, NSF Grants CCR-9504205 and CCR-9357851 for the second author, and NSFC Grant 19231060-2 for the third author.     

Best simultaneous approximation to totally bounded sequences in Banach spaces

This paper is concerned with the problem of best weighted simultaneous approximations to totally bounded sequences in Banach spaces. Characterization results from convex sets in Banach spaces are established under the assumption that the Banach space is uniformly smooth. The first author is supported in part by Scientific Research Fund of Hunan Provincial Education Department (Grant No. 06C651); the second author is supported in part by the National Natural Science Foundation of China (Grant Nos. 10671175, 10731060) and Program for New Century Excellent Talents in University; the third author is supported in part by Projects MTM2006-13997-C02-01 and FQM-127 of Spain     

Bounds on the size of tetrahedralizations

This paper gives lower and upper bounds on the complexity of triangulating the region between polyhedra. Particular attention is given to the case of convex polyhedra and terrains. The first author was suported in part by NSF Grant CCR-90-02352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. The second author was supported in part by NSF Grant PHY-90-21984.     

Pure Point Diffractive Substitution Delone Sets Have the Meyer Property

We prove that a primitive substitution Delone set, which is pure point diffractive, is a Meyer set. This answers a question of J.C. Lagarias. We also show that for primitive substitution Delone sets, being a Meyer set is equivalent to having a relatively dense set of Bragg peaks. The proof is based on tiling dynamical systems and the connection between the diffraction and dynamical spectra. The first author acknowledges support from the NSERC post-doctoral fellowship and thanks the University of Washington and the University of Victoria for being the host universities of the fellowship. The second author is grateful to the Weizmann Institute of Science where he was a Rosi and Max Varon Visiting Professor when this work was completed. He was also supported in part by NSF Grant DMS 0355187.     

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.