Solving inverse cone-constrained eigenvalue problems

We compare various algorithms for constructing a matrix of order $n$ whose Pareto spectrum contains a prescribed set $\Lambda =\{\lambda _1,\ldots , \lambda _p\}$ of reals. In order to avoid overdetermination one assumes that $p$ does not exceed $n^2.$ The inverse Pareto eigenvalue problem under consideration is formulated as an underdetermined system of nonlinear equations. We also address the issue of computing Lorentz spectra and solving inverse Lorentz eigenvalue problems.     

An algorithm for composite nonsmooth optimization problems

Nonsmooth optimization problems are divided into two categories. The first is composite nonsmooth problems where the generalized gradient can be approximated by information available at the current point. The second is basic nonsmooth problems where the generalized gradient must be approximated using information calculated at previous iterates.Methods for minimizing composite nonsmooth problems where the nonsmooth function is made up from a finite number of smooth functions, and in particular max functions, are considered. A descent method which uses an active set strategy, a nonsmooth line search, and a quasi-Newton approximation to the reduced Hessian of a Lagrangian function is presented. The Theoretical properties of the method are discussed and favorable numerical experience on a wide range of test problems is reported.This work was carried out at the University of Dundee from 1976–1979 and at the University of Kentucky at Lexington from 1979–1980. The provision of facilities in both universities is gratefully acknowledged, as well as the support of NSF Grant No. ECS-79-23272 for the latter period. The first author also wishes to acknowledge financial support from a George Murray Scholarship from the University of Adelaide and a University of Dundee Research Scholarship for the former period.     

Homotopy algorithm for symmetric eigenvalue problems

Summary The homotopy method can be used to solve eigenvalue-eigenvector problems. The purpose of this paper is to report the numerical experience of the homotopy method of computing eigenpairs for real symmetric tridiagonal matrices together with a couple of new theoretical results. In practice, it is rerely of any interest to compute all the eigenvalues. The homotopy method, having the order preserving property, can provide any specific eigenvalue without calculating any other eigenvalues. Besides this advantage, we note that the homotopy algorithm is to a large degree a parallel algorithm. Numerical experimentation shows that the homotopy method can be very efficient especially for graded matrices.Research was supported in part by NSF under Grant DMS-8701349     

A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems

The minimum sum-of-squares clustering problem is formulated as a problem of nonsmooth, nonconvex optimization, and an algorithm for solving the former problem based on nonsmooth optimization techniques is developed. The issue of applying this algorithm to large data sets is discussed. Results of numerical experiments have been presented which demonstrate the effectiveness of the proposed algorithm.     

A syncro-parallel nonsmooth PGD algorithm for nonsmooth optimization

A nonsmooth PGD scheme for minimizing a nonsmooth convex function is presented. In the parallelization step of the algorithm, a method due to Pang, Han and Pangaraj (1991), [7], is employed to solve a subproblem for constructing search directions. The convergence analysis is given as well.     

Multiple solutions of constant sign for nonlinear nonsmooth eigenvalue problems near resonance

In this paper we study a class of nonlinear elliptic eigenvalue problems driven by the p-Laplacian and having a nonsmooth locally Lipschitz potential. We show that as the parameter approaches (= the principal eigenvalue of ) from the right, the problem has three nontrivial solutions of constant sign. Our approach is variational based on the nonsmooth critical point theory for locally Lipschitz functions. In the process of the proof we also establish a generalization of a recent result of Brezis and Nirenberg for C₀¹ versus W₀^1,p minimizers of a locally Lipschitz functional. In addition we prove a result of independent interest on the existence of an additional critical point in the presence of a local minimizer of constant sign. Finally by restricting further the asymptotic behavior of the potential at infinity, we show that for all the problem has two solutions one strictly positive and the other strictly negative.Received: 7 January 2003, Accepted: 12 May 2003, Published online: 4 September 2003Mathematics Subject Classification (2000): 35J20, 35J85, 35R70     

A smoothing trust region filter algorithm for nonsmooth least squares problems

