Some iterative methods for the solution of a symmetric indefinite KKT system

This paper is concerned with the numerical solution of a Karush–Kuhn–Tucker system. Such symmetric indefinite system arises when we solve a nonlinear programming problem by an Interior-Point (IP) approach. In this framework, we discuss the effectiveness of two inner iterative solvers: the method of multipliers and the preconditioned conjugate gradient method. We discuss the implementation details of these algorithms in an IP scheme and we report the results of a numerical comparison on a set of large scale test-problems arising from the discretization of elliptic control problems. This research was supported by the Italian Ministry for Education, University and Research (MIUR), FIRB Project RBAU01JYPN.     

Approximation Schemes for Functional Optimization Problems

Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow “fast” with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the “curse of dimensionality,” which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables. Marcello Sanguineti was partially supported by a PRIN grant from the Italian Ministry for University and Research (project “Models and Algorithms for Robust Network Optimization”).     

An Adaptive Finite Element Method for the H- ψ Formulation of Time-dependent Eddy Current Problems

In this paper, we develop an adaptive finite element method based on reliable and efficient a posteriori error estimates for the H − ψ formulation of eddy current problems with multiply connected conductors. Multiply connected domains are considered by making “cuts”. The competitive performance of the method is demonstrated by an engineering benchmark problem, Team Workshop Problem 7, and a singular problem with analytic solution.W. Zheng was supported in part by China NSF under the grant 10401040.Z. Chen was supported in part by China NSF under the grant 10025102 and 10428105, and by the National Basic Research Project under the grant 2005CB321701.     

A filter inexact-restoration method for nonlinear programming

A new iterative algorithm based on the inexact-restoration (IR) approach combined with the filter strategy to solve nonlinear constrained optimization problems is presented. The high level algorithm is suggested by Gonzaga et al. (SIAM J. Optim. 14:646–669, 2003) but not yet implement—the internal algorithms are not proposed. The filter, a new concept introduced by Fletcher and Leyffer (Math. Program. Ser. A 91:239–269, 2002), replaces the merit function avoiding the penalty parameter estimation and the difficulties related to the nondifferentiability. In the IR approach two independent phases are performed in each iteration, the feasibility and the optimality phases. The line search filter is combined with the first one phase to generate a “more feasible” point, and then it is used in the optimality phase to reach an “optimal” point. Numerical experiences with a collection of AMPL problems and a performance comparison with IPOPT are provided.      

Error analysis of finite element approximations of the inverse mean curvature flow arising from the general relativity

This paper proposes and analyzes a finite element method for a nonlinear singular elliptic equation arising from the black hole theory in the general relativity. The nonlinear equation, which was derived and analyzed by Huisken and Ilmanen in (J Diff Geom 59:353–437), represents a level set formulation for the inverse mean curvature flow describing the evolution of a hypersurface whose normal velocity equals the reciprocal of its mean curvature. We first propose a finite element method for a regularized flow which involves a small parameter ɛ; a rigorous analysis is presented to study well-posedness and convergence of the scheme under certain mesh-constraints, and optimal rates of convergence are verified. We then prove uniform convergence of the finite element solution to the unique weak solution of the nonlinear singular elliptic equation as the mesh size h and the regularization parameter ɛ both tend to zero. Computational results are provided to show the efficiency of the proposed finite element method and to numerically validate the “jumping out” phenomenon of the weak solution of the inverse mean curvature flow. Numerical studies are presented to evidence the existence of a polynomial scaling law between the mesh size h and the regularization parameter ɛ for optimal convergence of the proposed scheme. Finally, a numerical convergence study for another approach recently proposed by R. Moser (The inverse mean curvature flow and p-harmonic functions. preprint U Bath, 2005) for approximating the inverse mean curvature flow via p-harmonic functions is also included.     

Interior-Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints

In this paper, we present an interior-point algorithm for large and sparse convex quadratic programming problems with bound constraints. The algorithm is based on the potential reduction method and the use of iterative techniques to solve the linear system arising at each iteration. The global convergence properties of the potential reduction method are reassessed in order to take into account the inexact solution of the inner system. We describe the iterative solver, based on the conjugate gradient method with a limited-memory incomplete Cholesky factorization as preconditioner. Furthermore, we discuss some adaptive strategies for the fill-in and accuracy requirements that we use in solving the linear systems in order to avoid unnecessary inner iterations when the iterates are far from the solution. Finally, we present the results of numerical experiments carried out to verify the effectiveness of the proposed strategies. We consider randomly generated sparse problems without a special structure. Also, we compare the proposed algorithm with the MOSEK solver. Research partially supported by the MIUR FIRB Project RBNE01WBBB “Large-Scale Nonlinear Optimization.”     

Fast Fourier Transform Solvers and Preconditioners for Quadratic Spline Collocation

