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

International Symposium on Computer Science and Computational Technology

作者： Wang, Guangbin Wen, Hao Tan, Fuping Qingdao Univ Sci & Technol Dept Math Qingdao 266043 Peoples R China Shanghai Univ Dept Math Shanghai 200444 Peoples R China

In this paper, we consider synchronous stationary and nonstationary multi-splitting Schwarz methods for solving the linear complementarity problems. Moreover, We establish two convergence theorems of the methods by us... 详细信息

ISBN: (纸本)9780769534985

关键词： Synchronous Multi-splitting Schwarz Method linear complementarity problems H-compatible splitting

来源：评论

学校读者我要写书评

暂无评论

Sign-solvable linear complementarity problems

引用

12th International Integer Programming and Combinatorial Optimization Conference

作者： Kakimura, Naonori Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Tokyo 1138656 Japan

ISBN: (纸本)9783540727910

This paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of the solutions is uniquely determined by the sign patterns of the given coefficients. We provide a characterization for sign-solvable LCPs such that the coefficient matrix has nonzero diagonals, which can be tested in polynomial time. This characterization leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. The algorithm runs in O(gamma) time, where gamma is the number of the nonzero coefficients.

关键词： Combinatorial matrix theory linear complementarity problems

来源：评论

学校读者我要写书评

暂无评论

A Predictor-Corrector Algorithm for P-*(kappa)-linear complementarity problems Based on a Specific Self-Regular Proximity Function

引用

ACTA MATHEMATICA VIETNAMICA 2016年第1期41卷 103-120页

作者： Kheirfam, B. Ahmadi, K. Azarbaijan Shahid Madani Univ Dept Math Tabriz Iran

First-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior point methods. In Peng et al. (SIAM J. Optim. 15(4): 1105-1127, 2005), based on a specific proximity function, a wide neighborhood of the central path is defined which matches the standard large neighborhood defined by the infinity norm. In this paper, we extend the predictor-corrector algorithm proposed for linear optimization in Peng et al. (SIAM J. Optim. 15(4): 1105-1127, 2005) to P-*(kappa)-linear complementarity problems. Our algorithm performs two kinds of steps. In corrector steps, we use the specific self-regular proximity function to compute the search directions. The predictor step is the same as the predictor step of standard predictor-corrector method in the interior point method literature. We prove that our predictor-corrector algorithm has an O ((1 + 2 kappa)root n log n log (x(0))(T)s(0)/is an element of) iteration bound, which is the best known iteration complexity for problems of this type.

关键词： Predictor-corrector algorithm Self-regular functions linear complementarity problems Polynomial complexity

来源：评论

学校读者我要写书评

暂无评论

Γ-robust linear complementarity problems with ellipsoidal uncertainty sets

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2022年第1期29卷 417-441页

作者： Krebs, Vanessa Mueller, Michael Schmidt, Martin Friedrich Alexander Univ Erlangen Nurnberg Discrete Optimizat Cauerstr 11 D-91058 Erlangen Germany Energie Campus Nurnberg Further Str 250 D-90429 Nurnberg Germany Trier Univ Dept Math Univ Ring 15 D-54296 Trier Germany

We study uncertain linear complementarity problems (LCPs), that is, problems in which the LCP vector q or the LCP matrix M may contain uncertain parameters. To this end, we use the concept of Gamma-robust optimization applied to the gap function formulation of the LCP. Thus, this work builds upon Krebs and Schmidt (2020). There, we studied Gamma-robustified LCPs for l(1)- and box-uncertainty sets, whereas we now focus on ellipsoidal uncertainty sets. For uncertainty in q or M, we derive conditions for the tractability of the robust counterparts. For these counterparts, we also give conditions for the existence and uniqueness of their solutions. Finally, a case study for the uncertain traffic equilibrium problem is considered, which illustrates the effects of the values of Gamma on the feasibility and quality of the respective robustified solutions.

关键词： robust optimization linear complementarity problems ellipsoidal uncertainty sets traffic equilibrium problems

来源：评论

学校读者我要写书评

暂无评论

The double-relaxation modulus-based matrix splitting iteration method for linear complementarity problems

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2023年 427卷

作者： Huang, Zhengge Cui, Jingjing Guangxi Minzu Univ Coll Math & Phys Ctr Appl Math Guangxi Nanning 530006 Peoples R China

For the large sparse linear complementarity problems (LCP), by adopting the relaxation and relaxation two-sweep techniques for the modulus-based matrix splitting (MMS) iteration method, we establish a double-relaxation two-sweep modulus-based matrix splitting (DRTMMS) iteration method. This new method contains some known ones developed recently. Some sufficient conditions for guaranteeing the convergence of the DRTMMS method are presented when the system matrices are positive definite matrices and H+-matrices, which generalize some existing results. And the parameter selection strategy of the DRTMMS iteration method is given. Besides, the convergence analyses of the DRTM accelerated overrelaxation (DRTMAOR) method are given. Finally, numerical experiments illustrate that the DRTMMS method is efficient and has better performance than several existing MMS-like methods, and outperforms the projected splitting methods in some cases.(c) 2023 Elsevier B.V. All rights reserved.

关键词： linear complementarity problems Modulus-based matrix splitting iteration method Double-relaxation Relaxation two-sweep strategy Relaxation technique Convergence

来源：评论

学校读者我要写书评

暂无评论

Γ-robust linear complementarity problems

引用

OPTIMIZATION METHODS & SOFTWARE 2022年第2期37卷 658-691页

作者： Krebs, Vanessa Schmidt, Martin Friedrich Alexander Univ Erlangen Nurnberg Discrete Optimizat Erlangen Germany Energie Campus Nurnberg Nurnberg Germany Trier Univ Dept Math Univ Ring 15 D-54296 Trier Germany