We propose a smoothing trust region filter algorithm for nonsmooth nonconvex least squares problems. We present convergence theorems of the proposed algorithm to a Clarke stationary point or a global minimizer of the objective function under certain conditions. Preliminary numerical experiments show the efficiency of the proposed algorithm for finding zeros of a system of polynomial equations with high degrees on the sphere and solving differential variational inequalities.     

The FEAST algorithm for large eigenvalue problems

We consider the eigensolver named FEAST that was introduced by Polizzi in 2009 [1]. This solver, tailored to the (partial) solution of large sparse (generalized) eigenproblems offers good potential for parallelism and showed good robustness in our experiments. We briefly introduce the algorithm, point out some problems and give two examples. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A FEAST algorithm with oblique projection for generalized eigenvalue problems

The contour integral‐based eigensolvers are the recent efforts for computing the eigenvalues inside a given region in the complex plane. The best‐known members are the Sakurai–Sugiura method, its stable version CIRR, and the FEAST algorithm. An attractive computational advantage of these methods is that they are easily parallelizable. The FEAST algorithm was developed for the generalized Hermitian eigenvalue problems. It is stable and accurate. However, it may fail when applied to non‐Hermitian problems. Recently, a dual subspace FEAST algorithm was proposed to extend the FEAST algorithm to non‐Hermitian problems. In this paper, we instead use the oblique projection technique to extend FEAST to the non‐Hermitian problems. Our approach can be summarized as follows: (a) construct a particular contour integral to form a search subspace containing the desired eigenspace and (b) use the oblique projection technique to extract desired eigenpairs with appropriately chosen test subspace. The related mathematical framework is established. Comparing to the dual subspace FEAST algorithm, we can save the computational cost roughly by a half if only the eigenvalues or the eigenvalues together with their right eigenvectors are needed. We also address some implementation issues such as how to choose a suitable starting matrix and design‐efficient stopping criteria. Numerical experiments are provided to illustrate that our method is stable and efficient.     

The CoMirror algorithm for solving nonsmooth constrained convex problems

We introduce a first-order Mirror-Descent (MD) type algorithm for solving nondifferentiable convex problems having a combination of simple constraint set X (ball, simplex, etc.) and an additional functional constraint. The method is tuned to exploit the structure of X by employing an appropriate non-Euclidean distance-like function. Convergence results and efficiency estimates are derived. The performance of the algorithm is demonstrated by solving certain image deblurring problems.     

Exponentially convergent parallel algorithm for nonlinear eigenvalue problems

A. V. Klimenko, V. L. Makarov ^{A new algorithm for nonlinear eigenvalue problems is proposed.The numerical technique is based on a perturbation of the coefficientsof differential equation combined with the Adomian decompositionmethod for the nonlinear part. The approach provides an exponentialconvergence rate with a base which is inversely proportionalto the index of the eigenvalue under consideration. The eigenpairscan be computed in parallel. Numerical examples are presentedto support the theory. They are in good agreement with the spectralasymptotics obtained by other authors.}     

Merit functions for nonsmooth complementarity problems and related descent algorithm

Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.     

A rank‐exploiting infinite Arnoldi algorithm for nonlinear eigenvalue problems

We consider the nonlinear eigenvalue problem M(λ)x = 0, where M(λ) is a large parameter‐dependent matrix. In several applications, M(λ) has a structure where the higher‐order terms of its Taylor expansion have a particular low‐rank structure. We propose a new Arnoldi‐based algorithm that can exploit this structure. More precisely, the proposed algorithm is equivalent to Arnoldi's method applied to an operator whose reciprocal eigenvalues are solutions to the nonlinear eigenvalue problem. The iterates in the algorithm are functions represented in a particular structured vector‐valued polynomial basis similar to the construction in the infinite Arnoldi method [Jarlebring, Michiels, and Meerbergen, Numer. Math., 122 (2012), pp. 169–195]. In this paper, the low‐rank structure is exploited by applying an additional operator and by using a more compact representation of the functions. This reduces the computational cost associated with orthogonalization, as well as the required memory resources. The structure exploitation also provides a natural way in carrying out implicit restarting and locking without the need to impose structure in every restart. The efficiency and properties of the algorithm are illustrated with two large‐scale problems. Copyright © 2016 John Wiley & Sons, Ltd.     

