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.     

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.     

Deterministic equivalent for a continuous-time linear-convex stochastic control problem

We consider a finite-horizon control model with additive input. There are two convex functions which describe the running cost and the terminal cost within the system. The cost of input is proportional to the input and can take both positive and negative values. It is shown that there exists a deterministic control problem whose optimal cost is the same as the one in the stochastic control problem. The optimal policy for the stochastic problem consists of keeping the process as close to the optimal deterministic trajectory as possible.This research is supported by NSERC Grant A4619, MRCO, NSF Grant DMS-86-01510, and AFOSR Grant 87-0278.     

Nonlinear programming via an exact penalty function: Global analysis

In this paper we motivate and describe an algorithm to solve the nonlinear programming problem. The method is based on an exact penalty function and possesses both global and superlinear convergence properties. We establish the global qualities here (the superlinear nature is proven in [7]). The numerical implementation techniques are briefly discussed and preliminary numerical results are given.This work is supported in part by NSERC Grant No. A8639 and the U.S. Dept. of Energy.     

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.     

Generalized linear complementarity problems treated without fixed-point theory

We study the (monotone) linear complementarity problem in reflexive Banach space. The problem is treated as a quadratic program and shown to satisfy appropriate constraint qualifications. This leads to a theory of the generalized monotone linear complementarity problem which is independent of Brouwer's fixed-point theorem. Certain related results on linear systems are given. The final section concerns copositive operators.This research was partially supported by NSERC Grant No. A-5516.The author thanks the referee for his painstaking and thorough comments on this paper.     

Camera placement in integer lattices

The camera placement problem concerns the placement of a fixed number of point-cameras on thed-dimensional integer lattice in order to maximize their visibility. We reduce the problem to a finite discrete optimization problem and give a characterization of optimal configurations of size at most 3 ^d . A preliminary version of this work appears in [8]. The research of E. Kranakis was supported by NSERC Grant No. 907002.     

Stochastic variational inequalities of parabolic type

Existence and uniqueness of strong solutions of stochastic partial differential equations of parabolic type with reflection (e.g., the solutions are never allowed to be negative) is proved. The problem is formulated as a stochastic variational inequality and then compactness is used to derive the result, but the method requires the space dimension to be one.This research was supported by NSERC under Grant No. 8051.     

Finite axiomatizations for existentially closed posets and semilattices

In this paper we exhibit axiomatizations for the theories of existentially closed posets and existentially closed semilattices. We do this by considering an infinite axiomatization which characterizes these structures in terms of embeddings of finite substructures, an axiomatization which exists for any locally finite universal class with a finite language and with the joint embedding and amalgamation properties. We then find particular finite subsets of these axioms which suffice to axiomatize both classes. Research supported by an NSERC Postdoctoral Fellowship. Research supported by NSERC Grant No. A7256.     

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.     

How to compute least infeasible flows

It is well-known how to use maximum flow to decide when a flow problem with demands, lower bounds, and upper bounds is infeasible. Less well-known is how to compute a flow that is least infeasible. This paper considers many possible ways to define “least infeasible” and shows how to compute optimal flows for each definition. For each definition it also gives a dual characterization in terms of cuts, a polynomial routine for recognizing that type of least infeasible flow, and relates that definition to dual cut canceling min-cost flow network algorithms. This research was partially supported by an NSERC Operating Grant, an NSERC Grant for Research Abroad, and a UBC Killam Faculty Study Leave Fellowship. Parts of this research were done while the author was visiting Laboratoire ARTEMIS IMAG at Université Joseph Fourier de Grenoble, France.     

The characters of supercuspidal representations as weighted orbital integrals

Weighted orbital integrals are the terms which occur on the geometric side of the trace formula. We shall investigate these distributions on ap-adic group. We shall evaluate the weighted orbital integral of a supercuspidal matrix coefficient as a multiple of the corresponding character. Supported in part by NSERC Operating Grant A3483.     

Cord-slope form of Taylor's expansion in univariate global optimization

