共查询到20条相似文献,搜索用时 0 毫秒
1.
Received March 18, 1996 / Revised version received August 8, 1997 Published online November 24, 1998 相似文献
2.
Approximating quadratic programming with bound and quadratic constraints 总被引:27,自引:3,他引:24
Yinyu Ye 《Mathematical Programming》1999,84(2):219-226
Received May 20, 1997 / Revised version received March 9, 1998 Published online October 9, 1998 相似文献
3.
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 相似文献
4.
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 相似文献
5.
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 相似文献
6.
Tran Van Nghi 《Optimization》2018,67(2):269-285
This paper deals with the stability of the solution set to parametric generalized affine variational inequalities with constraint set being defined by finitely many convex quadratic functions. The obtained results develop and complement the published ones. 相似文献
7.
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 相似文献
8.
9.
Received June 4, 1996 / Revised version received November 19, 1997 Published online November 24, 1998 相似文献
10.
An interior Newton method for quadratic programming 总被引:2,自引:0,他引:2
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 相似文献
11.
In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation
of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic
center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity
condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function
of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming
case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain
a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the
constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due
to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based
on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right
hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since
a similar set for which the primal-dual Slater condition holds is always open.
Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001 相似文献
12.
In this paper, we consider a special class of nonconvex programming problems for which the objective function and constraints
are defined in terms of general nonconvex factorable functions. We propose a branch-and-bound approach based on linear programming
relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev
interpolation polynomials coordinated with a Reformulation-Linearization Technique (RLT). A suitable partitioning process
is proposed that induces convergence to a global optimum. The algorithm has been implemented in C++ and some preliminary computational
results are reported on a set of fifteen engineering process control and design test problems from various sources in the
literature. The results indicate that the proposed procedure generates tight relaxations, even via the initial node linear
program itself. Furthermore, for nine of these fifteen problems, the application of a local search method that is initialized
at the LP relaxation solution produced the actual global optimum at the initial node of the enumeration tree. Moreover, for
two test cases, the global optimum found improves upon the solutions previously reported in the source literature.
Received: January 14, 1998 / Accepted: June 7, 1999?Published online December 15, 2000 相似文献
13.
《Optimization》2012,61(6):627-639
Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples. 相似文献
14.
A.B. Levy 《Mathematical Programming》1999,85(2):397-406
n such that x≥0, F(x,u)-v≥0 , and F(x,u)-v T·x=0 where these are vector inequalities. We characterize the local upper Lipschitz continuity of the (possibly set-valued)
solution mapping which assigns solutions x to each parameter pair (v,u). We also characterize when this solution mapping is
locally a single-valued Lipschitzian mapping (so solutions exist, are unique, and depend Lipschitz continuously on the parameters).
These characterizations are automatically sufficient conditions for the more general (and usual) case where v=0. Finally,
we study the differentiability properties of the solution mapping in both the single-valued and set-valued cases, in particular
obtaining a new characterization of B-differentiability in the single-valued case, along with a formula for the B-derivative.
Though these results cover a broad range of stability properties, they are all derived from similar fundamental principles
of variational analysis.
Received March 30, 1998 / Revised version received July 21, 1998
Published online January 20, 1999 相似文献
15.
In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization
problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems,
as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive
semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis
of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation
result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain
the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM
J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating
those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and
that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain
an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite.
This research was supported in part by NSF grant DMS-0306611. 相似文献
16.
Nguyen Nang Tam 《Journal of Global Optimization》2002,23(1):43-61
This paper characterizes the continuity property of the optimal value function in a general parametric quadratic programming problem with linear constraints. The lower semicontinuity and upper semicontinuity properties of the optimal value function are studied as well. 相似文献
17.
This paper describes a new technique for generating convex, strictly concave and indefinite (bilinear or not) quadratic programming problems. These problems have a number of properties that make them useful for test purposes. For example, strictly concave quadratic problems with their global maximum in the interior of the feasible domain and with an exponential number of local minima with distinct function values and indefinite and jointly constrained bilinear problems with nonextreme global minima, can be generated.Unlike most existing methods our construction technique does not require the solution of any subproblems or systems of equations. In addition, the authors know of no other technique for generating jointly constrained bilinear programming problems.Support of this work has been provided by the Instituto Nacional de Investigação Científica de Portugal (INIC) under contract 89/EXA/5 and by the Natural Sciences and Engineering Research Council of Canada operating grant 5671.Much of this paper was completed while this author was on a research sabbatical at the Universidade de Coimbra, Portugal. 相似文献
18.
《Optimization》2012,61(1-2):45-60
We obtain some conditions under which a small perturbation in the data of a quadratic programming problem can yield only a small change in its Karush-Kuhn-Tucker point set. Convexity of the objective function and boundedness of the constraint set are not assumed. The obtained results are illustrated by several examples 相似文献
19.
Francisco A. M. Gomes María Cristina Maciel José Mario Martínez 《Mathematical Programming》1999,84(1):161-200
The strategy for obtaining global convergence is based on the trust region approach. The merit function is a type of augmented Lagrangian. A new updating scheme is introduced for the penalty parameter, by means of which monotone increase is not necessary. Global convergence results are proved and numerical experiments are presented. Received May 31, 1995 / Revised version received December 12, 1997 Published online October 21, 1998 相似文献
20.
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 相似文献