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 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 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.     

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.     

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.     

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 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 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 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 Wilkinson-like multishift QR algorithm for symmetric eigenvalue problems and its global convergence

In 1989, Bai and Demmel proposed the multishift QR algorithm for eigenvalue problems. Although the global convergence property of the algorithm (i.e., the convergence from any initial matrix) still remains an open question for general nonsymmetric matrices, in 1992 Jiang focused on symmetric tridiagonal case and gave a global convergence proof for the generalized Rayleigh quotient shifts. In this paper, we propose Wilkinson-like shifts, which reduce to the standard Wilkinson shift in the single shift case, and show a global convergence theorem.     

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.     

A Ulm-like method for inverse eigenvalue problems

We propose a Ulm-like method for solving inverse eigenvalue problems, which avoids solving approximate Jacobian equations comparing with other known methods. A convergence analysis of this method is provided and the R-quadratic convergence property is proved under the assumption of the distinction of given eigenvalues. Numerical experiments as well as the comparison with the inexact Newton-like method are given in the last section.     

A method for solving stochastic eigenvalue problems

We present a novel approach for calculating stochastic eigenvalues of differential and integral equations as well as for random matrices. Five examples based on very different types of problem have been analysed and detailed numerical results obtained. It would seem that the method has considerable promise. The essence of the method is to replace the stochastic eigenvalue problem λ(ξ)?(ξ)=A(ξ)?(ξ), where ξ is a set of random variables, by the introduction of an auxiliary equation in which . This changes the problem from an eigenvalue one to an initial value problem in the new pseudo-time variable t. The new linear time-dependent equation may then be solved by a polynomial chaos expansion (PCE) and the stochastic eigenvalue and its moments recovered by a limiting process. This technique has the advantage of avoiding the non-linear terms in the conventional method of stochastic eigenvalue calculation by PCE, but it does introduce an additional, ‘pseudo-time’, independent variable t. The paper illustrates the viability of this approach by application to several examples based on realistic problems.     

A two-grid discretization scheme for eigenvalue problems

A two-grid discretization scheme is proposed for solving eigenvalue problems, including both partial differential equations and integral equations. With this new scheme, the solution of an eigenvalue problem on a fine grid is reduced to the solution of an eigenvalue problem on a much coarser grid, and the solution of a linear algebraic system on the fine grid and the resulting solution still maintains an asymptotically optimal accuracy.