首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Parametric global optimisation for bilevel programming   总被引:2,自引:2,他引:0  
We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.  相似文献   

2.
The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.  相似文献   

3.
The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.  相似文献   

4.
A new decomposition method for multistage stochastic linear programming problems is proposed. A multistage stochastic problem is represented in a tree-like form and with each node of the decision tree a certain linear or quadratic subproblem is associated. The subproblems generate proposals for their successors and some backward information for their predecessors. The subproblems can be solved in parallel and exchange information in an asynchronous way through special buffers. After a finite time the method either finds an optimal solution to the problem or discovers its inconsistency. An analytical illustrative example shows that parallelization can speed up computation over every sequential method. Computational experiments indicate that for large problems we can obtain substantial gains in efficiency with moderate numbers of processors.This work was partly supported by the International Institute for Applied Systems Analysis, Laxenburg, Austria.  相似文献   

5.
It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.  相似文献   

6.
Based on an augmented Lagrangian line search function, a sequential quadratically constrained quadratic programming method is proposed for solving nonlinearly constrained optimization problems. Compared to quadratic programming solved in the traditional SQP methods, a convex quadratically constrained quadratic programming is solved here to obtain a search direction, and the Maratos effect does not occur without any other corrections. The “active set” strategy used in this subproblem can avoid recalculating the unnecessary gradients and (approximate) Hessian matrices of the constraints. Under certain assumptions, the proposed method is proved to be globally, superlinearly, and quadratically convergent. As an extension, general problems with inequality and equality constraints as well as nonmonotone line search are also considered.  相似文献   

7.
Two important problems in the area of engineering plasticity are limit load analysis and elastoplastic analysis. It is well known that these two problems can be formulated as linear and quadratic programming problems, respectively (Refs. 1–2). In applications, the number of variables in each of these mathematical programming problems tends to be large. Consequently, it is important to have efficient numerical methods for their solution. The purpose of this paper is to present a method which allows the quadratic programming formulation of the elastoplastic analysis to be reformulated as an equivalent quadratic programming problem which has significantly fewer variables than the original formulation. Indeed, in Section 4, we will present details of an example for which the original quadratic programming formulation required 297 variables and for which the equivalent formulation presented here required only two variables. The method is based on a characterization of the entire family of optimal solutions for a linear programming problem.This research was supported by the Natural Science and Engineering Council of Canada under Grant No. A8189 and by a Leave Fellowship from the Social Sciences and Humanities Research Council of Canada. The author takes pleasure in acknowledging many stimulating discussions with Professor D. E. Grierson.  相似文献   

8.
One objective in regional planning is the creation of communities with great accessibility. Thus we should plan the locations of inhabitants and the activities of the region so that the total accessibility will be maximized subject to some restrictions. This is a quadratic programming problem, which can be solved by quadratic programming techniques, but we cannot then take into account the uncertainties of the problem.In this paper a new criterion function is proposed for accessibility, uncertainty problems in regional land-use planning. It is derived from Hurwicz's generalized maximin principle. Many advantages are gained, for the planning problem is separated into linear programming problems, the uncertainties are taken into consideration as in game theory and the methods of parametric programming are available.A simplified problem of the populations of three town areas is studied and the method is generalized for problems of many activities and areas.  相似文献   

9.
Multibody elastic contact analysis by quadratic programming   总被引:1,自引:0,他引:1  
A quadratic programming method for contact problems is extended to a general problem involving contact ofn elastic bodies. Sharp results of quadratic programming theory provide an equivalence between the originaln-body contact problem and the simplex algorithm used to solve the quadratic programming problem. Two multibody examples are solved to illustrate the technique.  相似文献   

10.
The paper deals with the numerical solution of the quasi-variational inequality describing the equilibrium of an elastic body in contact with a rigid foundation under Coulomb friction. After a discretization of the problem by mixed finite elements, the duality approach is exploited to reduce the problem to a sequence of quadratic programming problems with box constraints, so that efficient recently proposed algorithms may be applied. A new variant of this method is presented. It combines fixed point with block Gauss–Seidel iterations. The method may be also considered as a new implementation of fixed point iterations for a sequence of problems with given friction. Results of numerical experiments are given showing that the resulting algorithm may be much faster than the original fixed point method and its efficiency is comparable with the solution of frictionless contact problems.  相似文献   

11.
求解凸二次规划问题的势下降内点算法   总被引:11,自引:0,他引:11  
1 引 言二次规划问题的求解是数学规划和工业应用等领域的一个重要课题 ,同时也是解一般非线性规划问题的序列二次规划算法的关键 .求解二次规划问题的早期技术是利用线性规划问题的单纯形方法求解二次规划问题的 KKT最优性必要条件[1 ] .这类算法比较直观 ,但在处理不等式约束时 ,松弛变量的引进很容易导致求解过程的明显减慢 .有效集策略是求解二次规划问题的另一类主要技术 .这类方法一般都是稳定的 ,但随着问题中大量不等式约束的出现 ,其收敛速度将越来越低[2 ] .简约空间技术将所求问题的 Hessian阵投影到自由变量所在的子空间中 …  相似文献   

