Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming

Summary. This paper studies projected Barzilai-Borwein (PBB) methods for large-scale box-constrained quadratic programming. Recent work on this method has modified the PBB method by incorporating the Grippo-Lampariello-Lucidi (GLL) nonmonotone line search, so as to enable global convergence to be proved. We show by many numerical experiments that the performance of the PBB method deteriorates if the GLL line search is used. We have therefore considered the question of whether the unmodified method is globally convergent, which we show not to be the case, by exhibiting a counter example in which the method cycles. A new projected gradient method (PABB) is then considered that alternately uses the two Barzilai-Borwein steplengths. We also give an example in which this method may cycle, although its practical performance is seen to be superior to the PBB method. With the aim of both ensuring global convergence and preserving the good numerical performance of the unmodified methods, we examine other recent work on nonmonotone line searches, and propose a new adaptive variant with some attractive features. Further numerical experiments show that the PABB method with the adaptive line search is the best BB-like method in the positive definite case, and it compares reasonably well against the GPCG algorithm of Moré and Toraldo. In the indefinite case, the PBB method with the adaptive line search is shown on some examples to find local minima with better solution values, and hence may be preferred for this reason.This work was supported by the EPRSC in UK (no. GR/R87208/01) and the Chinese NSF grant (no. 10171104).Acknowledgement The authors would like to thank the two anonymous referees for their useful suggestions and comments.     

Superrelaxation and the rate of convergence in minimizing quadratic functions subject to bound constraints

The paper resolves the problem concerning the rate of convergence of the working set based MPRGP (modified proportioning with reduced gradient projection) algorithm with a long steplength of the reduced projected gradient step. The main results of this paper are the formula for the R-linear rate of convergence of MPRGP in terms of the spectral condition number of the Hessian matrix and the proof of the finite termination property for the problems whose solution does not satisfy the strict complementarity condition. The bound on the R-linear rate of convergence of the projected gradient is also included. For shorter steplengths these results were proved earlier by Dostál and Schöberl. The efficiency of the longer steplength is illustrated by numerical experiments. The result is an important ingredient in developming scalable algorithms for numerical solution of elliptic variational inequalities and substantiates the choice of parameters that turned out to be effective in numerical experiments.     

An Effective Line Search for the Subgradient Method

One of the main drawbacks of the subgradient method is the tuning process to determine the sequence of steplengths. In this paper, the radar subgradient method, a heuristic method designed to compute a tuning-free subgradient steplength, is geometrically motivated and algebraically deduced. The unit commitment problem, which arises in the electrical engineering field, is used to compare the performance of the subgradient method with the new radar subgradient method.Communicated by M. SimaanThis research was supported by the Spanish Government, CICYT Grant TAP99-1075-C02-01. We acknowledge the technical support from Logilab (HEC, University of Geneva) and especially the valuable remarks and suggestions of the referees.     

Inexact subgradient methods with applications in stochastic programming

In many instances, the exact evaluation of an objective function and its subgradients can be computationally demanding. By way of example, we cite problems that arise within the context of stochastic optimization, where the objective function is typically defined via multi-dimensional integration. In this paper, we address the solution of such optimization problems by exploring the use of successive approximation schemes within subgradient optimization methods. We refer to this new class of methods as inexact subgradient algorithms. With relatively mild conditions imposed on the approximations, we show that the inexact subgradient algorithms inherit properties associated with their traditional (i.e., exact) counterparts. Within the context of stochastic optimization, the conditions that we impose allow a relaxation of requirements traditionally imposed on steplengths in stochastic quasi-gradient methods. Additionally, we study methods in which steplengths may be defined adaptively, in a manner that reflects the improvement in the objective function approximations as the iterations proceed. We illustrate the applicability of our approach by proposing an inexact subgradient optimization method for the solution of stochastic linear programs.This work was supported by Grant Nos. NSF-DDM-89-10046 and NSF-DDM-9114352 from the National Science Foundation.     

Projected gradient methods for linearly constrained problems

The aim of this paper is to study the convergence properties of the gradient projection method and to apply these results to algorithms for linearly constrained problems. The main convergence result is obtained by defining a projected gradient, and proving that the gradient projection method forces the sequence of projected gradients to zero. A consequence of this result is that if the gradient projection method converges to a nondegenerate point of a linearly constrained problem, then the active and binding constraints are identified in a finite number of iterations. As an application of our theory, we develop quadratic programming algorithms that iteratively explore a subspace defined by the active constraints. These algorithms are able to drop and add many constraints from the active set, and can either compute an accurate minimizer by a direct method, or an approximate minimizer by an iterative method of the conjugate gradient type. Thus, these algorithms are attractive for large scale problems. We show that it is possible to develop a finite terminating quadratic programming algorithm without non-degeneracy assumptions. Work supported in part 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. Work supported in part 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.     

