共查询到10条相似文献,搜索用时 125 毫秒
1.
Michael J. Best 《Mathematical Programming》1984,30(1):71-87
We formulate a general algorithm for the solution of a convex (but not strictly convex) quadratic programming problem. Conditions
are given under which the iterates of the algorithm are uniquely determined. The quadratic programming algorithms of Fletcher,
Gill and Murray, Best and Ritter, and van de Panne and Whinston/Dantzig are shown to be special cases and consequently are
equivalent in the sense that they construct identical sequences of points. The various methods are shown to differ only in
the manner in which they solve the linear equations expressing the Kuhn-Tucker system for the associated equality constrained
subproblems. Equivalence results have been established by Goldfarb and Djang for the positive definite Hessian case. Our analysis
extends these results to the positive semi-definite case.
This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189. 相似文献
2.
By using conjugate directions a method for solving convex quadratic programming problems is developed. The algorithm generates a sequence of feasible solutions and terminates after a finite number of iterations. Extensions of the algorithm for nonconvex and large structured quadratic programming problems are discussed.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 and in part by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A 8189 and E 5582. 相似文献
3.
Robert Mifflin 《Mathematical Programming》1979,16(1):141-158
This paper presents a feasible descent algorithm for solving certain constrained least squares problems. These problems are specially structured quadratic programming problems with positive semidefinite Hessian matrices that are allowed to be singular. The algorithm generates a finite sequence of subproblems that are solved using the numerically stable technique of orthogonal factorization with reorthogonalization and Given's transformation updating.This material is based upon work supported by the National Science Foundation under Grant No. MCS 78-06716 and by the International Institute for Applied Systems Analysis. 相似文献
4.
Philip E. Gill Nicholas I. M. Gould Walter Murray Michael A. Saunders Margaret H. Wright 《Mathematical Programming》1984,30(2):176-195
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. 相似文献
5.
We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem.This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432. 相似文献
6.
We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized
Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying
a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon
which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic
programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem.
This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate
Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432. 相似文献
7.
一个关于二次规划问题的分段线性同伦算法 总被引:1,自引:1,他引:0
杨冰 《高校应用数学学报(A辑)》1994,(1):66-74
本文发展了一个关于二次规划问题的分段线性同伦算法。该算法可看作是外点罚函数法的一个变体。凡是符合外点罚函数法收敛条件的二次规划问题用该算法均可经有限次轮回运算得到稳定解。大量的关于随机的凸二次规划问题的数值实验结果表明它的计算效率是高的,在某些条件下可能是多项式时间算法。 相似文献
8.
A new penalty function is associated with an inequality constrained nonlinear programming problem via its dual. This penalty
function is globally differentiable if the functions defining the original problem are twice globally differentiable. In addition,
the penalty parameter remains finite. This approach reduces the original problem to a simple problem of maximizing a globally
differentiable function on the product space of a Euclidean space and the nonnegative orthant of another Euclidean space.
Many efficient algorithms exist for solving this problem. For the case of quadratic programming, the penalty function problem
can be solved effectively by successive overrelaxation (SOR) methods which can handle huge problems while preserving sparsity
features.
Sponsored by the United States Army under Contract No. DAAG 29-80-C-0041. This material is based upon work supported by the
National Science Foundation under Grants No. MCS-790166 and ENG-7903881. 相似文献
9.
Eric Rosenberg 《Mathematical Programming》1981,21(1):319-330
The several published methods for mapping a dual solution estimate to a primal solution estimate in posynomial geometric programming provide no criteria for deciding how much deviation from primal feasibility, or discrepancy between the primal and dual objective function values, should be permitted before the primal solution estimate is accepted by the designer. This paper presents a new and simple dual-to-primal conversion method that uses the cost coefficients to provide a sound economic criterion for determining when to accept a primal solution estimate. The primal solution estimate generated is the exact solution to a modified primal obtained from the given primal by modifying the cost coefficients, with the exponent matrix left unchanged. The method is shown to have desirable properties when coupled with a convergent dual algorithm. 相似文献
10.
Jie Sun 《Mathematical Programming》1993,60(1-3):69-79
This paper presents a theoretical result on convergence of a primal affine-scaling method for convex quadratic programs. It is shown that, as long as the stepsize is less than a threshold value which depends on the input data only, Ye and Tse's interior ellipsoid algorithm for convex quadratic programming is globally convergent without nondegeneracy assumptions. In addition, its local convergence rate is at least linear and the dual iterates have an ergodically convergent property.Research supported in part by the NSF under grant DDM-8721709. 相似文献