Quadratic Spline Collocation (QSC) methods of optimal order of convergence have been recently developed for the solution of elliptic Partial Differential Equations (PDEs). In this paper, linear solvers based on Fast Fourier Transforms (FFT)are developed for the solution of the QSC equations. The complexity of the FFT solvers is O(N ² log N), where N is the gridsize in one dimension. These direct solvers can handle PDEs with coefficients in one variable or constant, and Dirichlet, Neumann, alternating Dirichlet-Neumann or periodic boundary conditions, along at least one direction of a rectangular domain. General variable coefficient PDEs are handled by preconditioned iterative solvers. The preconditioner is the QSC matrix arising from a constant coefficient PDE. The convergence analysis of the preconditioner is presented. It is shown that, under certain conditions, the convergence rate is independent of the gridsize. The preconditioner is solved by FFT techniques, and integrated with one-step or acceleration methods, giving rise to asymptotically almost optimal linear solvers, with complexity O(N ² log N). Numerical experiments verify the effectiveness of the solvers and preconditioners, even on problems more general than the analysis assumes. The development and analysis of FFT solvers and preconditioners is extended to QSC equations corresponding to systems of elliptic PDEs.     

Detecting “dense” columns in interior point methods for linear programs

During the iterations of interior point methods symmetric indefinite systems are decomposed by LD̂L ^T factorization. This step can be performed in a special way where the symmetric indefinite system is transformed to a positive definite one, called the normal equations system. This approach proved to be efficient in most of the cases and numerically reliable, due to the positive definite property. It has been recognized, however, that in case the linear program contains “dense” columns, this approach results in an undesirable fill–in during the computations and the direct factorization of the symmetric indefinite system is more advantageous. The paper describes a new approach to detect cases where the system of normal equations is not preferable for interior point methods and presents a new algorithm for detecting the set of columns which is responsible for the excessive fill–in in the matrix AA ^T . By solving large–scale linear programming problems we demonstrate that our heuristic is reliable in practice. This work was supported in part by the Hungarian Scientific Research Fund OTKA K60480.     

CHEBYSHEV SPECTRAL-FINITE ELEMENT METHOD FOR INCOMPRESSIBLE FLUID FLOW

In this paper, we propose a mixed method for solving two-dimensional unsteady vorticity equations by using Chebyshev spectral-fiuite element approximation. The generalized stability and the optimal rate of convergence are proved. The numerical results show the advantages of such method. The technique in this paper is also useful for other nonlinear problems.     

Observations on the numerical stability of the Galerkin method

A simple factorization of the finite-dimensional Galerkin operators motivates a study of the numerical stability of a Galerkin procedure on the basis of its “potential stability” and the “conditioning” of its coordinate functions. Conditions sufficient for stability and conditions leading to instability are thereby identified. Numerical examples of stability and instability occurring in the application of the Galerkin method to boundary-integral equations arising in simple scattering problems are provided and discussed within this framework. Numerical instabilities reported by other authors are examined and explained from the same point of view. This revised version was published online in June 2006 with corrections to the Cover Date.     

A fixed-center spherical separation algorithm with kernel transformations for classification problems

We consider a special case of the optimal separation, via a sphere, of two discrete point sets in a finite dimensional Euclidean space. In fact we assume that the center of the sphere is fixed. In this case the problem reduces to the minimization of a convex and nonsmooth function of just one variable, which can be solved by means of an “ad hoc” method in O(p log p) time, where p is the dataset size. The approach is suitable for use in connection with kernel transformations of the type adopted in the support vector machine (SVM) approach. Despite of its simplicity the method has provided interesting results on several standard test problems drawn from the binary classification literature. This research has been partially supported by the Italian “Ministero dell’Istruzione, dell’Università e della Ricerca Scientifica”, under PRIN project Numerical Methods for Global Optimization and for some classes of Nonsmooth Optimization Problems (2005017083.002).     

Weighted norm inequalities,off-diagonal estimates and elliptic operators Part II: Off-diagonal estimates on spaces of homogeneous type

This is the second part of a series of four articles on weighted norm inequalities, off-diagonal estimates and elliptic operators. We consider a substitute to the notion of pointwise bounds for kernels of operators which usually is a measure of decay. This substitute is that of off-diagonal estimates expressed in terms of local and scale invariant L^p − L^q estimates. We propose a definition in spaces of homogeneous type that is stable under composition. It is particularly well suited to semigroups. We study the case of semigroups generated by elliptic operators. This work was partially supported by the European Union (IHP Network “Harmonic Analysis and Related Problems” 2002-2006, Contract HPRN-CT-2001-00273-HARP). The second author was also supported by MEC “Programa Ramón y Cajal, 2005” and by MEC Grant MTM2004-00678.     

