A parallel inexact newton method for stochastic programs with recourse

A parallel inexact Newton method with a line search is proposed for two-stage quadratic stochastic programs with recourse. A lattice rule is used for the numerical evaluation of multi-dimensional integrals, and a parallel iterative method is used to solve the quadratic programming subproblems. Although the objective only has a locally Lipschitz gradient, global convergence and local superlinear convergence of the method are established. Furthermore, the method provides an error estimate which does not require much extra computation. The performance of the method is illustrated on a CM5 parallel computer.This work was supported by the Australian Research Council and the numerical experiments were done on the Sydney Regional Centre for Parallel Computing CM5.     

Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices

The sum of the largest eigenvalues of a symmetric matrix is a nonsmooth convex function of the matrix elements. Max characterizations for this sum are established, giving a concise characterization of the subdifferential in terms of a dual matrix. This leads to a very useful characterization of the generalized gradient of the following convex composite function: the sum of the largest eigenvalues of a smooth symmetric matrix-valued function of a set of real parameters. The dual matrix provides the information required to either verify first-order optimality conditions at a point or to generate a descent direction for the eigenvalue sum from that point, splitting a multiple eigenvalue if necessary. Connections with the classical literature on sums of eigenvalues and eigenvalue perturbation theory are discussed. Sums of the largest eigenvalues in the absolute value sense are also addressed.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.The work of this author was supported by the National Science Foundation under grants CCR-8802408 and CCR-9101640.The work of this author was supported in part during a visit to Argonne National Laboratory by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under contract W-31-109-Eng-38, and in part during a visit to the Courant Institute by the U.S. Department of Energy under Contract DEFG0288ER25053.     

An Algorithm Based on Active Sets and Smoothing for Discretized Semi-Infinite Minimax Problems

We present a new active-set strategy which can be used in conjunction with exponential (entropic) smoothing for solving large-scale minimax problems arising from the discretization of semi-infinite minimax problems. The main effect of the active-set strategy is to dramatically reduce the number of gradient calculations needed in the optimization. Discretization of multidimensional domains gives rise to minimax problems with thousands of component functions. We present an application to minimizing the sum of squares of the Lagrange polynomials to find good points for polynomial interpolation on the unit sphere in ℝ³. Our numerical results show that the active-set strategy results in a modified Armijo gradient or Gauss-Newton like methods requiring less than a quarter of the gradients, as compared to the use of these methods without our active-set strategy. Finally, we show how this strategy can be incorporated in an algorithm for solving semi-infinite minimax problems.     

Quasi-Monte Carlo for Highly Structured Generalised Response Models

Highly structured generalised response models, such as generalised linear mixed models and generalised linear models for time series regression, have become an indispensable vehicle for data analysis and inference in many areas of application. However, their use in practice is hindered by high-dimensional intractable integrals. Quasi-Monte Carlo (QMC) is a dynamic research area in the general problem of high-dimensional numerical integration, although its potential for statistical applications is yet to be fully explored. We survey recent research in QMC, particularly lattice rules, and report on its application to highly structured generalised response models. New challenges for QMC are identified and new methodologies are developed. QMC methods are seen to provide significant improvements compared with ordinary Monte Carlo methods.      

A variational characterisation of spherical designs

In this paper we first establish a new variational characterisation of spherical designs: it is shown that a set , where , is a spherical L-design if and only if a certain non-negative quantity A_L,N(X_N) vanishes. By combining this result with a known “sampling theorem” for the sphere, we obtain the main result, which is that if is a stationary point set of A_L,N whose “mesh norm” satisfies h_XN<1/(L+1), then X_N is a spherical L-design. The latter result seems to open a pathway to the elusive problem of proving (for fixed d) the existence of a spherical L-design with a number of points N of order (L+1)^d. A numerical example with d=2 and L=19 suggests that computational minimisation of A_L,N can be a valuable tool for the discovery of new spherical designs for moderate and large values of L.     

A feasible semismooth asymptotically Newton method for mixed complementarity problems

 Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region. As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods. In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges to the Newton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method, which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior to doing (curved) line searches. As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration. The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical results are reported on all problems from the MCPLIB collection [8]. Received: December 1999 / Accepted: March 2002 Published online: September 5, 2002 RID="★" ID="★" This work was supported in part by the Australian Research Council. Key Words. mixed complementarity problems – semismooth equations – projected Newton method – convergence AMS subject classifications. 90C33, 90C30, 65H10     

Operation and physics potential of Tevatron Run 2

We consider a lattice scalar field model with higher derivative terms in the action whose phase diagram contains a tricritical point which is also a triple point between the paramagnetic, ferromagnetic and antiferromagnetic phases. The continuum limit is defined by approching the tricritical point from the paramagnetic side. Contrary to the lattice tricritical g₆ϕ⁶ model we can do a perturbative computation in dimension four. The non-perturbative aspect of the theory relies on the dispersion relation which has the particular feature of having several minima similar to the propagator of lattice fermions. It is shown that this new model is perturbatively renormalizable and provides a non trivial mass spectrum. The positive norm Hilbert space and the unitarity of the time evolution operator in Minkowski space is established by means of the reflection positivity property.