complementarity problems are often used to compute equilibria made up of specifically coordinated solutions of different optimization problems. Specific examples are game-theoretic settings like the bimatrix game or energy market models like for electricity or natural gas. While optimization under uncertainties is rather well-developed, the field of equilibrium models represented by complementarity problems under uncertainty - especially using the concepts of robust optimization - is still in its infancy. In this paper, we extend the theory of strictly robust linear complementarity problems (LCPs) to Gamma-robust settings, where existence of worst-case-hedged equilibria cannot be guaranteed. Thus, we study the minimization of the worst-case gap function of Gamma-robust counterparts of LCPs. For box and-norm uncertainty sets we derive tractable convex counterparts for monotone LCPs and study their feasibility as well as the existence and uniqueness of solutions. To this end, we consider uncertainties in the vector and in the matrix defining the LCP. We additionally study so-called rho-robust solutions, i.e. solutions of relaxed uncertain LCPs. Finally, we illustrate the Gamma-robust concept applied to LCPs in the light of the above mentioned classical examples of bimatrix games and market equilibrium modelling.

关键词： linear complementarity problems robust optimization optimization under uncertainty Gamma-robustness tractable counterparts

来源：评论

学校读者我要写书评

暂无评论

Quitting Games and linear complementarity problems

引用

MATHEMATICS OF OPERATIONS RESEARCH 2020年第2期45卷 434-454页

作者： Solan, Eilon Solan, Omri N. Tel Aviv Univ Sch Math Sci Tel Aviv 6997800 Israel

We prove that every multiplayer quitting game admits a sunspot epsilon-equilibrium for every epsilon> 0, that is, an e-equilibrium in an extended game in which the players observe a public signal at every stage. We also prove that, if a certain matrix that is derived from the payoffs in the game is not a Q-matrix in the sense of linear complementarity problems, then the game admits a uniform epsilon-equilibrium for every epsilon > 0.

关键词： stochastic games quitting games stopping games sunspot equilibrium linear complementarity problems Q-matrices

来源：评论

学校读者我要写书评

暂无评论

A Full Multigrid Method for linear complementarity problems arising from Elastic Normal Contact problems

引用

MATHEMATICAL MODELLING AND ANALYSIS 2014年第2期19卷 216-240页

作者： Zhao, Jing Vollebregt, Edwin A. H. Oosterlee, Cornelis W. Delft Univ Technol NL-2628 CD Delft Netherlands VORtech BV NL-2628 CD Delft Netherlands Ctr Math & Comp Sci NL-1090 GB Amsterdam Netherlands

This paper presents a full multigrid (FMG) technique, which combines a multigrid method, an active set algorithm and a nested iteration technique, to solve a linear complementarity problem (LCP) modeling elastic normal contact problems. The governing system in this LCP is derived from a Fredholm integral of the first kind, and its coefficient matrix is dense, symmetric and positive definite. One multigrid cycle is applied to solve this system approximately in each active set iteration. Moreover, this multigrid solver incorporates a special strategy to handle the complementarity conditions, including restricting both the defect and the contact area (active set) to the coarse grid, and setting all quantities outside contact to zero. The smoother is chosen by some analysis based on the eigenvectors of the iteration matrix. This method is applied to a Hertzian smooth contact and a rough surface contact problem.

关键词： full multigrid linear complementarity problems integral equation normal contact problems active set algorithm

来源：评论

学校读者我要写书评

暂无评论

A Penalty Branch-and-Bound Method for Mixed Binary linear complementarity problems

引用

INFORMS JOURNAL ON COMPUTING 2022年第6期34卷 3117-3133页

作者： De Santis, Marianna de Vries, Sven Schmidt, Martin Winkel, Lukas Sapienza Univ Roma Dipartimento Ingn Informat Automat & Gest Antonio I-00185 Rome Italy Trier Univ Dept Math D-54296 Trier Germany

linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations and also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well-studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, almost no tailored algorithms are known besides reformulations of the problem that allow us to apply general purpose mixed integer linear programming solvers. In this paper, we present, theoretically analyze, enhance, and test a novel branch-and-bound method for MILCPs. The main property of this method is that we do not "branch" on constraints as usual but by adding suitably chosen penalty terms to the objective function. By doing so, we can either provably compute an MILCP solution if one exists or compute an approximate solution that minimizes an infeasibility measure combining integrality and complementarity conditions. We enhance the method by MILCP-tailored valid inequalities, node selection strategies, branching rules, and warm-starting techniques. The resulting algorithm is shown to clearly outperform two benchmark approaches from the literature.

关键词： mixed-integer programming linear complementarity problems mixed-integer linear complementarity problems branch and bound penalty methods

来源：评论

学校读者我要写书评

暂无评论

A notion of equivalence for linear complementarity problems Applications to the design of nonsmooth bifurcations ⁎

引用

IFAC-PapersOnLine 2020年第2期53卷 5435-5440页

作者： Fernando Castaños Felix A. Miranda-Villatoro Alessio Franci Automatic Control Department Cinvestav-IPN. Av. IPN 2508 07360 CDMX Mexico Department of Engineering University of Cambridge. Trumpington Street CB2 1PZ Cambridge UK Department of Mathematics Universidad Nacional Autónoma de México Circuito Exterior S/N C.U. 04510 CDMX Mexico

Many systems of interest to control engineering can be modeled by linear complementarity problems. We introduce a new notion of equivalence between linear complementarity problems that sets the basis to translate the powerful tools of smooth bifurcation theory to this class of models. Leveraging this notion of equivalence, we introduce new tools to analyze, classify, and design nonsmooth bifurcations in linear complementarity problems and their interconnection.

关键词： linear complementarity problems bifurcations topological equivalence piecewise linear equations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：