Monotone projected gradient methods for large-scale box-constrained quadratic programming

Inspired by the success of the projected Barzilai-Borwein (PBB) method for large-scale box-constrained quadratic programming, we propose and analyze the monotone projected gradient methods in this paper. We show by experiments and analyses that for the new methods, it is generally a bad option to compute steplengths based on the negative gradients. Thus in our algorithms, some continuous or discontinuous projected gradients are used instead to compute the steplengths. Numerical experiments on a wide variety of test problems are presented, indicating that the new methods usually outperform the PBB method.     

Inexact projected gradient method for vector optimization

In this work, we propose an inexact projected gradient-like method for solving smooth constrained vector optimization problems. In the unconstrained case, we retrieve the steepest descent method introduced by Graña Drummond and Svaiter. In the constrained setting, the method we present extends the exact one proposed by Graña Drummond and Iusem, since it admits relative errors on the search directions. At each iteration, a decrease of the objective value is obtained by means of an Armijo-like rule. The convergence results of this new method extend those obtained by Fukuda and Graña Drummond for the exact version. For partial orders induced by both pointed and nonpointed cones, under some reasonable hypotheses, global convergence to weakly efficient points of all sequences generated by the inexact projected gradient method is established for convex (respect to the ordering cone) objective functions. In the convergence analysis we also establish a connection between the so-called weighting method and the one we propose.     

A cyclic projected gradient method

In recent years, convex optimization methods were successfully applied for various image processing tasks and a large number of first-order methods were designed to minimize the corresponding functionals. Interestingly, it was shown recently in Grewenig et al. (2010) that the simple idea of so-called “superstep cycles” leads to very efficient schemes for time-dependent (parabolic) image enhancement problems as well as for steady state (elliptic) image compression tasks. The “superstep cycles” approach is similar to the nonstationary (cyclic) Richardson method which has been around for over sixty years. In this paper, we investigate the incorporation of superstep cycles into the projected gradient method. We show for two problems in compressive sensing and image processing, namely the LASSO approach and the Rudin-Osher-Fatemi model that the resulting simple cyclic projected gradient algorithm can numerically compare with various state-of-the-art first-order algorithms. However, due to the nonlinear projection within the algorithm convergence proofs even under restrictive assumptions on the linear operators appear to be hard. We demonstrate the difficulties by studying the simplest case of a two-cycle algorithm in ?² with projections onto the Euclidean ball.     

applying a reduced gradient in quadratic programming

This paper considers specific aspects of implementing an algorithm for solving problems of quadratic programming, which is based on a reduced gradient method. In the subspace of superbasis variables, minimization is carried out by a conjugate gradient method. Some examples of solving test problems are given.     

A splitting method for quadratic programming problem

1. IntroductionThe quadratic programming (QP) problem is the most simple one in nonlinear pro-gramming and plays a very important role in optimization theory and applications.It is well known that matriX splitting teChniques are widely used for solving large-scalelinear system of equations very successfully. These algorithms generate an infinite sequence,in contrast to the direct algorithms which terminate in a finite number of steps. However,iterative algorithms are considerable simpler tha…     

An interior Newton method for quadratic programming

We propose a new (interior) approach for the general quadratic programming problem. We establish that the new method has strong convergence properties: the generated sequence converges globally to a point satisfying the second-order necessary optimality conditions, and the rate of convergence is 2-step quadratic if the limit point is a strong local minimizer. Published alternative interior approaches do not share such strong convergence properties for the nonconvex case. We also report on the results of preliminary numerical experiments: the results indicate that the proposed method has considerable practical potential. Received October 11, 1993 / Revised version received February 20, 1996 Published online July 19, 1999     

A projected conjugate gradient method for sparse minimax problems

A new method for nonlinear minimax problems is presented. The method is of the trust region type and based on sequential linear programming. It is a first order method that only uses first derivatives and does not approximate Hessians. The new method is well suited for large sparse problems as it only requires that software for sparse linear programming and a sparse symmetric positive definite equation solver are available. On each iteration a special linear/quadratic model of the function is minimized, but contrary to the usual practice in trust region methods the quadratic model is only defined on a one dimensional path from the current iterate to the boundary of the trust region. Conjugate gradients are used to define this path. One iteration involves one LP subproblem and requires three function evaluations and one gradient evaluation. Promising numerical results obtained with the method are presented. In fact, we find that the number of iterations required is comparable to that of state-of-the-art quasi-Newton codes.Research supported by The Nordic Council of Ministers, The Icelandic Science Council, The University of Iceland Research Fund and The Danish Natural Science Research Council.     

Dual gradient method for linearly constrained,strongly convex,separable mathematical programming problems

A new dual gradient method is given to solve linearly constrained, strongly convex, separable mathematical programming problems. The dual problem can be decomposed into one-dimensional problems whose solutions can be computed extremely easily. The dual objective function is shown to have a Lipschitz continuous gradient, and therefore a gradient-type algorithm can be used for solving the dual problem. The primal optimal solution can be obtained from the dual optimal solution in a straightforward way. Convergence proofs and computational results are given.     

