Geometry of homogeneous convex cones,duality mapping,and optimal self-concordant barriers

We study homogeneous convex cones. We first characterize the extreme rays of such cones in the context of their primal construction (due to Vinberg) and also in the context of their dual construction (due to Rothaus). Then, using these results, we prove that every homogeneous cone is facially exposed. We provide an alternative proof of a result of Güler and Tunç el that the Siegel rank of a symmetric cone is equal to its Carathéodory number. Our proof does not use the Jordan-von Neumann-Wigner characterization of the symmetric cones but it easily follows from the primal construction of the homogeneous cones and our results on the geometry of homogeneous cones in primal and dual forms. We study optimal self-concordant barriers in this context. We briefly discuss the duality mapping in the context of automorphisms of convex cones and prove, using numerical integration, that the duality mapping is not an involution on certain self-dual cones.Research of this author was supported in part by a Summer Undergraduate Research Assistantship Award from NSERC (Summer 2001) and a research grant from NSERC while she was an undergraduate student at Faculty of Mathematics, University of Waterloo.Research of this author was supported in part by a PREA from Ontario, Canada and research grants from NSERC. Corresponding author.Mathematics Subject Classification (2000): 90C25, 90C51, 90C60, 90C05, 65Y20, 52A41, 49M37, 90C30     

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.     

“Cone-free” primal-dual path-following and potential-reduction polynomial time interior-point methods

We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the problem (as is, without a conic reformulation) using the very usual primal central path concept and a less usual version of a dual path concept. We show that many of the advantages of the primal-dual interior-point techniques are available to us in this framework and therefore, they are not intrinsically tied to the conic reformulation and the logarithmic homogeneity of the underlying barrier function.Part of the research was done while the author was a Visiting Professor at the University of Waterloo.Research of this author is supported in part by a PREA from Ontario and by a NSERC Discovery Grant. Tel: (519) 888-4567 ext.5598, Fax: (519) 725-5441Mathematics Subject Classification (2000): 90C51, 90C25, 65Y20,90C28, 49D49     

Characterization of the barrier parameter of homogeneous convex cones

We characterize the smallest (best) barrier parameter of self-concordant barriers for homogeneous convex cones. In particular, we prove that this parameter is the same as the rank of the cone which is the number of steps in a recursive construction of the cone (Siegel domain construction). We also provide lower bounds on the barrier parameter in terms of the Carathéodory number of the cone. The bounds are tight for homogeneous self-dual cones. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by an operating grant from NSERC of Canada.Research supported in part by the National Science Foundation under grant DMS-9306318.     

Bases of convex cones and Borwein's proper efficiency

In this note, we establish some interesting relationships between the existence of Borwein's proper efficient points and the existence of bases for convex ordering cones in normed linear spaces. We show that, if the closed unit ball in a smooth normed space ordered by a convex cone possesses a proper efficient point in the sense of Borwein, then the ordering cone is based. In particular, a convex ordering cone in a reflexive space is based if the closed unit ball possesses a proper efficient point. Conversely, we show that, in any ordered normed space, if the ordering cone has a base, then every weakly compact set possesses a proper efficient point.The research was conducted while the author was working on his PhD Degree under the supervision of Professor J. M. Borwein, whose guidance and valuable suggestions are gratefully appreciated. The author would like to thank two anonymous referees for their constructive comments and suggestions. This research was supported by an NSERC grant and a Mount Saint Vincent University Research Grant.     

Representations and positive functionals

We discuss the representation theory of both the locally convex and non-locally convex topological^*-algebras. First we discuss the^*-representation of topological^*-algebras by operators on a Hilbert space. Then we study those topological^*-algebras so that every^*-representation of which on a Hilbert space is necessarily continuous. It is well-known that each^*-representation of aB ^*-algebra on a Hilbert space is continuous. We show that this is true for a large class of^*-algebras more general thanB ^*-algebras, including certain non-locally convex^*-algebras. Finally, we investigate the conditions under which a positive functional on a topological^*-algebra is representable.The research of the first-named author was partially supported by an NSERC grant. This work was done by the second-named author when he was a post-doctoral fellow at McMaster University.     

Multipasting of lattices

In this paper we introduce a lattice construction, calledmultipasting, which is a common generalization of gluing, pasting, andS-glued sums. We give a Characterization Theorem which generalizes results for earlier constructions. Multipasting is too general to prove the analogues of many known results. Therefore, we investigate in some detail three special cases: strong multipasting, multipasting of convex sublattices, and multipasting with the Interpolation Property.Presented by R. Freese.The research of the first and the third authors was supported by the Hungarian National Foundation for Scientific Research, under Grant No. 1813. The research of the second author was supported by the NSERC of Canada.     

Analyticity of weighted central paths and error bounds for semidefinite programming

The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary solutions. Secondly, we consider a sequence of primal–dual solutions that lies within a prescribed neighborhood of the central path of a pair of primal–dual semidefinite programming problems, and converges to the respective optimal faces. Under the additional assumption of strict complementarity, we derive two necessary and sufficient conditions for the sequence of primal–dual solutions to converge linearly with their duality gaps. This research was supported by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC.     

A microscopic convexity principle for nonlinear partial differential equations

We study microscopic convexity property of fully nonlinear elliptic and parabolic partial differential equations. Under certain general structure condition, we establish that the rank of Hessian ∇ ² u is of constant rank for any convex solution u of equation F(∇ ² u,∇ u,u,x)=0. The similar result is also proved for parabolic equations. Some of geometric applications are also discussed. Research of the first author was supported in part by NSFC No.10671144 and National Basic Research Program of China (2007CB814903). Research of the second author was supported in part by an NSERC Discovery Grant.     