The <Emphasis Type="Italic">Q</Emphasis> Method for Symmetric Cone Programming

The Q method of semidefinite programming, developed by Alizadeh, Haeberly and Overton, is extended to optimization problems over symmetric cones. At each iteration of the Q method, eigenvalues and Jordan frames of decision variables are updated using Newton’s method. We give an interior point and a pure Newton’s method based on the Q method. In another paper, the authors have shown that the Q method for second-order cone programming is accurate. The Q method has also been used to develop a “warm-starting” approach for second-order cone programming. The machinery of Euclidean Jordan algebra, certain subgroups of the automorphism group of symmetric cones, and the exponential map is used in the development of the Newton method. Finally we prove that in the presence of certain non-degeneracies the Jacobian of the Newton system is nonsingular at the optimum. Hence the Q method for symmetric cone programming is accurate and can be used to “warm-start” a slightly perturbed symmetric cone program.     

The optimal convergence of the h–p version of the boundary element method with quasiuniform meshes for elliptic problems on polygonal domains

In the framework of the Jacobi-weighted Besov spaces, we analyze the lower and upper bounds of errors in the h–p version of boundary element solutions on quasiuniform meshes for elliptic problems on polygons. Both lower bound and upper bound are optimal in h and p, and they are of the same order. The optimal convergence of the h–p version of boundary element method with quasiuniform meshes is proved, which includes the optimal rates for h version with quasiuniform meshes and the p version with quasiuniform degrees as two special cases. Dedicated to Professor Charles Micchelli on the occasion of his sixtieth birthday Mathematics subject classification (2000) 65N38. Benqi Guo: The work of this author was supported by NSERC of Canada under Grant OGP0046726 and was complete during visiting Newton Institute for Mathematical Sciences, Cambridge University for participating in special program “Computational Challenges in PDEs” in 2003. Norbert Heuer: This author is supported by Fondecyt project No. 1010220 and by the FONDAP Program (Chile) on Numerical Analysis. Current address: Mathematical Sciences, Brunel University, Uxbridge, U.K.     

<Emphasis Type="Italic">R</Emphasis> -function method as a supportive extension for the ritz method and least squares method

We carried out a comparative analysis of the solutions for two model problems, obtained by the Ritz method and least squares method, using the R -function method. Numerical experiments were performed in the system “POLE”.     

Structural stability and robustness to bounded rationality for non-compact cases

We study the model M consisting of “general games” with noncompact action space, together with an associated abstract rationality function. We prove that M is structurally stable and robust to ϵ-equilibria for “almost all” parameters. As applications, we investigate structural stability and robustness to bounded rationality for noncooperative games, multiobjective optimizations and fixed point problems satisfying existence and some continuity conditions. Specifically, we introduce concrete rationality functions for such three kinds of problems with both payoffs and strategy sets, objective functions and domain spaces, and correspondence and domain spaces as parameters, respectively, and show the generic structural stability and robustness to bounded rationality for the corresponding model Ms.     

Wheel inequalities for stable set polytopes

We introduce new classes of valid inequalities, called wheel inequalities, for the stable set polytopeP _G of a graphG. Each “wheel configuration” gives rise to two such inequalities. The simplest wheel configuration is an “odd” subdivisionW of a wheel, and for these we give necessary and sufficient conditions for the wheel inequality to be facet-inducing forP _W . Generalizations arise by allowing subdivision paths to intersect, and by replacing the “hub” of the wheel by a clique. The separation problem for these inequalities can be solved in polynomial time. Research partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada. Research partially supported by scholarships from the Ontario Ministry of Colleges and Universities.     

On singular perturbation in non well posed problems

Summary Let L_εu and L ₀ v be the elliptic and “backward” heat operators defined by(1.1) and(1.2), respectively. The following question is considered for a pair of “non-well posed” initial-boundary value problems for L_ε and L ₀ : if u and v are the respective solutions, under what restrictions on the classes of admissible solutions and in what sense, if any, does u converge to v as ɛ →0? This research was supported in part by the National Science Foundation Grant No. GP 5882 with Cornell University.     

Quadrature formulae with multiple nodes and a maximal trigonometric degree of exactness

In this paper we consider interpolatory quadrature formulae with multiple nodes, which have the maximal trigonometric degree of exactness. Our approach is based on a procedure given by Ghizzeti and Ossicini (Quadrature formulae, Academie-Verlag, Berlin, 1970). We introduce and consider the so-called σ-orthogonal trigonometric polynomials of semi-integer degree and give a numerical method for their construction. Also, some numerical examples are included. The authors were supported in part by the Serbian Ministry of Science and Technological Development (Project: Orthogonal Systems and Applications, grant number #144004) and the Swiss National Science Foundation (SCOPES Joint Research Project No. IB7320-111079 “New Methods for Quadrature”).