检索结果-内蒙古大学图书馆

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

MATHEMATICAL PROGRAMMING 2004年第3期100卷 517-535页

作者： Kesavan, P Allgor, RJ Gatzke, EP Barton, PI Sensitron Semicond Deer Pk NY 11729 USA Amazon Com Inc Seattle WA USA Univ S Carolina Dept Chem Engn Columbia SC 29208 USA MIT Dept Chem Engn Cambridge MA 02139 USA

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.

关键词： mixed-integer nonconvex nonlinear programming decomposition algorithms global solution

来源：评论

学校读者我要写书评

暂无评论

A proximal decomposition algorithm for variational inequality problems

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2003年第1期161卷 231-244页

作者： Han, DR Nanjing Normal Univ Sch Math & Comp Sci Nanjing 210097 Peoples R China

In this paper, we propose a new decomposition algorithm for solving monotone variational inequality problems with linear constraints. The algorithm utilizes the problem's structure conductive to decomposition. At each iteration, the algorithm solves a system of nonlinear equations, which is structurally much easier to solve than variational inequality problems, the subproblems of classical decomposition methods, and then performs a projection step to update the multipliers. We allow to solve the subproblems approximately and we prove that under mild assumptions on the problem's data, the algorithm is globally convergent. We also report some preliminary computational results, which show that the algorithm is encouraging. (C) 2003 Elsevier B.V. All rights reserved.

关键词： variational inequality problems decomposition algorithms global convergence monotone mappings

来源：评论

学校读者我要写书评

暂无评论

New decomposition methods for solving variational inequality problems

引用

MATHEMATICAL AND COMPUTER MODELLING 2003年第3-4期37卷 405-418页

作者： Han, DR Sun, WY Nanjing Normal Univ Sch Math & Comp Sci Nanjing 210097 Peoples R China

For solving large-scale constrained separable variational inequality problems, the de-composition methods are attractive, since they solve the original problems via solving a series of small-scale problems, which may be much easier to solve than the original problems. In this paper, we-propose some new decomposition methods, which axe based on the Lagrange and the augmented Lagrange mappings of the problems, respectively. For the global convergence, the first method needs the partial cocoercivity of the underlying mapping, while the second one just requires monotonicity, a condition which is much weaker than partial cocoercivity. The cost for this weaker condition is to perform two additional projection steps on the dual variables and the primal-dual variables. We then extend the method to a more practical one, which just solves the subproblem approximately. We also report some computational results of the inexact method to show its promise. (C) 2003 Elsevier Science Ltd. All rights reserved.

关键词： variational inequality problems decomposition algorithms partial cocoercive mappings monotone mappings global convergence

来源：评论

学校读者我要写书评

暂无评论

The obstacle problem for water tanks

引用

JOURNAL DE MATHEMATIQUES PURES ET APPLIQUEES 2003年第11期82卷 1527-1553页

作者： Bonnans, JF Fourati, RB Smaoui, H Inst Natl Rech Informat & Automat Projet SYDOCO F-78153 Rocquencourt France ENIT URMCS Tunis Tunisia

In this paper we discuss the problem of computing and analyzing the static equilibrium of a nonrigid water tank. Specifically, we fix the amount of water contained in the tank, modelled as a membrane. In addition, there are rigid obstacles that constrain the deformation. This amounts to a nonconvex variational problem. We derive the optimality system and its interpretation in terms of equilibrium of forces. A second-order sensitivity analysis, allowing to compute derivatives of solutions and a second-order Taylor expansion of the cost function, is performed, in spite of the fact that the cost function is not twice differentiable. We also study the finite elements discretization, introduce a decomposition algorithm for the numerical computation of the solution, and display numerical results. (C) 2003 Editions scientifiques et medicales Elsevier SAS. All rights reserved.

关键词： obstacle problem nonconvex variational problems sensitivity analysis finite elements decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

Performance analysis of a parallel Dantzig-Wolfe decomposition algorithm for linear programming

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2002年第10-11期44卷 1431-1437页

作者： Lyu, J Luh, H Lee, MC Natl Cheng Kung Univ Dept Ind Management Sci Tainan Taiwan Natl Chengchi Univ Tainan Taiwan

This paper employs the Dantzig-Wolfe decomposition principle to solve linear programming models in a parallel-computing environment. Adopting the queuing discipline, we showed that under very general conditions, the proposed algorithm speedup trends toward a limiting value as the number of processors increases. (C) 2002 Elsevier Science Ltd. All rights reserved.

关键词： linear programming decomposition algorithms parallel processing

来源：评论

学校读者我要写书评

暂无评论

Cutting plane methods based on the analytic barrier for minimization of a convex function subject to box-constraints

引用

OPTIMIZATION METHODS & SOFTWARE 2002年第2期17卷 251-269页

