共查询到20条相似文献,搜索用时 109 毫秒
1.
1 , the smallest eigenvalue of a symmetric, positive definite matrix, and is solved by Newton iteration with line search. The
paper describes the algorithm and its implementation including estimation of λ1, how to get a good starting point for the iteration, and up- and downdating of Cholesky factorization. Results of extensive
testing and comparison with other methods for constrained QP are given.
Received May 1, 1997 / Revised version received March 17, 1998 Published online November 24, 1998 相似文献
2.
Basis- and partition identification for quadratic programming and linear complementarity problems 总被引:1,自引:0,他引:1
Arjan B. Berkelaar Benjamin Jansen Kees Roos Tamás Terlaky 《Mathematical Programming》1999,86(2):261-282
Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide
maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other
hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification
algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification
algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from
any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski
and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity
problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality
property of basis tableaus.
Received April 9, 1996 / Revised version received April 27, 1998?
Published online May 12, 1999 相似文献
3.
Received March 18, 1996 / Revised version received August 8, 1997 Published online November 24, 1998 相似文献
4.
Received June 6, 1995 / Revised version received May 26, 1998 Published online October 9, 1998 相似文献
5.
Received February 10, 1997 / Revised version received June 6, 1998 Published online October 9, 1998 相似文献
6.
Jörg Fliege 《Mathematical Programming》1999,84(2):435-438
Received September 3, 1997 / Revised version received March 20, 1998 Published online October 9, 1998 相似文献
7.
A branch and cut algorithm for nonconvex quadratically constrained quadratic programming 总被引:12,自引:0,他引:12
Charles Audet Pierre Hansen Brigitte Jaumard Gilles Savard 《Mathematical Programming》2000,87(1):131-152
We present a branch and cut algorithm that yields in finite time, a globally ε-optimal solution (with respect to feasibility
and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic
terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four
classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select
the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree,
and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at
any node of the tree is flexible enough to be used at other nodes. Computational results are reported that include standard
test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality.
Received December 19, 1997 / Revised version received July 26, 1999?Published online November 9, 1999 相似文献
8.
Received July 24, 1997 / Revised version received August 9, 1998
Published online January 20, 1999 相似文献
9.
Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation
methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming)
Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems
have a linear objective function c
T
x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,”
into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number
of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of
standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method
which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for
a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method
which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations.
Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000 相似文献
10.
An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints 总被引:12,自引:0,他引:12
Le Thi Hoai An 《Mathematical Programming》2000,87(3):401-426
In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids.
The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the
proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound
scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham
Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting
point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order
to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the
ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can
be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting
procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems.
Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA
and the combined DCA-branch-and-bound algorithm.
Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000 相似文献
11.
Received January 9, 1997 / Revised version received January 26, 1998
Published online November 24, 1998 相似文献
12.
Received June 4, 1996 / Revised version received November 19, 1997
Published online November 24, 1998 相似文献
13.
Stephen M. Robinson 《Mathematical Programming》1999,85(1):1-13
* TL, where T is maximal monotone and L is linear and continuous with adjoint L*.
Received September 9, 1997 / Revised version received June 30, 1998 Published online January 20, 1999 相似文献
14.
Asymptotic constraint qualifications and global error bounds for convex inequalities 总被引:2,自引:0,他引:2
Received October 26, 1996 / Revised version received October 1, 1997 Published online October 9, 1998 相似文献
15.
A.S. Lewis 《Mathematical Programming》1999,84(1):1-24
Received October 28, 1996 / Revised version received January 28, 1998 Published online October 9, 1998 相似文献
16.
We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound
uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known
projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and
computational effort.
Received: February 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
17.
Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems 总被引:3,自引:0,他引:3
ln) iterations, where ν is the parameter of a self-concordant barrier for the cone, ε is a relative accuracy and ρf is a feasibility measure.
We also discuss the behavior of path-following methods as applied to infeasible problems. We prove that strict infeasibility
(primal or dual) can be detected in O(ln) iterations, where ρ· is a primal or dual infeasibility measure.
Received April 25, 1996 / Revised version received March 4, 1998 Published online October 9, 1998 相似文献
18.
, they differ from the Legendre-Clebsch condition. They give information about the Hesse matrix of the integrand at not only
inactive points but also active points. On the other hand, since the inequality state constraints can be regarded as an infinite
number of inequality constraints, they sometimes form an envelope. According to a general theory [9], one has to take the
envelope into consideration when one consider second-order necessary optimality conditions for an abstract optimization problem
with a generalized inequality constraint. However, we show that we do not need to take it into account when we consider Legendre-type
conditions. Finally, we show that any inequality state constraint forms envelopes except two trivial cases. We prove it by
presenting an envelope in a visible form.
Received April 18, 1995 / Revised version received January 5, 1998 Published online August 18, 1998 相似文献
19.
Mihai Anitescu 《Mathematical Programming》2002,92(2):359-386
We analyze the convergence of a sequential quadratic programming (SQP) method for nonlinear programming for the case in which
the Jacobian of the active constraints is rank deficient at the solution and/or strict complementarity does not hold for some
or any feasible Lagrange multipliers. We use a nondifferentiable exact penalty function, and we prove that the sequence generated
by an SQP using a line search is locally R-linearly convergent if the matrix of the quadratic program is positive definite
and constant over iterations, provided that the Mangasarian-Fromovitz constraint qualification and some second-order sufficiency
conditions hold.
Received: April 28, 1998 / Accepted: June 28, 2001?Published online April 12, 2002 相似文献
20.
A class of affine-scaling interior-point methods for bound constrained optimization problems is introduced which are locally
q–superlinear or q–quadratic convergent. It is assumed that the strong second order sufficient optimality conditions at the
solution are satisfied, but strict complementarity is not required. The methods are modifications of the affine-scaling interior-point
Newton methods introduced by T. F. Coleman and Y. Li (Math. Programming, 67, 189–224, 1994). There are two modifications. One is a modification of the scaling matrix, the other one is the use of a
projection of the step to maintain strict feasibility rather than a simple scaling of the step. A comprehensive local convergence
analysis is given. A simple example is presented to illustrate the pitfalls of the original approach by Coleman and Li in
the degenerate case and to demonstrate the performance of the fast converging modifications developed in this paper.
Received October 2, 1998 / Revised version received April 7, 1999?Published online July 19, 1999 相似文献