A weighted gram-schmidt method for convex quadratic programming

Range-space methods for convex quadratic programming improve in efficiency as the number of constraints active at the solution decreases. In this paper we describe a range-space method based upon updating a weighted Gram-Schmidt factorization of the constraints in the active set. The updating methods described are applicable to both primal and dual quadratic programming algorithms that use an active-set strategy. Many quadratic programming problems include simple bounds on all the variables as well as general linear constraints. A feature of the proposed method is that it is able to exploit the structure of simple bound constraints. This allows the method to retain efficiency when the number ofgeneral constraints active at the solution is small. Furthermore, the efficiency of the method improves as the number of active bound constraints increases. This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110. The work of Nicholas Gould was supported by the Science and Engineering Research Council of Great Britain.     

Convergence of a projected gradient method variant for quasiconvex objectives

We present a version of the projected gradient method for solving constrained minimization problems with a competitive search strategy: an appropriate step size rule through an Armijo search along the feasible direction, thereby obtaining global convergence properties when the objective function is quasiconvex or pseudoconvex. In contrast to other similar step size rules, this one requires only one projection onto the feasible set per iteration, rather than one projection for each tentative step during the search for the step size, which represents a considerable saving when the projections are computationally expensive.     

A multivariate spectral projected gradient method for bound constrained optimization

In this paper, we consider a multivariate spectral projected gradient (MSPG) method for bound constrained optimization. Combined with a quasi-Newton property, the multivariate spectral projected gradient method allows an individual adaptive step size along each coordinate direction. On the basis of nonmonotone line search, global convergence is established. A numerical comparison with the traditional SPG method shows that the method is promising.     

Convergence of the projected gradient method for quasiconvex multiobjective optimization

We consider the projected gradient method for solving the problem of finding a Pareto optimum of a quasiconvex multiobjective function. We show convergence of the sequence generated by the algorithm to a stationary point. Furthermore, when the components of the multiobjective function are pseudoconvex, we obtain that the generated sequence converges to a weakly efficient solution.     

Dual support method for solving convex quadratic programs

In this article, we present a new dual method for solving convex (but not strictly convex) quadratic programs (QPs). Our method is the generalization of the dual support method, developed by Gabasov and co-workers in 1981, for solving convex QPs. It proceeds in two phases: the first is to construct the initial support, called coordinator support, for the problem and the second is to achieve the optimality of the problem. Results of numerical experiments are given comparing our approach with the active-set method.     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.     

A robust sequential quadratic programming method

The sequential quadratic programming method developed by Wilson, Han and Powell may fail if the quadratic programming subproblems become infeasible, or if the associated sequence of search directions is unbounded. This paper considers techniques which circumvent these difficulties by modifying the structure of the constraint region in the quadratic programming subproblems. Furthermore, questions concerning the occurrence of an unbounded sequence of multipliers and problem feasibility are also addressed.Work supported in part by the National Science Foundation under Grant No. DMS-8602399 and by the Air Force Office of Scientific Research under Grant No. ISSA-860080.Work supported in part by the National Science Foundation under Grant No. DMS-8602419.     

On the convergence of the projected gradient method

We study the projected gradient algorithm for linearly constrained optimization. Wolfe (Ref. 1) has produced a counterexample to show that this algorithm can jam. However, his counterexample is only ¹( ⁿ ), and it is conjectured that the algorithm is convergent for ²-functions. We show that this conjecture is partly right. We also show that one needs more assumptions to prove convergence, since we present a family of counterexamples. We finally give a demonstration that no jamming can occur for quadratic objective functions.This work was supported by the Natural Sciences and Engineering Research Council of Canada     

Solving semi-infinite programs by smoothing projected gradient method

In this paper, we study a semi-infinite programming (SIP) problem with a convex set constraint. Using the value function of the lower level problem, we reformulate SIP problem as a nonsmooth optimization problem. Using the theory of nonsmooth Lagrange multiplier rules and Danskin’s theorem, we present constraint qualifications and necessary optimality conditions. We propose a new numerical method for solving the problem. The novelty of our numerical method is to use the integral entropy function to approximate the value function and then solve SIP by the smoothing projected gradient method. Moreover we study the relationships between the approximating problems and the original SIP problem. We derive error bounds between the integral entropy function and the value function, and between locally optimal solutions of the smoothing problem and those for the original problem. Using certain second order sufficient conditions, we derive some estimates for locally optimal solutions of problem. Numerical experiments show that the algorithm is efficient for solving SIP.     

An interior point method for quadratic programs based on conjugate projected gradients

We propose an interior point method for large-scale convex quadratic programming where no assumptions are made about the sparsity structure of the quadratic coefficient matrixQ. The interior point method we describe is a doubly iterative algorithm that invokes aconjugate projected gradient procedure to obtain the search direction. The effect is thatQ appears in a conjugate direction routine rather than in a matrix factorization. By doing this, the matrices to be factored have the same nonzero structure as those in linear programming. Further, one variant of this method istheoretically convergent with onlyone matrix factorization throughout the procedure.     

An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization

Mathematical Programming - We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate...