共查询到20条相似文献,搜索用时 15 毫秒
1.
A successive quadratic programming algorithm with global and superlinear convergence properties 总被引:6,自引:0,他引:6
Masao Fukushima 《Mathematical Programming》1986,35(3):253-264
This paper presents a successive quadratic programming algorithm for solving general nonlinear programming problems. In order to avoid the Maratos effect, direction-finding subproblems are derived by modifying the second-order approximations to both objective and constraint functions of the problem. We prove that the algorithm possesses global and superlinear convergence properties.This work was supported in part by a Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan. 相似文献
2.
A standard Quadratic Programming problem (StQP) consists in minimizing a (nonconvex) quadratic form over the standard simplex. For solving a StQP we present an exact and a heuristic algorithm, that are based on new theoretical results for quadratic and convex optimization problems. With these results a StQP is reduced to a constrained nonlinear minimum weight clique problem in an associated graph. Such a clique problem, which does not seem to have been studied before, is then solved with an exact and a heuristic algorithm. Some computational experience shows that our algorithms are able to solve StQP problems of at least one order of magnitude larger than those reported in the literature. 相似文献
3.
4.
Described here is the structure and theory for a sequential quadratic programming algorithm for solving sparse nonlinear optimization problems. Also provided are the details of a computer implementation of the algorithm along with test results. The algorithm maintains a sparse approximation to the Cholesky factor of the Hessian of the Lagrangian. The solution to the quadratic program generated at each step is obtained by solving a dual quadratic program using a projected conjugate gradient algorithm. An updating procedure is employed that does not destroy sparsity. 相似文献
5.
In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the ratio is dependent on the data of the problem with α being a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α δd if every weight is strictly positive,where δd > 0 is a constant depending on the problem dimension and data. 相似文献
6.
In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001). 相似文献
7.
8.
9.
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 相似文献
10.
A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
Existing global optimization techniques for nonconvex quadratic programming (QP) branch by recursively partitioning the convex
feasible set and thus generate an infinite number of branch-and-bound nodes. An open question of theoretical interest is how
to develop a finite branch-and-bound algorithm for nonconvex QP. One idea, which guarantees a finite number of branching decisions,
is to enforce the first-order Karush-Kuhn-Tucker (KKT) conditions through branching. In addition, such an approach naturally
yields linear programming (LP) relaxations at each node. However, the LP relaxations are unbounded, a fact that precludes
their use. In this paper, we propose and study semidefinite programming relaxations, which are bounded and hence suitable
for use with finite KKT-branching. Computational results demonstrate the practical effectiveness of the method, with a particular
highlight being that only a small number of nodes are required.
This author was supported in part by NSF Grants CCR-0203426 and CCF-0545514. 相似文献
11.
1. IntroductionA bilevel programming problem (BLPP) involves two sequential optimization problems where the constraint region of the upper one is implicitly determined by the solutionof the lower. It is proved in [1] that even to find an approximate solution of a linearBLPP is strongly NP-hard. A number of algorithms have been proposed to solve BLPPs.Among them, the descent algorithms constitute an important class of algorithms for nonlinear BLPPs. However, it is assumed for almost all… 相似文献
12.
Yinyu Ye 《Mathematical Programming》2001,90(1):101-111
We present a .699-approximation algorithm for Max-Bisection, i.e., partitioning the nodes of a weighted graph into two blocks
of equal cardinality so as to maximize the weights of crossing edges. This is an improved result from the .651-approximation
algorithm of Frieze and Jerrum and the semidefinite programming relaxation of Goemans and Williamson.
Received: October 1999 / Accepted: July 2000?Published online January 17, 2001 相似文献
13.
Da-chuanXu Ji-yeHan 《计算数学(英文版)》2003,21(3):357-366
Using outward rotations,we obtain an approximation algorithm for Max-Bisection problem,i.e.,Partitioning the vertices of an unirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges.In many interesting cases,the algorithm performs better than the algorithms of Ye and of Halperin and Zwick .The main tool used to obtain this result is semidefinite programming. 相似文献
14.
A robust sequential quadratic programming method 总被引:9,自引:0,他引:9
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. 相似文献
15.
Zengxin Wei 《应用数学学报(英文版)》1992,8(3):281-288
The main difficulties encountered in the successive quadratic programming methods are the choice of penalty parameter, the choice of steplenth, and the Maratos effect. An algorithm without penalty parameters is presented in this paper. The choice of steplength parameters is based on the method of trust region. Global convergence and local superlinear convergence are proved under suitable assumption. 相似文献
16.
In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based
on the Fischer-Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an
equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which
is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown
to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set
to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported for 0-1
quadratic programming problems from the OR-Library, and the optimal values generated are made comparisons with those given
by the well-known SBB and BARON solvers. The comparison results indicate that the continuous approach is extremely promising
by the quality of the optimal values generated and the computational work involved, if the initial barrier parameter is chosen
appropriately.
This work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province. 相似文献
17.
A successive quadratic programming method for a class of constrained nonsmooth optimization problems
Masao Fukushima 《Mathematical Programming》1990,49(1-3):231-251
In this paper we present an algorithm for solving nonlinear programming problems where the objective function contains a possibly nonsmooth convex term. The algorithm successively solves direction finding subproblems which are quadratic programming problems constructed by exploiting the special feature of the objective function. An exact penalty function is used to determine a step-size, once a search direction thus obtained is judged to yield a sufficient reduction in the penalty function value. The penalty parameter is adjusted to a suitable value automatically. Under appropriate assumptions, the algorithm is shown to produce an approximate optimal solution to the problem with any desirable accuracy in a finite number of iterations. 相似文献
18.
For the general quadratic programming problem (including an equivalent form of the linear complementarity problem) a new solution method of branch and bound type is proposed. The branching procedure uses a well-known simplicial subdivision and the bound estimation is performed by solving certain linear programs. 相似文献
19.
Pairwise reactive sor algorithm for quadratic programming of net import spatial equilibrium models 总被引:1,自引:0,他引:1
F. Güder 《Mathematical Programming》1989,43(1-3):175-186
An iterative method based on the successive overrelaxation (SOR) is proposed to solve quadratic programming of net important spatial equilibrium models. The algorithm solves the problem by updating the variables pairwise at each iteration. The principal feature of the algorithm is that the lagrange multipliers corresponding to the constraints do not have to be calculated at each iteration as is the case in SOR based algorithms. Yet the Lagrange multipliers can easily be extracted from the solution values.This research was partially supported by grants from the James F. Kember Foundation and the School of Business, Loyola University of Chicago. 相似文献
20.
In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising. 相似文献