Strategies for the Computation of Configurational Forces in Dissipative Media

Configurational forces can be interpreted as driving forces on material inhomogeneities such as crack tips. In dissipative media the total configurational force on an inhomogeneity consists of an elastic contribution and a contribution due to the dissipative processes in the material. For the computation of discrete configurational forces acting at the nodes of a finite element mesh, the elastic and dissipative contributions must be evaluated at integration point level. While the evaluation of the elastic contribution is straightforward, the evaluation of the dissipative part is faced with certain difficulties. This is because gradients of internal variables are necessary in order to compute the dissipative part of the configurational force. For the sake of efficiency, these internal variables are usually treated as local history data at integration point level in finite element (FE) implementations. Thus, the history data needs to be projected to the nodes of the FE mesh in order to compute the gradients by means of shape function interpolations of nodal data as it is standard practice. However, this is a rather cumbersome method which does not easily integrate into standard finite element frameworks. An alternative approach which facilitates the computation of gradients of local history data is investigated in this work. This approach is based on the definition of subelements within the elements of the FE mesh and allows for a straightforward integration of the configurational force computation into standard finite element software. The suitability and the numerical accuracy of different projection approaches and the subelement technique are discussed and analyzed exemplarily within the context of a crystal plasticity model. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Steplength selection in interior-point methods for quadratic programming

We present a new strategy for choosing primal and dual steplengths in a primal–dual interior-point algorithm for convex quadratic programming. Current implementations often scale steps equally to avoid increases in dual infeasibility between iterations. We propose that this method can be too conservative, while safeguarding an unequally-scaled steplength approach will often require fewer steps toward a solution. Computational results are given.     

A family of iterative methods for computing the approximate inverse of a square matrix and inner inverse of a non-square matrix

Based on a quadratical convergence method, a family of iterative methods to compute the approximate inverse of square matrix are presented. The theoretical proofs and numerical experiments show that these iterative methods are very effective. And, more importantly, these methods can be used to compute the inner inverse and their convergence proofs are given by fundamental matrix tools.     

Robust regression for mixed Poisson–Gaussian model

This paper focuses on efficient computational approaches to compute approximate solutions of a linear inverse problem that is contaminated with mixed Poisson–Gaussian noise, and when there are additional outliers in the measured data. The Poisson–Gaussian noise leads to a weighted minimization problem, with solution-dependent weights. To address outliers, the standard least squares fit-to-data metric is replaced by the Talwar robust regression function. Convexity, regularization parameter selection schemes, and incorporation of non-negative constraints are investigated. A projected Newton algorithm is used to solve the resulting constrained optimization problem, and a preconditioner is proposed to accelerate conjugate gradient Hessian solves. Numerical experiments on problems from image deblurring illustrate the effectiveness of the methods.     

Computing convex quadrangulations

We use projected Delaunay tetrahedra and a maximum independent set approach to compute large subsets of convex quadrangulations on a given set of points in the plane. The new method improves over the popular pairing method based on triangulating the point set.     

利用谱投影梯度法计算张量M-特征值（英文）

In this paper, we present the connection between the M-eigenvalues of a fourth-order partially symmetric rectangular tensor and the Z-eigenvalues of a new fourth-order weakly symmetric square tensor by using the symmetric embedding technique. Based on this, the M-eigenvalue problem can be converted to be the Z-eigenvalue problem. Then we compute the M-eigenpairs by the spectral projected gradient(SPG) method that is for computing the Z-eigenpairs. Some numerical results are reported at the end of this paper.     

无约束优化的一类共轭梯度法(英)

本文给出了一类具有4个参数的共轭梯度法，并且分析了其中两个子类的方法．证明了在步长满足更一般的Wolfe条件时，这两个子类的方法是下降算法．同时还证明了这两个子类算法的全局收敛性．     

A Modified Quasi-Newton Method for Structured Optimization with Partial Information on the Hessian

This paper develops a modified quasi-Newton method for structured unconstrained optimization with partial information on the Hessian, based on a better approximation to the Hessian in current search direction. The new approximation is decided by both function values and gradients at the last two iterations unlike the original one which only uses the gradients at the last two iterations. The modified method owns local and superlinear convergence. Numerical experiments show that the proposed method is encouraging comparing with the methods proposed in [4] for structured unconstrained optimization Presented at the 6th International Conference on Optimization: Techniques and Applications, Ballarat, Australia, December 9–11, 2004     

