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

A generalized dual phase-2 simplex algorithm

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2003年第1期149卷 1-16页

作者： Maros, I Univ London Imperial Coll Sci Technol & Med Dept Comp London SW7 2BZ England

Recently, the dual simplex method has attracted considerable interest. This is mostly due to its important role in solving mixed integer linear programming problems where dual feasible bases are readily available. Even more than that, it is a realistic alternative to the primal simplex method in many cases. Real world linear programming problems include all types of variables and constraints. This necessitates a version of the dual simplex algorithm that can handle all types of variables efficiently. The paper presents increasingly more capable dual algorithms that evolve into one which is based on the piecewise linear nature of the dual objective function. The distinguishing features of this method are: (i) in one iteration it can make progress equivalent to many traditional dual iterations, (ii) using proper data structures it can be implemented very efficiently so that an iteration requires hardly more work than the traditional pivot method, (iii) its effectiveness just increases if more upper bounded variables are present, (iv) it has inherently better numerical stability because it can create a large flexibility in finding a pivot element, (v) it can excel itself in coping with degeneracy as it can bypass dual degenerate vertices more easily than the traditional pivot procedures. The power of the method is demonstrated through examples. The performance on some real world problems is also presented. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： linear programming simplex method dual algorithm large scale optimization

来源：评论

学校读者我要写书评

暂无评论

A revised dual projective pivot algorithm for linear programming

引用

SIAM JOURNAL ON OPTIMIZATION 2005年第1期16卷 49-68页

作者： Pan, PQ Southeast Univ Dept Math Nanjing 210096 Peoples R China

We revise the dual projective pivot algorithm using sparse rectangular LU factors. In each iteration, the proposed algorithm solves at most three triangular systems, while simplex algorithms solve four. Instead of the classical basis, it uses a so-called pseudobasis ( a rectangular matrix having fewer columns than rows), thereby solving smaller linear systems with a potentially improved stability compared to simplex algorithms. Most importantly, it generates good search directions at a low cost. We report encouraging computational results on a set of 50 Netlib standard test problems as well as a set of 15 much larger real-world problems. A code named RDPPA 1.10 based on the proposed algorithm outperformed MINOS 5.51 significantly in terms of both iterations and run time. In particular, it appears that a high proportion of degenerate iterations need not imply many total iterations ( contradicting the common belief).

关键词： large-scale linear programming dual algorithm projection pivot pseudobasis deficient basis LU factorization

来源：评论

学校读者我要写书评

暂无评论

Perturbed Utility Stochastic Traffic Assignment

引用

TRANSPORTATION SCIENCE 2024年第4期58卷 876页

作者： Yao, Rui Fosgerau, Mogens Paulsen, Mads Rasmussen, Thomas Kjaer Ecole Polytech Fed Lausanne Sch Architecture Civil & Environm Engn CH-1015 Lausanne Switzerland Univ Copenhagen Dept Econ DK-1353 Copenhagen Denmark Tech Univ Denmark Dept Technol Management & Econ DK-2800 Lyngby Denmark

This paper develops a fast algorithm for computing the equilibrium assignment with the perturbed utility route choice (PURC) model. Without compromise, this allows the significant advantages of the PURC model to be used in large-scale applications. We formulate the PURC equilibrium assignment problem as a convex minimization problem and find a closed -form stochastic network loading expression that allows us to formulate the Lagrangian dual of the assignment problem as an unconstrained optimization problem. To solve this dual problem, we formulate a quasi -Newton accelerated gradient descent algorithm (qN-AGD*). Our numerical evidence shows that qN-AGD* clearly outperforms a conventional primal algorithm and a plain accelerated gradient descent algorithm. qN-AGD* is fast with a runtime that scales about linearly with the problem size, indicating that solving the perturbed utility assignment problem is feasible also with very large networks.

关键词： perturbed utility stochastic traffic assignment dual algorithm closed-form network loading network route choice

来源：评论

学校读者我要写书评

暂无评论

High-Dimensional Least-Squares with Perfect Positive Correlation

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2019年第4期36卷 1950016.1-1950016.16页

作者： Huang, Zhiyong Luo, Ziyan Xiu, Naihua Beijing Jiaotong Univ Dept Appl Math Beijing Peoples R China Beijing Jiaotong Univ State Key Lab Rail Traff Control & Safety Beijing Peoples R China

The least-squares is a common and important method in linear regression. However, it often leads to overfitting phenomenon as dealing with high-dimensional problems, and various regularization schemes regarding prior information for specific problems are studied to make up such a deficiency. In the sense of Kendall's tau from the community of nonparametric analysis, we establish a new model wherein the ordinary least-squares is equipped with perfect positive correlation constraint, sought to maintain the concordance of the rankings of the observations and the systematic components. By sorting the observations into an ascending order, we reduce the perfect positive correlation constraint into a linear inequality system. The resulting linearly constrained least-squares problem together with its dual problem is shown to be solvable. In particular, we introduce a mild assumption on the observations and the measurement matrix which rules out the zero vector from the optimal solution set. This indicates that our proposed model is statistically meaningful. To handle large-scale instances, we propose an efficient alternating direction method of multipliers (ADMM) to solve the proposed model from the dual perspective. The effectiveness of our model compared to ordinary least-squares is evaluated in terms of rank correlation coefficient between outputs and the systematic components, and the efficiency of our dual algorithm is demonstrated with the comparison to three efficient solvers via CVX in terms of computation time, solution accuracy and rank correlation coefficient.