Interval arithmetic and Taylor's formula can be used to bound the slope of the cord of a univariate function at a given point. This leads in turn to bounding the values of the function itself. Computing such bounds for the function, its first and second derviatives, allows the determination of intervals in which this function cannot have a global minimum. Exploiting this information together with a simple branching rule yields an efficient algorithm for global minimization of univariate functions. Computational experience is reported.The first and second authors have been supported by FCAR (Fonds pour la Formation de Chercheurs et l'Aide à la Recherche) Grant 92EQ1048 and AFOSR Grant 90-0008 to Rutgers University. The first author has also been supported by NSERC (Natural Sciences and Engineering Research Council of Canada) Grant to HEC and NSERC Grant GP0105574. The second author has been supported by NSERC Grant GP0036426, FCAR Grant 90NC0305, and a NSF Visiting Professorship for Women in Science at Princeton University. Work of the third author was done in part while he was a graduate student at the Department of Mathematics, Rutgers University, New Brunswick, New Jersey, USA and during a visit to GERAD, June–August 1991.     

Studying an overload system using rotation

1. IntroductionThe motivation of writing this paper was from calculating the blocking probability foran overloaded finite system. Our numerical experiments suggested that this probability canbe approximated efficiently by rotating the transition matrix by 180". Some preliminaryresults were obtained and can be found in [11 and [2]. Rotating the transition matrix definesa new Markov chain, which is often called the dual process in the literature, for example,[3--7]. For a finite Markov chain, …     

Rate of convergence of transport processes with an application to stochastic differential equations

Summary We obtain a rate of convergence of uniform transport processes to Brownian motion, which we apply to the Wong and Zakai approximation of stochastic integrals.The research of both authors was supported by a NSERC Canada Grant and by an EMR Canada Grant of M. Csörgö at Carleton University, Ottawa     

On solving three classes of nonlinear programming problems via simple differentiable penalty functions

We consider the following classes of nonlinear programming problems: the minimization of smooth functions subject to general constraints and simple bounds on the variables; the nonlinearl ₁-problem; and the minimax problem. Numerically reliable methods for solving problems in each of these classes, based upon exploiting the structure of the problem in constructing simple differentiable penalty functions, are presented.This research was made possible by NSERC Grant No. A8442.The author would like to thank Mrs. J. Selwood of the Department of Combinatories and Optimization, University of Waterloo, Ontario, Canada for her excellent typesetting.This work was carried out in the Department of Combinatories and Optimization, University of Waterloo, Waterloo, Ontario, Canada.     

Relaxation methods for monotropic programs

We propose a dual descent method for the problem of minimizing a convex, possibly nondifferentiable, separable cost subject to linear constraints. The method has properties reminiscent of the Gauss-Seidel method in numerical analysis and uses the-complementary slackness mechanism introduced in Bertsekas, Hosein and Tseng (1987) to ensure finite convergence to near optimality. As special cases we obtain the methods in Bertsekas, Hosein and Tseng (1987) for network flow programs and the methods in Tseng and Bertsekas (1987) for linear programs.Work supported by the National Science Foundation under grant NSF-ECS-8519058 and by the Army Research Office under grant DAAL03-86-K-0171.This author is also supported by Canadian NSERC under Grant U0505.     

On countable homogeneous 3-hypergraphs

Summary We present some results on countable homogeneous 3-hypergraphs. In particular, we show that there is no unexpected homogeneous 3-hypergraph determined by a single constraint.The authors are grateful for support from NSERC (Canada) Grant A3040     

The strong fixed point property for small sets

It is shown that every partially ordered set with the fixed point property and with ten or fewer elements actually has the strong fixed point property.Supported by NSERC Operating Grant A7884.Supported by NSERC Operating Grant 41702.     

A theory of rolling horizon decision making

In this paper, we develop a theoretical framework for the common business practice of rolling horizon decision making. The main idea of our approach is that the usefulness of rolling horizon methods is, to a great extent, implied by the fact that forecasting the future is a costly activity. We, therefore, consider a general, discrete-time, stochastic dynamic optimization problem in which the decision maker has the possibility to obtain information on the uncertain future at given cost. For this non-standard optimization problem with optimal stopping decisions, we develop a dynamic programming formulation. We treat both finite and infinite horizon cases. We also provide a careful interpretation of the dynamic programming equations and illustrate our results by a simple numerical example. Various generalizations are shown to be captured by straightforward modifications of our model.This research is supported in part by NSERC Grant A4619, SSHRC Grant 410-87-0524, and Manufacturing Research Corporation of Ontario. Comments and suggestions from Qing Zhang and the referees are gratefully acknowledged.