作者： Beer, K Skokov, VA Tech Univ Chemnitz Fak Math D-09107 Chemnitz Germany

We analyze three variants of analytic barrier methods for minimization of a convex function under box-constraints: the classical method of analytic barriers (centres), the proximal method of analytic barriers and the modified proximal method of analytic barriers. We give theoretical and practical complexity estimates of these methods and based on numerical tests outline their dependence on the used control parameters. We consider also the case where the objective function is not given in explicit analytic form and may not be defined everywhere.

关键词： nondifferentiable optimization centre methods cutting plane methods decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing call-blocking probabilities in LEO satellite networks: The single-orbit case

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2002年第2期51卷 332-347页

作者： Zaim, AH Rouskas, GN Perros, HG N Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA

We study the problem of carrying voice calls over a low-earth-orbit satellite network and present an analytical model for computing call-blocking probabilities for a single orbit of a satellite constellation. We have devised a method to solve the corresponding Markov process efficiently for orbits of up to five satellites. For orbits consisting of a larger number of satellites, we have developed an approximate decomposition algorithm to compute the call-blocking probabilities by decomposing the system into smaller subsystems and iteratively solving each subsystem in isolation using the exact Markov process. Our approach can capture blocking due to handoffs for both satellite-fixed and earth-fixed constellations. Numerical results demonstrate that our method is accurate for a wide range of traffic patterns and for orbits with a number of satellites that is representative of commercial satellite systems.

关键词： call blocking probability decomposition algorithms handoffs low-earth-orbit (LEO) satellite networks

来源：评论

学校读者我要写书评

暂无评论

Minimization of a nondifferentiable convex function defined not everywhere

引用

OPTIMIZATION 2002年第6期51卷 819-840页

作者： Beer, K Gol'shtein, EG Sokolov, NA Russian Acad Sci Cent Econ & Math Inst Moscow 117418 Russia Tech Univ Chemnitz Fak Math D-09107 Chemnitz Germany

We examine an oracle-type method to minimize a convex function f over a convex polyhedron G. The method is an extension of the level-method to the case, when f is a not everywhere finite function, i.e., it may equal to +infinity at some points of G. An estimate of its efficiency is given, and some modifications of the method are mentioned. Finally, we indicate possible ways of its employment and report results of a numerical experiment.

关键词： nondifferentiable optimization cutting plane methods level methods decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

A path decomposition approach for computing blocking probabilities in wavelength-routing networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2000年第6期8卷 747-762页

作者： Zhu, YH Rouskas, GN Perros, HG N Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA N Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA

We study a class of circuit-switched wavelength-routing networks with fixed or alternate routing and with random wavelength allocation. We present an iterative path decomposition algorithm to evaluate accurately and efficiently the blocking performance of such networks with and without wavelength converters. Our iterative algorithm analyzes the original network by decomposing it into single-path subsystems. These subsystems are analyzed in isolation, and the individual results are appropriately combined to obtain a solution for the overall network, To analyze individual subsystems, we first construct an exact Markov process that captures the behavior of a path in terms of wavelength use. We also obtain an approximate Markov process which has a closed-form solution that can be computed efficiently for short paths, We then develop an iterative algorithm to analyze approximately arbitrarily long paths. The path decomposition approach naturally captures the correlation of both link loads and link blocking events, Our algorithm represents a simple and computationally efficient solution to the difficult problem of computing call-blocking probabilities in wavelength-routing networks. We also demonstrate how our analytical techniques can be applied to gain insight into the problem of converter placement in wavelength-routing networks.

关键词： call-blocking probability converter placement decomposition algorithms wavelength-division multiplexing wavelength-routing networks

来源：评论

学校读者我要写书评

暂无评论

A two-level queueing network model with blocking and non-blocking messages

引用

ANNALS OF OPERATIONS RESEARCH 2000年第1-4期93卷 357-372页

作者： Ramesh, S Perros, HG N Carolina State Univ Dept Comp Sci Raleigh NC 27607 USA N Carolina State Univ Ctr Adv Comp & Commun Raleigh NC 27607 USA

We analyze a novel two-level queueing network with blocking, consisting of N level-1 parallel queues linked to M level-2 parallel queues. The processing of a customer by a level-1 server requires additional services that are exclusively offered by level-2 servers. These level-2 servers are accessed through blocking and non-blocking messages issued by level-1 servers. If a blocking message is issued, the level-1 server gets blocked until the message is fully processed at the level-2 server. The queueing network is analyzed approximately using a decomposition method, which can be viewed as a generalization of the well-known two-node decomposition algorithm used to analyze tandem queueing networks with blocking. Numerical tests show that the algorithm has a good accuracy.

关键词： queueing networks with blocking decomposition algorithms BCMP theorem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：