共查询到20条相似文献,搜索用时 9 毫秒
1.
Comparison of Two Reformulation-Linearization Technique Based Linear Programming Relaxations for Polynomial Programming Problems 总被引:3,自引:0,他引:3
In this paper, we compare two strategies for constructing linear programmingrelaxations for polynomial programming problems using aReformulation-Linearization Technique (RLT). RLT involves an automaticreformulation of the problem via the addition of certain nonlinear impliedconstraints that are generated by using the products of the simple boundingrestrictions (among other products), and a subsequent linearization based onvariable redefinitions. We prove that applying RLT directly to the originalpolynomial program produces a bound that dominates in the sense of being atleast as tight as the value obtained when RLT is applied to the jointcollection of all equivalent quadratic problems that could be constructed byrecursively defining additional variables as suggested by Shor. 相似文献
2.
线性互补问题的一类新的带参数价值函数的阻尼牛顿法 总被引:1,自引:0,他引:1
本文给出了线性互补问题LCP(q ,M)的一类新的带参数光滑价值函数 ,基此价值函数提出了一种阻尼牛顿类算法 ,并证明了当M为P 矩阵时 ,该算法全局收敛且有限步终止 .通过数值实验说明了该算法高效可靠 .与互补问题的磨光方程组中所采用的带参数价值函数不同 ,这里的参数最终并不趋向于零 ,而是趋向于被称作解的乘子向量 (与凸非线性极小极大问题的Lagrange乘子完全一致 ) ,这一思想是本文作者首次提出来的 ,同时本文中所采用的阻尼牛顿类方法也有其独到之处 ,在互补问题的研究中有进一步发展的潜力 相似文献
3.
In this paper we develop a self-adaptive projection and contraction method for the linear complementarity problem (LCP). This method improves the practical performance of the modified projection and contraction method in [10] by adopting a self-adaptive technique. The global convergence of our new method is proved under mild assumptions. Our numerical tests clearly demonstrate the necessity and effectiveness of our proposed method. 相似文献
4.
Chenliang Li Jinping Zeng 《高等学校计算数学学报(英文版)》2006,15(4):289-298
In this paper we consider some synchronous and asynchronous multisplitting and Schwarz methods for solving the linear complementarity problems. We establish some convergence theorems of the methods by using the concept of M-splitting. 相似文献
5.
Jari Toivanen & Cornelis W. Oosterlee 《高等学校计算数学学报(英文版)》2012,5(1):85-98
We present an algebraic version of an iterative multigrid method for
obstacle problems, called projected algebraic multigrid (PAMG) here.
We show that classical algebraic multigrid algorithms can easily be
extended to deal with this kind of problem. This paves the way for
efficient multigrid solution of obstacle problems with partial
differential equations arising, for example, in financial engineering. 相似文献
6.
多值单调算子的隐补问题 总被引:4,自引:0,他引:4
郭伟平 《应用泛函分析学报》2003,5(3):271-275
在Banach空间中引入了多值算子的隐补问题和相补问题的新概念,并证明了多值单调算子隐补问题和相补问题解的存在性定理。 相似文献
7.
对称线性互补问题的乘性Schwarz算法 总被引:1,自引:0,他引:1
本文提出了求解对称性互补问题的乘性Schwarz算法,其中子问题用投影迭代方法求解.利用投影迭代算子的性质及投影迭代的收敛性,证明了算法产生的迭代点列的聚点为原互补问题的解,并在一定条件下,证明算法产生的迭代点列的聚点存在. 相似文献
8.
Lili Zhang 《计算数学(英文版)》2015,33(1):100-112
To reduce the communication among processors and improve the computing time for solving linear complementarity problems, we present a two-step modulus-based synchronous multisplitting iteration method and the corresponding symmetric modulus-based multisplitting relaxation methods. The convergence theorems are established when the system matrix is an $H_+$-matrix, which improve the existing convergence theory. Numerical results show that the symmetric modulus-based multisplitting relaxation methods are effective in actual implementation. 相似文献
9.
Pu-yan Nie 《应用数学学报(英文版)》2006,22(1):9-20
In this work, null space techniques are employed to tackle nonlinear complementarity problems (NCPs). NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm. 相似文献
10.
11.
The monotonicity of the linear complementarity problem (LCP) is discussed in this paper. Both
the monotone property about the single element of the solution and the monotone property
of the whole solution are presented. In order to illustrate the results, some corresponding
numerical experiments are provided. 相似文献
12.
For the nonlinear complementarity problem, we derive norm bounds for the error of an approximate solution, generalizing the known results for the linear case. Furthermore, we present a linear system with interval data, whose solution set contains the error of an approximate solution. We perform extensive numerical tests and compare the different approaches. 相似文献
13.
给出了该类问题的数学模型,其约束的特殊性表现在被指派的资源数量必须在给定的范围内,因而不同于一般非平衡指派问题;运用m进制运算规则将二维解矩阵转化为一维解向量,减少解组合的数量,据此用隐枚举法求得问题的最优解。通过对多个算例的求解,找出了该问题最优解的两个特点。这些特点可为求解大规模该问题的智能算法提供有益的帮助。 相似文献
14.
In this paper, we construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish
the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system.
The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the
problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of
the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly
applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and
that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge,
such properties have not appeared in the existing literature for smoothing-type algorithms.
This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science
Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese
Scholars, State Education Ministry. 相似文献
15.
We give new error bounds for the linear complementarity problem where the involved matrix is a P-matrix. Computation of rigorous
error bounds can be turned into a P-matrix linear interval system. Moreover, for the involved matrix being an H-matrix with
positive diagonals, an error bound can be found by solving a linear system of equations, which is sharper than the Mathias-Pang
error bound. Preliminary numerical results show that the proposed error bound is efficient for verifying accuracy of approximate
solutions.
This work is partly supported by a Grant-in-Aid from Japan Society for the Promotion of Science. 相似文献
16.
A. Hassouni A. Lahlou A. Lamghari 《Journal of Optimization Theory and Applications》2005,126(2):225-246
In this paper, we establish some existence results for linear complementarity problems on closed convex cones under generalized monotonicity assumptionsThe authors are grateful to the referees for detailed comments and suggestions on an early version of the paper 相似文献
17.
本文提出一个二阶锥线性互补问题的长步原始对偶内点法,搜索方向由一个一般的核函数来定义.如果给出初始的严格内点,可以得到本算法的复杂性为O((1+2k)llog(lμ0/ε)). 相似文献
18.
19.
The linear complementarity problem (LCP) belongs to the class of
-hard problems. Therefore, we cannot expect a polynomial time solution method for LCPs without requiring some special property
of the matrix of the problem. We show that the dual LCP can be solved in polynomial time if the matrix is row sufficient;
moreover, in this case, all feasible solutions are complementary. Furthermore, we present an existentially polytime (EP) theorem
for the dual LCP with arbitrary matrix.
The research of Tibor Illés and Marianna Nagy has been supported by the Hungarian National Research Fund OTKA T 049789 and
by the Hungarian Science and Technology Foundation TéT SLO-4/2005.
Tamàs Terlaky has been supported by an NSERC Discovery grant, MITACS and the Canada Research Chair program. 相似文献
20.
In this paper, a new notion of exceptional family of elements (EFE) for a pair of functions involved in the implicit complementarity problem (ICP) is introduced. Based upon this notion and the Leray–Schauder Alternative, a general alternative is obtained which gives more general existence theorems for the implicit complementarity problem. Finally, via the techniques of continuous selections, these existence theorems are extended to the multi-valued implicit complementarity problems (MIPS). 相似文献