关键词： High-dimensional linear regression least-squares perfect positive correlation dual algorithm

来源：评论

学校读者我要写书评

暂无评论

Reliability estimation and statistical inference under joint progressively Type-II right-censored sampling for certain lifetime distributions

引用

COMMUNICATIONS IN STATISTICS-SIMULATION AND COMPUTATION 2024年

作者： Lin, Chien-Tai Chen, Yen-Chou Yeh, Tzu-Chi Ng, Hon Keung Tony Tamkang Univ Dept Math New Taipei City Taiwan Bentley Univ Dept Math Sci Waltham MA USA

In this article, the parameter estimation of several commonly used two-parameter lifetime distributions, including the Weibull, inverse Gaussian, and Birnbaum-Saunders distributions, based on joint progressively Type-II right-censored sample is studied. Different numerical methods and algorithms are used to compute the maximum likelihood estimates of the unknown model parameters. These methods include the Newton-Raphson method, the stochastic expectation-maximization (SEM) algorithm, and the dual annealing (DA) algorithm. These estimation methods are compared in terms of accuracy (e.g. the bias and mean squared error), computational time and effort (e.g. the required number of iterations), the ability to obtain the largest value of the likelihood, and convergence issues by means of a Monte Carlo simulation study. Recommendations are made based on the simulated results. A real data set is analyzed for illustrative purposes. These methods are implemented in Python, and the computer programs are available from the authors upon request.

关键词： dual algorithm Maximum likelihood estimation Monte Carlo simulation Simulated annealing algorithm Stochastic EM algorithm

来源：评论

学校读者我要写书评

暂无评论

Voting-Based Multiagent Reinforcement Learning for Intelligent IoT

引用

IEEE INTERNET OF THINGS JOURNAL 2021年第4期8卷 2681-2693页

作者： Xu, Yue Deng, Zengde Wang, Mengdi Xu, Wenjun So, Anthony Man-Cho Cui, Shuguang Beijing Univ Posts & Telecommun Minist Educ Key Lab Universal Wireless Commun Beijing 100876 Peoples R China Chinese Univ Hong Kong Shenzhen Res Inst Big Data Shenzhen 518172 Peoples R China Chinese Univ Hong Kong Sch Sci & Engn Shenzhen 518172 Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Hong Kong Peoples R China Princeton Univ Dept Elect Engn Ctr Stat & Machine Learning Dept Operat Res & Financial Engn Princeton NJ 08544 USA Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Chinese Univ Hong Kong Future Network Intelligence Inst Shenzhen 518172 Peoples R China

The recent success of single-agent reinforcement learning (RL) in Internet of Things (IoT) systems motivates the study of multiagent RL (MARL), which is more challenging but more useful in large-scale IoT. In this article, we consider a voting-based MARL problem, in which the agents vote to make group decisions and the goal is to maximize the globally averaged returns. To this end, we formulate the MARL problem based on the linear programming form of the policy optimization problem and propose a primal-dual algorithm to obtain the optimal solution. We also propose a voting mechanism through which the distributed learning achieves the same sublinear convergence rate as centralized learning. In other words, the distributed decision making does not slow down the process of achieving global consensus on optimality. Finally, we verify the convergence of our proposed algorithm with numerical simulations and conduct case studies in practical multiagent IoT systems.

关键词： Convergence Internet of Things Optimization Collaboration Task analysis Learning (artificial intelligence) Games Multiagent reinforcement learning (MARL) primal– dual algorithm voting mechanism

来源：评论

学校读者我要写书评

暂无评论

A class of nonlinear Lagrangians: Theory and algorithm

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2008年第3期25卷 327-371页

作者： Zhang, Li-Wei Ren, Yong-Hong Wu, Yue Xiao, Xian-Tao Dalian Univ Technol Dept Appl Math Dalian 116024 Peoples R China Liaoning Normal Univ Sch Math Dalian 116029 Peoples R China Univ Southampton Sch Management Southampton SO17 1BJ Hants England

This paper establishes a theory framework of a class of nonlinear Lagrangians for solving nonlinear programming problems with inequality constraints. A set of conditions are proposed to guarantee the convergence of nonlinear Lagrangian algorithms, to analyze condition numbers of nonlinear Lagrangian Hessians as well as to develop the dual approaches. These conditions are satisfied by well-known nonlinear Lagrangians appearing in literature. The convergence theorem shows that the dual algorithm based on any nonlinear Lagrangian in the class is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions and the error bound solution, depending on the penalty parameter, is also established. The paper also develops the dual problems based on the proposed nonlinear Lagrangians, and the related duality theorem and saddle point theorem are demonstrated. Furthermore, it is shown that the condition numbers of Lagrangian Hessians at optimal solutions are proportional to the controlling penalty parameters. We report some numerical results obtained by using nonlinear Lagrangians.