On an enumerative algorithm for solving eigenvalue complementarity problems

In this paper, we discuss the solution of linear and quadratic eigenvalue complementarity problems (EiCPs) using an enumerative algorithm of the type introduced by Júdice et al. (Optim. Methods Softw. 24:549–586, 2009). Procedures for computing the interval that contains all the eigenvalues of the linear EiCP are first presented. A nonlinear programming (NLP) model for the quadratic EiCP is formulated next, and a necessary and sufficient condition for a stationary point of the NLP to be a solution of the quadratic EiCP is established. An extension of the enumerative algorithm for the quadratic EiCP is also developed, which solves this problem by computing a global minimum for the NLP formulation. Some computational experience is presented to highlight the efficiency and efficacy of the proposed enumerative algorithm for solving linear and quadratic EiCPs.     

Residual algorithm for large-scale positive definite generalized eigenvalue problems

In the positive definite case, the extreme generalized eigenvalues can be obtained by solving a suitable nonlinear system of equations. In this work, we adapt and study the use of recently developed low-cost derivative-free residual schemes for nonlinear systems, to solve large-scale generalized eigenvalue problems. We demonstrate the effectiveness of our approach on some standard test problems, and also on a problem associated with the vibration analysis of large structures. In our numerical results we use preconditioning strategies based on incomplete factorizations, and we compare with and without preconditioning with a well-known available package.     

A structure-preserving doubling algorithm for quadratic eigenvalue problems arising from time-delay systems

We propose a structure-preserving doubling algorithm for a quadratic eigenvalue problem arising from the stability analysis of time-delay systems. We are particularly interested in the eigenvalues on the unit circle, which are difficult to estimate. The convergence and backward error of the algorithm are analyzed and three numerical examples are presented. Our experience shows that our algorithm is efficient in comparison to the few existing approaches for small to medium size problems.     

A linear eigenvalue algorithm for the nonlinear eigenvalue problem

The Arnoldi method for standard eigenvalue problems possesses several attractive properties making it robust, reliable and efficient for many problems. The first result of this paper is a characterization of the solutions to an arbitrary (analytic) nonlinear eigenvalue problem (NEP) as the reciprocal eigenvalues of an infinite dimensional operator denoted ${\mathcal {B}}$ . We consider the Arnoldi method for the operator ${\mathcal {B}}$ and show that with a particular choice of starting function and a particular choice of scalar product, the structure of the operator can be exploited in a very effective way. The structure of the operator is such that when the Arnoldi method is started with a constant function, the iterates will be polynomials. For a large class of NEPs, we show that we can carry out the infinite dimensional Arnoldi algorithm for the operator ${\mathcal {B}}$ in arithmetic based on standard linear algebra operations on vectors and matrices of finite size. This is achieved by representing the polynomials by vector coefficients. The resulting algorithm is by construction such that it is completely equivalent to the standard Arnoldi method and also inherits many of its attractive properties, which are illustrated with examples.     

A descent algorithm for nonsmooth convex optimization

This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The algorithm can be implemented and may be considered a modification of the ε-subgradient algorithm and Lemarechal's descent algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below. Limited computational experience with the algorithm is also reported.     

A trust region algorithm for nonsmooth optimization

A trust region algorithm is proposed for minimizing the nonsmooth composite functionF(x) = h(f(x)), wheref is smooth andh is convex. The algorithm employs a smoothing function, which is closely related to Fletcher's exact differentiable penalty functions. Global and local convergence results are given, considering convergence to a strongly unique minimizer and to a minimizer satisfying second order sufficiency conditions.     

A collocation method for eigenvalue problems

Approximations to the eigenvalues ofmth-order linear eigenvalue problems are determined by using a collocation method with piecewise-polynomial functions of degreem+d possessingm continuous derivatives as basis functions. It is shown that for a general class of problems the error in these approximations is at leastO([h(II)] ^d+1) whereh(II) is the maximal subinterval length. The question of stability of the discretized problems is also considered. It is not assumed that the eigenvalue problems are in any sense self-adjoint.