Non-Interior continuation methods for solving semidefinite complementarity problems

 There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported. Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002 RID="⋆" ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273. Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear convergence     

A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002 RID="†" ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.     

Error bounds for proximal point subproblems and associated inexact proximal point algorithms

We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem, and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method, while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance rules is also discussed. Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05     

Variational conditions with smooth constraints: structure and analysis

 This is an expository paper about the analysis of variational conditions over sets defined in finite-dimensional spaces by fairly smooth functions satisfying a constraint qualification. The primary focus is on results that can provide quantitative and computable sensitivity information for particular instances of the problems under study, and our objective is to give a personal view of the state of current knowledge in this area and of gaps in that knowledge that require future work. The writing style is informal, in keeping with the objective of focusing the reader's attention on the basic concepts and the relationships between them, rather than on details of the particular results themselves. Received: December 1, 2002 / Accepted: April 25, 2003 Published online: May 28, 2003 Key words. variational condition – variational inequality – complementarity – sensitivity – stability – nondegeneracy Mathematics Subject Classification (2000): Primary: 90C31. Secondary: 47J20, 49J40, 49J53, 90C33     

Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints

 Multidimensional optimization problems where the objective function and the constraints are multiextremal non-differentiable Lipschitz functions (with unknown Lipschitz constants) and the feasible region is a finite collection of robust nonconvex subregions are considered. Both the objective function and the constraints may be partially defined. To solve such problems an algorithm is proposed, that uses Peano space-filling curves and the index scheme to reduce the original problem to a H?lder one-dimensional one. Local tuning on the behaviour of the objective function and constraints is used during the work of the global optimization procedure in order to accelerate the search. The method neither uses penalty coefficients nor additional variables. Convergence conditions are established. Numerical experiments confirm the good performance of the technique. Received: April 2002 / Accepted: December 2002 Published online: March 21, 2003 RID="⋆" ID="⋆" This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 01–01–00587. Key Words. global optimization – multiextremal constraints – local tuning – index approach     

A uniqueness result for a Neumann problem involving the critical Sobolev exponent

 In this paper we consider the problem

Propagation of polarization in elastodynamics with residual stress and travel times

 We show that knowing the displacement-to-traction map associated to the equations of isotropic elastodynamics with residual stress we can determine the lens maps of compressional and shear waves. We derive several consequences of this for the inverse problem of determining the residual stress and the Lamé parameters from the displacement-to-traction map. Received: 6 December 2001 / Revised version: 29 October 2002 / Published online: 8 April 2003 RID="⋆" ID="⋆" The author thanks the Department of Mathematics at the University of Washington for its hospitality during his visit in fall 2000. RID="⋆⋆" ID="⋆⋆" Partly supported by NSF grant DMS-0070488 and a John Simon Guggenheim fellowship. The author also thanks MSRI for partial support and for providing a very stimulating environment during the inverse problems program in fall 2001.     

Hydrodynamic limit for ∇φ interface model on a wall

 We consider random evolution of an interface on a hard wall under periodic boundary conditions. The dynamics are governed by a system of stochastic differential equations of Skorohod type, which is Langevin equation associated with massless Hamiltonian added a strong repelling force for the interface to stay over the wall. We study its macroscopic behavior under a suitable large scale space-time limit and derive a nonlinear partial differential equation, which describes the mean curvature motion except for some anisotropy effects, with reflection at the wall. Such equation is characterized by an evolutionary variational inequality. Received: 10 January 2002 / Revised version: 18 August 2002 / Published online: 15 April 2003 Mathematics Subject Classification (2000): 60K35, 82C24, 35K55, 35K85 Key words or phrases: Hydrodynamic limit – Effective interfaces – Hard wall – Skorohod's stochastic differential equation – Evolutionary variational inequality     

Solving monotone inclusions with linear multi-step methods

 In this paper a new class of proximal-like algorithms for solving monotone inclusions of the form T(x)∋0 is derived. It is obtained by applying linear multi-step methods (LMM) of numerical integration in order to solve the differential inclusion , which can be viewed as a generalization of the steepest decent method for a convex function. It is proved that under suitable conditions on the parameters of the LMM, the generated sequence converges weakly to a point in the solution set T ⁻¹ (0). The LMM is very similar to the classical proximal point algorithm in that both are based on approximately evaluating the resolvants of T. Consequently, LMM can be used to derive multi-step versions of many of the optimization methods based on the classical proximal point algorithm. The convergence analysis allows errors in the computation of the iterates, and two different error criteria are analyzed, namely, the classical scheme with summable errors, and a recently proposed more constructive criterion. Received: April 2001 / Accepted: November 2002 Published online: February 14, 2003 Key Words. proximal point algorithm – monotone operator – numerical integration – strong stability – relative error criterion Mathematics Subject Classification (1991): 20E28, 20G40, 20C20