关键词： nonconvex optimization nonlinear Lagrangian dual algorithm condition number dual function

来源：评论

学校读者我要写书评

暂无评论

A novel displacement constrained optimization approach for black and white structural topology designs under multiple load cases

引用

STRUCTURAL AND MULTIDISCIPLINARY OPTIMIZATION 2017年第4期56卷 865-884页

作者： Rong, Jian Hua Yu, Liaohong Rong, Xuan Pei Zhao, Zhi Jun Changsha Univ Sci & Technol Sch Automot & Mech Engn Changsha 410114 Hunan Peoples R China Coll Hunan Prov Key Lab Lightweight & Reliabil Technol Engn Vehic Changsha 410114 Hunan Peoples R China Yichun Univ Sch Phys Sci & Technol Yichun Jiangxi Peoples R China Changsha Univ Dept Civil Engn Changsha 410003 Hunan Peoples R China

The gray problem of displacement constrained topology volume minimization under multiple load cases still is an opening topic of research. A series of topologies with clear profiles generated from an optimization process are very beneficial to method engineering applications. In this paper, a novel displacement constrained optimization approach for black and white structural topology designs under multiple load cases, is proposed to obtain a series of topologies with clear profiles. Firstly, a distribution feature of constraint displacement derivatives is investigated. Secondly, an adaptive adjusting approach of design variable bounds is proposed, and an improved approximate model with varied constraint limits and a volume penalty objective function are constructed. Thirdly, an improved density-based optimization method is proposed for the displacement constrained topology volume minimization under multiple load cases. Finally, several examples are given to demonstrate that the results obtained by the proposed method provide a series of topologies with clear profiles during an optimization process. It is concluded from examples that the proposed method is effective and robust for generating an optimal topology.

关键词： Structural topology optimization Feasible domain adjustment Trust region Multiple constraints dual algorithm

来源：评论

学校读者我要写书评

暂无评论

A nonlinear Lagrangian based on Fischer-Burmeister NCP function

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第2期188卷 1344-1363页

作者： Ren, Yong-Hong Zhang, Li-Wei Xiao, Xian-Tao Liaoning Normal Univ Sch Math Dalian 116029 Peoples R China Dalian Univ Technol Dept Appl Math Dalian 116024 Peoples R China

This paper proposes a nonlinear Lagrangian Based on Fischer-Burmeister NCP function for solving nonlinear programming problems with inequality constraints. The convergence theorem shows that the sequence of points generated by this nonlinear Lagrange algorithm is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions, and the error bound of solution, depending on the penalty parameter, is also established. Moreover, the paper develops the dual approach associated with the proposed nonlinear Lagrangian, in which the related duality theorem is demonstrated. Furthermore, it is shown that the condition number of the nonlinear Lagrangian Hessian at the optimal solution is proportional to the controlling penalty parameter. Numerical results for solving several nonlinear programming problems are reported, showing that the new nonlinear Lagrangian is superior over other known nonlinear Lagrangians for solving some nonlinear programming problems. (c) 2006 Elsevier Inc. All rights reserved.

关键词： nonlinear Lagrangian Fischer-Burmeister NCP function augmented Lagrangian dual algorithm condition number dual function

来源：评论

学校读者我要写书评

暂无评论

An improved region-based model with local statistical features for image segmentation

引用

PATTERN RECOGNITION 2012年第4期45卷 1578-1590页

作者： Ge, Qi Xiao, Liang Zhang, Jun Wei, Zhi Hui Nanjing Univ Sci & Technol Sch Comp Nanjing 210094 Jiangsu Peoples R China Nanjing Univ Sci & Technol Sch Sci Nanjing 210094 Jiangsu Peoples R China

In this paper, we propose a new region-based active contour model (ACM) for image segmentation. In particular, this model utilizes an improved region fitting term to partition the regions of interests in images depending on the local statistics regarding the intensity and the magnitude of gradient in the neighborhood of a contour. By this improved region fitting term, images with noise, intensity non-uniformity, and low-contrast boundaries can be well segmented. Integrated with the duality theory and the anisotropic diffusion process based on structure tensor, a new regularization term is defined through the duality formulation to penalize the length of active contour. By this new regularization term, the structural information of images is utilized to improve the ability of capturing the geometric features such as corners and cusps. From a numerical point of view, we minimize the energy function of our model by an efficient dual algorithm, which avoids the instability and the non-differentiability of traditional numerical solutions, e.g. the gradient descent method. Experiments on medical and natural images demonstrate the advantages of the proposed model over other segmentation models in terms of both efficiency and accuracy. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Active contour model Image segmentation Improved regularization term Structure tensor Local statistics dual algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：