First- and second-order methods for semidefinite programming

 In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity. Received: December 16, 2002 / Accepted: May 5, 2003 Published online: May 28, 2003 Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods – nonlinear programming – Newton method – first-order methods – bundle method – matrix completion The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401. Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

Beckman-Quarles type theorems for mappings from $$ \mathbb{R}^n $$ to $$ \mathbb{C}^n $$

Summary. Let We say that preserves the distance d 0 if for each implies Let A _n denote the set of all positive numbers d such that any map that preserves unit distance preserves also distance d. Let D _n denote the set of all positive numbers d with the property: if and then there exists a finite set S _xy with such that any map that preserves unit distance preserves also the distance between x and y. Obviously, We prove: (1) (2) for n 2 D _n is a dense subset of (2) implies that each mapping f from to (n 2) preserving unit distance preserves all distances, if f is continuous with respect to the product topologies on and      

Singularity formation in the Yang-Mills Flow

It is shown that, for the Yang-Mills flow, a sequence of blow-ups of a rapidly forming singularity will converge, modulo the gauge group, to a non-trivial homothetically shrinking soliton. Explicit examples of homothetically shrinking solitons are given in the case of trivial bundles over R ⁿ for .Received: 22 November 2002, Accepted: 12 March 2003, Published online: 6 June 2003Mathematics Subject Classification (2000): 53C44     

Polynomial Pell's equation

Consider the polynomial Pell's equation , where is a monic polynomial in and . Then for , , and , a necessary and sufficient condition for the polynomial Pell's equation to have a nontrivial solution in is obtained.

     

An equivalent definition of stable Equilibria

Characterisations of stable equilibria in terms of the best reply correspondence are given.Received January 2003JEL Classification: C72, C73.1991 Mathematics Subject Classification: 90D05, 90D10, 90D20This work was supported in part by N.S.F. Grant #SES 8922610.     

Castelnuovo-Mumford regularity of simplicial semigroup rings with isolated singularity

Let be the polynomial ring in variables over a field and its graded maximal ideal. Let be homogeneous polynomials of degree generating an -primary ideal, and let be arbitrary homogeneous polynomials of degree . In the present paper it will be proved that the Castelnuovo-Mumford regularity of the standard graded -algebra is at most . By virtue of this result, it follows that the regularity of a simplicial semigroup ring with isolated singularity is at most , where is the multiplicity of and is the codimension of .

     

Extrinsic Killing spinors

 Under intrinsic and extrinsic curvature assumptions on a Riemannian spin manifold and its boundary, we show that there is an isomorphism between the restriction to the boundary of parallel spinors and extrinsic Killing spinors of non-negative Killing constant. As a corollary, we prove that a complete Ricci-flat spin manifold with mean-convex boundary isometric to a round sphere, is necessarily a flat disc. Received: 2 February 2002; in final form: 1 August 2002 / Published online: 1 April 2003 Mathematics Subject Classification (1991): 53C27, 53C40, 53C80, 58G25 The authors would like to thank Lars Andersson for helpful discussions and for bringing to our knowledge the information regarding Remark 4. We are also grateful to the referee for pointing out that Corollary 5 and Corollary 6 are only valid when the boundary is at least 2-dimensional. Research of S. Montiel is partially supported by a Spanish MCyT grant No. BFM2001-2967     

Limitations on the extendibility of the Radon-Nikodym Theorem

Given two locally compact spaces and a continuous map the Banach lattice is naturally a -module. Following the Bourbaki approach to integration we define generalized measures as -linear functionals . The construction of an -space and the concepts of absolute continuity and density still make sense. However we exhibit a counter-example to the natural generalization of the Radon-Nikodym Theorem in this context.

     

Stochastic programming with integer variables

 Including integer variables into traditional stochastic linear programs has considerable implications for structural analysis and algorithm design. Starting from mean-risk approaches with different risk measures we identify corresponding two- and multi-stage stochastic integer programs that are large-scale block-structured mixed-integer linear programs if the underlying probability distributions are discrete. We highlight the role of mixed-integer value functions for structure and stability of stochastic integer programs. When applied to the block structures in stochastic integer programming, well known algorithmic principles such as branch-and-bound, Lagrangian relaxation, or cutting plane methods open up new directions of research. We review existing results in the field and indicate departure points for their extension. Received: December 2, 2002 / Accepted: April 23, 2003 Published online: May 28, 2003 Mathematics Subject Classification (2000): 90C15, 90C11, 90C06, 90C57     

Real quadratic fields with class number divisible by 3

 We shall show that the number of real quadratic fields whose absolute discriminant is ≤ x and whose class number is divisible by 3 is improving the existing best known bound of K. Chakraborty and R. Murty. Received: 7 January 2003 Published online: 19 May 2003 This work was supported by Korea Research Foundation Grant KRF-2002-003-C00001. Mathematics Subject Classification(2000): 11R11, 11R29     

Maximal complexifications of certain homogeneous Riemannian manifolds

Let be a homogeneous Riemannian manifold with , where denotes the universal complexification of . Under certain extensibility assumptions on the geodesic flow of , we give a characterization of the maximal domain of definition in for the adapted complex structure and show that it is unique. For instance, this can be done for generalized Heisenberg groups and naturally reductive homogeneous Riemannian spaces. As an application it is shown that the case of generalized Heisenberg groups yields examples of maximal domains of definition for the adapted complex structure which are neither holomorphically separable nor holomorphically convex.

     

Graphs that are not complete pluripolar

Let be domains in . Under very mild conditions on we show that there exist holomorphic functions , defined on with the property that is nowhere extendible across , while the graph of over is not complete pluripolar in . This refutes a conjecture of Levenberg, Martin and Poletsky (1992).

     

Bounds on leaves of one-dimensional foliations

Let X be a variety over an algebraically closed field, a onedimensional singular foliation, and a projective leaf of . We prove that

A note on Weyl's theorem for operator matrices

When and are given we denote by an operator acting on the Banach space of the form

In this note we examine the relation of Weyl's theorem for and through local spectral theory.

     

Behavior of the Bergman kernel and metric near convex boundary points

The boundary behavior of the Bergman metric near a convex boundary point of a pseudoconvex domain is studied. It turns out that the Bergman metric at points in the direction of a fixed vector tends to infinity, when is approaching , if and only if the boundary of does not contain any analytic disc through in the direction of .

     

Longtime existence of the Lagrangian mean curvature flow

Given a compact Lagrangian submanifold in flat space evolving by its mean curvature, we prove uniform -bounds in space and C²-estimates in time for the underlying Monge-Ampére equation under weak and natural assumptions on the initial Lagrangian submanifold. This implies longtime existence and convergence of the Lagrangian mean curvature flow. In the 2-dimensional case we can relax our assumptions and obtain two independent proofs for the same result.Received: 3 September 2002, Accepted: 12 June 2003, Published online: 4 September 2003Mathematics Subject Classification (2000): 53C44     

Some stable vector bundles with reducible theta divisor

 Let C be a curve of genus g and L a line bundle of degree 2g on C. Let M_L be the kernel of the evaluation map . We show that when L is general enough, the rank g bundle M_L and its exterior powers are stable, but admit a reducible theta divisor. Received: 16 September 2002 / Revised version: 29 October 2002 Published online: 14 February 2003 Mathematics Subject Classification (2000): 14H60