quadraticprogramming is a class of constrained optimization problems with quadratic objective function and linear constraints. It is an important optimization problem with applications in many areas and is also used ...
详细信息
quadraticprogramming is a class of constrained optimization problems with quadratic objective function and linear constraints. It is an important optimization problem with applications in many areas and is also used to solve nonlinear optimization problems. quadratic programs arisen in practice are often large, but sparse, and have a special Hessian structure which we can exploit. They usually cannot be solved efficiently without exploiting their structures. This thesis proposes methods for solving several classes of quadraticprogramming with structure. We show a heuristic method for the large-scalequadratic programs with block diagonal Hessian matrices and dense constraint matrices. Our method separates the problem into smaller problems, computes optimal solutions for the smaller problems, and uses them to construct the solution to the original problem. Computational results show that our method is highly efficient at computing approximate solutions for large-scale problems. The other method is an efficient method to compute the search directions for the primal-dual path-following interior- point method for the similar class of Hessian matrix structure and dense constraint matrices. The time complexity of the method is significantly smaller than that of using a sparse linear solver. The computational results also show that the proposed method is faster. This thesis also proposes a pivot selection algorithm for the factorization of the Karush-Kuhn-Tucker (KKT) matrix for the equality constrained quadratic programs whose constraint matrices are block diagonal. Such factorization should maintain both sparsity and numerical stability of the factors, both of which depend solely on the choices of the pivots. The proposed method maintains the sparsity and stability of the problem. The experiments show that the pivot selection algorithm appears to produce no fill-ins in the factorization of such matrices. In addition, we compare the method with MA57 and find that the fa
Computational methods are considered for finding a point that satisfies the second-order necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formul...
详细信息
Computational methods are considered for finding a point that satisfies the second-order necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formulation and analysis of an active-set method for a generic QP with both equality and inequality constraints. The method uses a search direction that is the solution of an equality-constrained subproblem involving a "working set" of linearly independent constraints. The method is a reformulation of a method for general QP first proposed by Fletcher, and modified subsequently by Gould. The reformulation facilitates a simpler analysis and has the benefit that the algorithm reduces to a variant of the simplex method when the QP is a linear program. The search direction is computed from a KKT system formed from the QP Hessian and the gradients of the working-set constraints. It is shown that, under certain circumstances, the solution of this KKT system may be updated using a simple recurrence relation, thereby giving a significant reduction in the number of KKT systems that need to be solved. The second part of the paper focuses on the solution of QP problems with constraints in so-called standard form. We describe how the constituent KKT systems are solved, and discuss how an initial basis is defined. Numerical results are presented for all QPs in the CUTEst test collection.
Iterative solvers appear to be very promising in the development of efficient software, based on Interior Point methods, for large-scale nonlinear optimization problems. In this paper we focus on the use of preconditi...
详细信息
Iterative solvers appear to be very promising in the development of efficient software, based on Interior Point methods, for large-scale nonlinear optimization problems. In this paper we focus on the use of preconditioned iterative techniques to solve the KKT system arising at each iteration of a Potential Reduction method for convex quadraticprogramming. We consider the augmented system approach and analyze the behaviour of the Constraint Preconditioner with the Conjugate Gradient algorithm. Comparisons with a direct solution of the augmented system and with MOSEK show the effectiveness of the iterative approach on large-scale sparse problems.
We describe the design of version 1.0 of GALAHAD, a library of Fortran 90 packages for large-scale nonlinear optimization. The library particularly addresses quadraticprogramming problems, containing both interior po...
详细信息
We describe the design of version 1.0 of GALAHAD, a library of Fortran 90 packages for large-scale nonlinear optimization. The library particularly addresses quadraticprogramming problems, containing both interior point and active set algorithms, as well as tools for preprocessing problems prior to solution. It also contains an updated version of the venerable nonlinear programming package, LANCELOT.
The constraint-partitioning approach achieves a significant reduction in solution time while resolving some large-scale mixed-integer optimization problems. Its theoretical foundation, extended saddle-point theory, wh...
详细信息
ISBN:
(纸本)9783642163357
The constraint-partitioning approach achieves a significant reduction in solution time while resolving some large-scale mixed-integer optimization problems. Its theoretical foundation, extended saddle-point theory, which implies the original problem can be decomposed into several subproblems of relatively smaller scale in virtue of the separability of extended saddle-point conditions, still needs to be deliberated carefully. Enlightened by such a plausible theory, we have developed a novel parallel algorithm for convex programming. Our approach not only works well theoretically, but also may be promising in numerical experiments. As the theoretical essence of Support Vector Machine (SVM) is a quadraticprogramming, we are inspired to apply this new method onto large-scale SVMs to achieve some numerical improvements.
暂无评论