Amenability and weak amenability of the Fourier algebra

Let G be a locally compact group. We show that its Fourier algebra A(G) is amenable if and only if G has an abelian subgroup of finite index, and that its Fourier–Stieltjes algebra B(G) is amenable if and only if G has a compact, abelian subgroup of finite index. We then show that A(G) is weakly amenable if the component of the identity of G is abelian, and we prove some partial results towards the converse.Research supported by NSERC under grant no. 90749-00.Research supported by NSERC under grant no. 227043-00.     

Some Geometrical Aspects of Efficient Points in Vector Optimization

We study efficient point sets in terms of extreme points, positive support points and strongly positive exposed points. In the case when the ordering cone has a bounded base, we prove that the efficient point set of a weakly compact convex set is contained in the closed convex hull of its strongly positive exposed points, thereby extending the Phelps theorem. We study also the density of positive proper efficient point sets. This research was supported by a Central Research Grant of Hong Kong Polytechnic University, Grant G-T 507. Research of the first author was also supported by the National Natural Science Foundation of P.R. China, Grant 10361008, and the Natural Science Foundation of Yunnan Province, China, Grant 2003A002M. Research of the second author was also supported by the Natural Science Foundation of Chongqing. Research of the third author was supported by a research grant from Australian Research Counsil.     

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.     

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.     

Descent constructions for central extensions of infinite dimensional Lie algebras

We use Galois descent to construct central extensions of twisted forms of split simple Lie algebras over rings. These types of algebras arise naturally in the construction of Extended Affine Lie Algebras. The construction also gives information about the structure of the group of automorphisms of such algebras. A. Pianzola is supported by the NSERC Discovery Grant Program. The author also wishes to thank the Instituto Argentino de Matemática for their hospitality. D. Prelat is supported by a Research Grant from Universidad CAECE.     

Super efficiency in convex vector optimization

We establish a Lagrange Multiplier Theorem for super efficiency in convex vector optimization and express super efficient solutions as saddle points of appropriate Lagrangian functions. An example is given to show that the boundedness of the base of the ordering cone is essential for the existence of super efficient points.Research is supported partially by NSERC.Research is supported partially by NSERC and Mount St. Vincent University grant.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

Representations of quasi-Newton matrices and their use in limited memory methods

We derive compact representations of BFGS and symmetric rank-one matrices for optimization. These representations allow us to efficiently implement limited memory methods for large constrained optimization problems. In particular, we discuss how to compute projections of limited memory matrices onto subspaces. We also present a compact representation of the matrices generated by Broyden's update for solving systems of nonlinear equations.These authors were supported by the Air Force Office of Scientific Research under Grant AFOSR-90-0109, the Army Research Office under Grant DAAL03-91-0151 and the National Science Foundation under Grants CCR-8920519 and CCR-9101795.This author was supported by the U.S. Department of Energy, under Grant DE-FG02-87ER25047-A001, and by National Science Foundation Grants CCR-9101359 and ASC-9213149.     

Contingent cone to a set defined by equality and inequality constraints at a Fréchet differentiable point

In this paper, we prove equality expression for the contingent cone and the strict normal cone to a set determined by equality and/or inequality constraints at a Fréchet differentiable point. A similar result has appeared before in the literature under the assumption that all the constraint functions are of classC or under the assumption that the functions are strictly differentiable at the point in question. Our result has applications to the calculation of various kinds of tangent cones and normal cones.This research was supported, in part by the National Science and Engineering Research Council of Canada under Grant No. OGP-41983.The authors would like to thank D. E. Ward for his many helpful comments.     

The structure of admissible points with respect to cone dominance

We study the set of admissible (Pareto-optimal) points of a closed, convex setX when preferences are described by a convex, but not necessarily closed, cone. Assuming that the preference cone is strictly supported and making mild assumptions about the recession directions ofX, we extend a representation theorem of Arrow, Barankin, and Blackwell by showing that all admissible points are either limit points of certainstrictly admissible alternatives or translations of such limit points by rays in the closure of the preference cone. We also show that the set of strictly admissible points is connected, as is the full set of admissible points.Relaxing the convexity assumption imposed uponX, we also consider local properties of admissible points in terms of Kuhn-Tucker type characterizations. We specify necessary and sufficient conditions for an element ofX to be a Kuhn-Tucker point, conditions which, in addition, provide local characterizations of strictly admissible points.Several results from this paper were presented in less general form at the National ORSA/TIMS Meeting, Chicago, Illinois, 1975.This research was supported, in part, by the United States Army Research Office (Durham), Grant No. DAAG-29-76-C-0064, and by the Office of Naval Research, Grant No. N00014-67-A-0244-0076. The research of the second author was partially conducted at the Center for Operations Research and Econometrics (CORE), Université Catholique de Louvain, Heverlee, Belgium.The authors are indebted to A. Assad for several helpful discussions and to A. Weiczorek for his careful reading of an earlier version of this paper.     

Covering numbers for Chevalley groups

LetG be a quasisimple Chevalley group. We give an upper bound for the covering number cn(G) which is linear in the rank ofG, i.e. we give a constantd such that for every noncentral conjugacy classC ofG we haveC ^rd =G, wherer=rankG. Research supported in part by NSERC Canada Grant A7251. Research supported in part by the Hermann Minkowski-Minerva Center for Geometry at Tel Aviv University.