Efficient numerical methods for pricing American options under stochastic volatility

Five numerical methods for pricing American put options under Heston's stochastic volatility model are described and compared. The option prices are obtained as the solution of a two‐dimensional parabolic partial differential inequality. A finite difference discretization on nonuniform grids leading to linear complementarity problems with M‐matrices is proposed. The projected SOR, a projected multigrid method, an operator splitting method, a penalty method, and a componentwise splitting method are considered. The last one is a direct method while all other methods are iterative. The resulting systems of linear equations in the operator splitting method and in the penalty method are solved using a multigrid method. The projected multigrid method and the componentwise splitting method lead to a sequence of linear complementarity problems with one‐dimensional differential operators that are solved using the Brennan and Schwartz algorithm. The numerical experiments compare the accuracy and speed of the considered methods. The accuracies of all methods appear to be similar. Thus, the additional approximations made in the operator splitting method, in the penalty method, and in the componentwise splitting method do not increase the error essentially. The componentwise splitting method is the fastest one. All multigrid‐based methods have similar rapid grid independent convergence rates. They are about two or three times slower that the componentwise splitting method. On the coarsest grid the speed of the projected SOR is comparable with the multigrid methods while on finer grids it is several times slower. ©John Wiley & Sons, Inc. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Steplengths in the extragradient type methods

The extragradient type methods are a class of efficient direct methods. For solving monotone variational inequalities, these methods only require function evaluation, and therefore are widely applied to black-box models. In this type of methods, the distance between the iterate and a fixed solution point decreases by iterations. Furthermore, in each iteration, the negative increment of such squared distance has a differentiable concave lower bound function without requiring any solution in its formula. In this paper, we investigate some properties for the lower bound. Our study reveals that the lower bound affords a steplength domain which guarantees the convergence of the entire algorithm. Based on these results, we present two new steplengths. One involves the projection onto the tangent cone without line search, while the other can be computed via searching the positive root of a one dimension concave lower bound function. Our preliminary numerical results confirm and illustrate the attractiveness of our contributions.     

A new local reduced basis discontinuous Galerkin approach for heterogeneous multiscale problems

Inspired by the reduced basis approach and modern numerical multiscale methods, we present a new framework for an efficient treatment of heterogeneous multiscale problems. The new approach is based on the idea of considering heterogeneous multiscale problems as parametrized partial differential equations where the parameters are smooth functions. We then construct, in an offline phase, a suitable localized reduced basis that is used in an online phase to efficiently compute approximations of the multiscale problem by means of a discontinuous Galerkin method on a coarse grid. We present our approach for elliptic multiscale problems and discuss an a posteriori error estimate that can be used in the construction process of the localized reduced basis. Numerical experiments are given to demonstrate the efficiency of the new approach.     

A class of superlinearly convergent projection algorithms with relaxed stepsizes

A quasi-Newton extension of the Goldstein-Levitin-Polyak (GLP) projected gradient algorithm for constrained optimization is considered. Essentially, this extension projects an unconstrained descent step on to the feasible region. The determination of the stepsize is divided into two stages. The first is a stepsize sequence, chosen from the range [1,2], converging to unity. This determines the size of the unconstrained step. The second is a stepsize chosen from the range [0,1] according to a stepsize strategy and determines the length of the projected step. Two such strategies are considered. The first bounds the objective function decrease by a conventional linear functional, whereas the second uses a quadratic functional as a bound.The introduction of the unconstrained step provides the option of taking steps that are larger than unity. It is shown that unit steplengths and subsequently superlinear convergence rates are attained if the projection of the quasi-Newton Hessian approximation approaches the projection of the Hessian at the solution. Thus, the requirement in the GLP algorithm for a positive definite Hessian at the solution is relaxed. This allows the use of strictly positive definite Hessian approximations, thereby simplifying the quadratic subproblem involved, even if the Hessian at the solution is not strictly positive definite.This research was funded by a Science and Engineering Research Council Advanced Fellowship. The author is also grateful to an anonymous referee for numerous constructive criticisms and comments.     

求解界约束优化的一种新的非单调谱投影梯度法

本文给出求解界约束优化问题的一种新的非单调谱投影梯度算法. 该算法是将谱投影梯度算法与Zhang and Hager [SIAM Journal on Optimization,2004,4（4）：1043-1056]提出的非单调线搜索结合得到的方法. 在合理的假设条件下,证明了算法的全局收敛性.数值实验结果表明,与已有的界约束优化问题的谱投影梯度法比较,利用本文给出的算法求解界约束优化问题是有竞争力的.