12.
The implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for the solution of large convex equality constrained quadratic programming problems is considered. It is proved that if the auxiliary problems are approximately solved by the conjugate gradient method, then the algorithm finds an approximate solution of the class of problems with uniformly bounded spectrum of the Hessian matrix at O(1) matrix–vector multiplications. If applied to the class of problems with the Hessian matrices that are in addition either sufficiently sparse or can be expressed as a product of such sparse matrices, then the cost of the solution is proportional to the dimension of the problems. Theoretical results are illustrated by numerical experiments. This research is supported by grants of the Ministry of Education No. S3086102, ET400300415 and MSM 6198910027.  相似文献   

13.
It is co-NP-complete to decide whether a given matrix is copositive or not. In this paper, this decision problem is transformed into a quadratic programming problem, which can be approximated by solving a sequence of linear conic programming problems defined on the dual cone of the cone of nonnegative quadratic functions over the union of a collection of ellipsoids. Using linear matrix inequalities (LMI) representations, each corresponding problem in the sequence can be solved via semidefinite programming. In order to speed up the convergence of the approximation sequence and to relieve the computational effort of solving linear conic programming problems, an adaptive approximation scheme is adopted to refine the union of ellipsoids. The lower and upper bounds of the transformed quadratic programming problem are used to determine the copositivity of the given matrix.  相似文献   

14.
This paper presents a global optimization approach for solving signomial geometric programming problems. In most cases nonconvex optimization problems with signomial parts are difficult, NP-hard problems to solve for global optimality. But some transformation and convexification strategies can be used to convert the original signomial geometric programming problem into a series of standard geometric programming problems that can be solved to reach a global solution. The tractability and effectiveness of the proposed successive convexification framework is demonstrated by seven numerical experiments. Some considerations are also presented to investigate the convergence properties of the algorithm and to give a performance comparison of our proposed approach and the current methods in terms of both computational efficiency and solution quality.  相似文献   

15.
In this paper, we present a smoothing sequential quadratic programming to compute a solution of a quadratic convex bilevel programming problem. We use the Karush-Kuhn-Tucker optimality conditions of the lower level problem to obtain a nonsmooth optimization problem known to be a mathematical program with equilibrium constraints; the complementary conditions of the lower level problem are then appended to the upper level objective function with a classical penalty. These complementarity conditions are not relaxed from the constraints and they are reformulated as a system of smooth equations by mean of semismooth equations using Fisher-Burmeister functional. Then, using a quadratic sequential programming method, we solve a series of smooth, regular problems that progressively approximate the nonsmooth problem. Some preliminary computational results are reported, showing that our approach is efficient.  相似文献   

16.
NLPQL is a FORTRAN implementation of a sequential quadratic programming method for solving nonlinearly constrained optimization problems with differentiable objective and constraint functions. At each iteration, the search direction is the solution of a quadratic programming subproblem. This paper discusses the organization of NLPQL, including the formulation of the subproblem and the information that must be provided by a user. A summary is given of the performance of different algorithmic options of NLPQL on a collection of test problems (115 hand-selected or application problems, 320 randomly generated problems). The performance of NLPQL is compared with that of some other available codes.  相似文献   

17.
The long-term planning of electricity generation in a liberalised market using the Bloom and Gallant model can be posed as a quadratic programming (QP) problem with an exponential number of linear inequality constraints called load-matching constraints (LMCs) and several other linear non-LMCs. Direct solution methods are inefficient at handling such problems and a heuristic procedure has been devised to generate only those LMCs that are likely to be active at the optimiser. The problem is then solved as a finite succession of QP problems with an increasing, though still limited, number of LMCs, which can be solved efficiently using a direct method, as would be the case with a QP interior-point algorithm. Warm starting between successive QP solutions helps then in reducing the number of iterations necessary to reach the optimiser.  相似文献   

18.
NLPQL is a FORTRAN implementation of a sequential quadratic programming method for solving nonlinearly constrained optimization problems with differentiable objective and constraint functions. At each iteration, the search direction is the solution of a quadratic programming subproblem. This paper discusses the organization of NLPQL, including the formulation of the subproblem and the information that must be provided by a user. A summary is given of the performance of different algorithmic options of NLPQL on a collection of test problems (115 hand-selected or application problems, 320 randomly generated problems). The performance of NLPQL is compared with that of some other available codes.  相似文献   

19.
A class of branch-and-bound methods is proposed for minimizing a quasiconvex-concave function subject to convex and quasiconvex-concave inequality constraints. Several important special cases where the subproblems involved by the bounding-and-branching operations can be solved quite effectively include certain d.c. programming problems, indefinite quadratic programming with one negative eigenvalue, affine multiplicative problems, and fractional multiplicative optimization.This research was accomplished while the second author was a Fellow of the Alexander von Humboldt Foundation at the University of Trier, Trier, Germany.  相似文献   

20.
Numerical test results are presented for solving smooth nonlinear programming problems with a large number of constraints, but a moderate number of variables. The active set method proceeds from a given bound for the maximum number of expected active constraints at an optimal solution, which must be less than the total number of constraints. A quadratic programming subproblem is generated with a reduced number of linear constraints from the so-called working set, which is internally changed from one iterate to the next. Only for active constraints, i.e., a certain subset of the working set, new gradient values must be computed. The line search is adapted to avoid too many active constraints which do not fit into the working set. The active set strategy is an extension of an algorithm described earlier by the author together with a rigorous convergence proof. Numerical results for some simple academic test problems show that nonlinear programs with up to 200,000,000 nonlinear constraints are efficiently solved on a standard PC.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号