共查询到20条相似文献,搜索用时 520 毫秒
1.
In this paper, we consider the global error bound for the generalized linear complementarity problem over a polyhedral cone (GLCP). Based on the new transformation of the problem, we establish its global error bound under milder conditions, which improves the result obtained by Sun and Wang (2009) for GLCP by weakening the assumption. 相似文献
2.
Hongchun Sun Yiju Wang Shengjie Li Min Sun 《Journal of Fixed Point Theory and Applications》2018,20(2):75
In this paper, we further consider the global error bound for the generalized linear complementarity problem over a polyhedral cone (GLCP). By introducing a new technique, we establish a sharper global error bound for the GLCP under weaker conditions, which greatly improve the existing error bounds for this problem. 相似文献
3.
We give a bound on the distance between an arbitrary point and the solution set of a monotone linear complementarity problem
in terms of a condition constant that depends on the problem data only and a residual function of the violations of the complementary
problem conditions by the point considered. When the point satisfies the linear inequalities of the complementarity problem,
the residual consists of the complementarity condition plus its square root. This latter term is essential and without it
the error bound cannot hold. We also show that another natural residual that has been employed to bound errors for strictly
monotone linear complementarity problems fails to bound errors for the monotone case considered here.
Sponsored by the United States Army under contract No. DAAG29-80-C-0041. This material is based on research sponsored by National
Foundation Grant DCR-8420963 and Air Force Office of Scientific Research Grant AFOSR-ISSA-85-00080. 相似文献
4.
A globally convergent approximately active search algorithm for solving mathematical programs with linear complementarity constraints 总被引:2,自引:0,他引:2
Summary. In this paper, we propose a new algorithm for solving mathematical programs with linear complementarity constraints. The algorithm uses a method of approximately active search and introduces the idea of acceptable descent face. The main advantage of the new algorithm is that it is globally convergent without requiring strong assumptions such as nondegeneracy or linear independence condition. Numerical results are presented to show the effectiveness of the algorithm.Mathematics Subject Classification (2000): 90C30, 90C33, 65K05This research is partially supported by City University of Hong Kong under its Strategic Research Grant #7001339 and the National Natural Science Foundation of China grant # 10171108 and # 70271014 相似文献
5.
X.-L. Luo C. T. Kelley L.-Z. Liao H. W. Tam 《Journal of Optimization Theory and Applications》2009,140(2):265-286
Rosenbrock methods are popular for solving a stiff initial-value problem of ordinary differential equations. One advantage
is that there is no need to solve a nonlinear equation at every iteration, as compared with other implicit methods such as
backward difference formulas or implicit Runge–Kutta methods. In this article, we introduce a trust-region technique to select
the time steps of a second-order Rosenbrock method for a special initial-value problem, namely, a gradient system obtained
from an unconstrained optimization problem. The technique is different from the local error approach. Both local and global
convergence properties of the new method for solving an equilibrium point of the gradient system are addressed. Finally, some
promising numerical results are also presented.
This research was supported in part by Grant 2007CB310604 from National Basic Research Program of China, and #DMS-0404537
from the United States National Science Foundation, and Grant #W911NF-05-1-0171 from the United States Army Research Office,
and the Research Grant Council of Hong Kong. 相似文献
6.
Liqun Qi Chen Ling Xiaojiao Tong Guanglu Zhou 《Computational Optimization and Applications》2009,42(1):1-30
This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first
reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system
by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The
feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this
method is established under some standard assumptions. Preliminary numerical results are reported.
Qi’s work is supported by the Hong Kong Research Grant Council.
Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168).
Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070)
and the Technology Grant of Hunan (06FJ3038).
Zhou’s work is supported by Australian Research Council. 相似文献
7.
Smoothing Trust Region Methods for Nonlinear Complementarity Problems with P
0-Functions 总被引:1,自引:0,他引:1
By using the Fischer–Burmeister function to reformulate the nonlinear complementarity problem (NCP) as a system of semismooth
equations and using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing trust
region algorithm for solving the NCP with P
0 functions. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under
a nonsingularity condition, local Q-superlinear/Q-quadratic convergence of the algorithm is established without the strict
complementarity condition.
This work was partially supported by the Research Grant Council of Hong Kong and the National Natural Science Foundation of
China (Grant 10171030). 相似文献
8.
Constrained Inverse Minimum Spanning Tree Problems under the Bottleneck-Type Hamming Distance 总被引:4,自引:0,他引:4
In this paper, we consider the inverse minimum spanning tree problem under the bottleneck-type Hamming distance, where the
weights of edges can be modified only within given intervals. We further consider the constrained case in which the total
modification cost cannot exceed a given upper bound. It is shown that these inverse problems can be transformed into a minimum
node cover problem on a bipartite graph, and we give a strongly polynomial time algorithm to solve this type of node cover
problems.
This work is supported by The National Natural Science Foundation of China (60021201), The Hong Kong Research Grant Council
under the grant CERG 9040883 (CITYU 103003), and the Doctoral Foundation of Hohai University (2005-02). 相似文献
9.
In this paper, we consider two types of inverse sorting problems. The first type is an inverse sorting problem by minimizing
the total weighted number of changes with bound constraints. We present an O(n
2) time algorithm to solve the problem. The second type is a partial inverse sorting problem and a variant of the partial inverse
sorting problem. We show that both the partial inverse sorting problem and the variant can be solved by a combination of a
sorting problem and an inverse sorting problem.
Supported by the Hong Kong Universities Grant Council (CERG CITYU 103105) and the National Key Research and Development Program
of China (2002CB312004) and the National Natural Science Foundation of China (700221001, 70425004). 相似文献
10.
An Inexact Newton Method Derived from Efficiency Analysis 总被引:1,自引:0,他引:1
We consider solving an unconstrained optimization problem by Newton-PCG like methods in which the preconditioned conjugate gradient method is applied to solve the Newton equations. The main question to be investigated is how efficient Newton-PCG like methods can be from theoretical point of view. An algorithmic model with several parameters is established. Furthermore, a lower bound of the efficiency measure of the algorithmic model is derived as a function of the parameters. By maximizing this lower bound function, the parameters are specified and therefore an implementable algorithm is obtained. The efficiency of the implementable algorithm is compared with Newtons method by theoretical analysis and numerical experiments. The results show that this algorithm is competitive.Mathematics Subject Classification: 90C30, 65K05.This work was supported by the National Science Foundation of China Grant No. 10371131, and Hong Kong Competitive Earmarked Research Grant CityU 1066/00P from Hong Kong University Grant Council 相似文献
11.
New improved error bounds for the linear complementarity problem 总被引:1,自引:0,他引:1
New local and global error bounds are given for both nonmonotone and monotone linear complementarity problems. Comparisons of various residuals used in these error bounds are given. A possible candidate for a best error bound emerges from our comparisons as the sum of two natural residuals.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801. 相似文献
12.
A new class of branching models, the general collision branching processes with two parameters, is considered in this paper.
For such models, it is necessary to evaluate the absorbing probabilities and mean extinction times for both absorbing states.
Regularity and uniqueness criteria are firstly established. Explicit expressions are then obtained for the extinction probability
vector, the mean extinction times and the conditional mean extinction times. The explosion behavior of these models is investigated
and an explicit expression for mean explosion time is established. The mean global holding time is also obtained. It is revealed
that these properties are substantially different between the super-explosive and sub-explosive cases.
This work was partially supported by National Natural Science Foundation of China (Grant No. 10771216), Research Grants Council
of Hong Kong (Grant No. HKU 7010/06P) and Scientific Research Foundation for Returned Overseas Chinese Scholars, State Education
Ministry of China (Grant No. [2007]1108) 相似文献
13.
In this paper, we present a power penalty function approach to the linear complementarity problem arising from pricing American
options. The problem is first reformulated as a variational inequality problem; the resulting variational inequality problem
is then transformed into a nonlinear parabolic partial differential equation (PDE) by adding a power penalty term. It is shown
that the solution to the penalized equation converges to that of the variational inequality problem with an arbitrary order.
This arbitrary-order convergence rate allows us to achieve the required accuracy of the solution with a small penalty parameter.
A numerical scheme for solving the penalized nonlinear PDE is also proposed. Numerical results are given to illustrate the
theoretical findings and to show the effectiveness and usefulness of the method.
This work was partially supported by a research grant from the University of Western Australia and the Research Grant Council
of Hong Kong, Grants PolyU BQ475 and PolyU BQ493. 相似文献
14.
Based on the recent theoretical results of Zhao and Li [Math. Oper. Res., 26 (2001), pp. 119—146], we present in this paper
a new path-following method for nonlinear P* complementarity problems. Different from most existing interior-point algorithms
that are based on the central path, this algorithm tracks the “regularized central path” which exists for any continuous P*
problem. It turns out that the algorithm is globally convergent for any P* problem provided that its solution set is nonempty.
By different choices of the parameters in the algorithm, the iterative sequence can approach to different types of points
of the solution set. Moreover, local superlinear convergence of this algorithm can also be achieved under certain conditions.
The research of the first author was supported by The National Natural Science Foundation of China under Grant No. 10201032
and Grant No. 70221001. The research of the second author was supported by Grant CUHK4214/01E, Research Grants Council, Hong
Kong.
An erratum to this article is available at . 相似文献
15.
According to the basic idea of classical yin-yang complementarity and modern dualcomplementarity, in a simple and unified
way some basic principles for linear coupled dynamic thermopiezoelectricity can be established systematically. An important
integral relation in terms of convolutions is given, which can be considered as the generalized principle of virtual work
in mechanics. Based on this relation, it is possible not only to obtain the principle of virtual work and the reciprocal theorem
in linear coupled dynamic thermopiezoelectricity, but also to derive systematically the complementary functionals for eleven-field,
nine-field, six-field and three-field simplified Gurtin-type variational principles. Furthermore, with this approach, the
intrinsic relationship among various principles can be explained clearly.
Project supported by the National Natural Science Foundation of China (Grant No. 19672074) and Research Grand Council of Hong
Kong, No.RGC97/98, HKUST 6055/97E. 相似文献
16.
J. S. Pang 《Journal of Optimization Theory and Applications》1986,49(1):107-134
In an earlier paper, the author has given some necessary and sufficient conditions for the convergence of iterative methods for solving the linear complementarity problem. These conditions may be viewed as global in the sense that they apply to the methods regardless of the constant vector in the linear complementarity problem. More precisely, the conditions characterize a certain class of matrices for which the iterative methods will converge, in a certain sense, to a solution of the linear complementarity problem for all constant vectors. In this paper, we improve on our previous results and establish necessary and sufficient conditions for the convergence of iterative methods for solving each individual linear complementarity problem with a fixed constant vector. Unlike the earlier paper, our present analysis applies only to the symmetric linear complementarity problem. Various applications to a strictly convex quadratic program are also given.The author gratefully acknowledges several stimulating conversations with Professor O. Mangasarian on the subject of this paper. He is also grateful to a referee, who has suggested Lemma 2.2 and the present (stronger) version of Theorem 2.1 as well as several other constructive comments.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571, sponsored by the United States Army under Contract No. DAAG29-80-C-0041, and was completed while the author was visiting the Mathematics Research Center at the University of Wisconsin, Madison, Wisconsin. 相似文献
17.
We introduce some sufficient conditions under which a generalized linear complementarity problem (GLCP) can be solved as a pure linear complementarity problem. We also establish that the GLCP is in general a NP-Hard problem.Support of this work has been provided by the Instituto Nacional de Investigação Cientifica de Portugal (INIC) under contract 89/EXA/5. 相似文献
18.
Exact Algorithm for Concave Knapsack Problems: Linear Underestimation and Partition Method 总被引:2,自引:0,他引:2
Integer programming problems with a concave cost function are often encountered in optimization models involving economics
of scale. In this paper, we propose an efficient exact algorithm for solving concave knapsack problems. The algorithm consists
of an iterative process between finding lower and upper bounds by linearly underestimating the objective function and performing
domain cut and partition by exploring the special structure of the problem. The lower bound is improved iteratively via cutting
and partitioning the domain. This iteration process converges to the optimality in a finite number of steps. Promising computational
results are reported for large-scale concave knapsack problems with up to 1200 integer variables. Comparison results with
other existing methods in the literature are also presented.
*Research supported by the National Natural Science Foundation of China under Grants 79970107 and 10271073,and the Research
Grants Council of Hong Kong under Grant CUHK 4214/01E. 相似文献
19.
We consider a class of quadratic programs with linear complementarity constraints (QPLCC) which belong to mathematical programs
with equilibrium constraints (MPEC). We investigate various stationary conditions and present new and strong necessary and
sufficient conditions for global and local optimality. Furthermore, we propose a Newton-like method to find an M-stationary
point in finite steps without MEPC linear independence constraint qualification.
The research of this author is partially supported by NSERC, and Research Grand Council of Hong Kong. 相似文献
20.
Error bounds for analytic systems and their applications 总被引:1,自引:0,他引:1
Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01. 相似文献