共查询到20条相似文献,搜索用时 15 毫秒
1.
Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior
continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be
globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a
linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm,
we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For
non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature
in order to achieve global linear convergence results of the algorithms. 相似文献
2.
We propose a non-interior continuation algorithm for the solution of the linear
complementarity problem (LCP) with a P0 matrix. The proposed algorithm
differentiates itself from the current continuation algorithms by combining good global
convergence properties with good local convergence properties under unified conditions.
Specifically, it is shown that the proposed algorithm is globally convergent under an
assumption which may be satisfied even if the solution set of the LCP is unbounded.
Moreover, the algorithm is globally linearly and locally superlinearly convergent under
a nonsingularity assumption. If the matrix in the LCP is a P* matrix, then the
above results can be strengthened to include global linear and local quadratic
convergence under a strict complementary condition without the nonsingularity
assumption. 相似文献
3.
D. Sun 《Applied Mathematics and Optimization》1999,40(3):315-339
In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P
0
-function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution
set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic)
without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are
provided and further applications to other problems are discussed.
Accepted 25 March 1998 相似文献
4.
By using a smooth entropy function to approximate the non-smooth max-type function, a vertical linear complementarity problem
(VLCP) can be treated as a family of parameterized smooth equations. A Newton-type method with a testing procedure is proposed
to solve such a system. We show that under some milder than usual assumptions the proposed algorithm finds an exact solution
of VLCP in a finite number of iterations. Some computational results are included to illustrate the potential of this approach.
This author’s work was partially supported by the National Natural Science Foundation of China (Grant Nos. 10271002 and 10401038).
This author’s work was partially supported by the Scientific Research Foundation of Tianjin University for the Returned Overseas
Chinese Scholars and the Scientific Research Foundation of Liu Hui Center for Applied Mathematics, Nankai University-Tianjin
University. 相似文献
5.
基于Fischer-Burmeister函数,本文将半定规划(SDP)的中心路径条件转化为非线性方程组,进而用SDCP的非内点连续化方法求解之.证明了牛顿方向的存在性,迭代点列的有界性.在适当的假设条件下,得到算法的全局收敛性及局部二次收敛率.数值结果表明算法的有效性. 相似文献
6.
We propose a noninterior continuation method for the monotone linear complementarity problem (LCP) by modifying the Burke–Xu framework of the noninterior predictor-corrector path-following method (Refs. 1–2). The new method solves one system of linear equations and carries out only one line search at each iteration. It is shown to converge to the LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution. Our analysis of the continuation method is based on a broader class of the smooth functions introduced by Chen and Mangasarian (Ref. 3). 相似文献
7.
Solution of a General Linear Complementarity Problem Using Smooth Optimization and Its Application to Bilinear Programming and LCP 总被引:2,自引:0,他引:2
L. Fernandes A. Friedlander M. Guedes J. Júdice 《Applied Mathematics and Optimization》2001,43(1):1-19
This paper addresses a General Linear Complementarity Problem (GLCP) that has found applications in global optimization.
It is shown that a solution of the GLCP can be computed by finding a stationary point of a differentiable function over a
set defined by simple bounds on the variables. The application of this result to the solution of bilinear programs and LCPs
is discussed. Some computational evidence of its usefulness is included in the last part of the paper.
Accepted 28 June 1999. Online publication 4 December 2000. 相似文献
8.
本文对于P0函数非线性互补问题提出了一个基于Kanzow光滑函数的一步非内点连续方法,在适当的假设条件下,证明了方法的全局线性及局部二次收敛性.特别,在方法的全局线性收敛性的分析中,不需要假定非线性互补问题的函数的Jacobi阵是Lipschitz连续的.文献中为了得到非内点连续方法的全局线性收敛性,这一假定是被广泛使用的.本文提出的方法在每一次迭代只须解一个线性方程式组. 相似文献
9.
In this paper, a specific class of convex feasibility problems are considered and a non-interior continuation algorithm based on a smoothing function to solve this class of problems is introduced. The proposed algorithm solves at most one system of linear equations at each iteration. Under some weak assumptions, we show that the algorithm is globally linearly and locally quadratically convergent. Preliminary numerical results are also reported, which verify the favorable theoretical properties of the proposed algorithm. 相似文献
10.
通过将互补问题转化为一种带非负约束的极小化问题 ,给出了求解互补问题的一种序列二次规划方法 .该方法中每一个子问题都是可解的 ,迭代产生的序列是非负的 ,在适当的条件下 ,分别证明了算法的全局收敛性、局部超线收敛性以及局部二次收敛性 . 相似文献
11.
For exact Newton method for solving monotone semidefinite complementarity problems (SDCP), one needs to exactly solve a linear system of equations at each iteration. For problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a new inexact smoothing/continuation algorithm for solution of large-scale monotone SDCP. At each iteration the corresponding linear system of equations is solved only approximately. Under mild assumptions, the algorithm is shown to be both globally and superlinearly convergent. 相似文献
12.
Min Li 《Numerical Functional Analysis & Optimization》2013,34(3):310-322
An algorithm for solving nonlinear monotone equations is proposed, which combines a modified Liu-Storey conjugate gradient method with hyperplane projection method. Under mild conditions, the global convergence of the proposed method is established with a suitable line search method. The method can be applied to solve large-scale problems for its lower storage requirement. Numerical results indicate that our method is efficient. 相似文献
13.
D. Han 《Applied Mathematics and Optimization》2002,45(1):63-74
The alternating direction method is an attractive method for solving large-scale variational inequality problems whenever
the subproblems can be solved efficiently. However, the subproblems are still variational inequality problems, which are as
structurally difficult to solve as the original one. To overcome this disadvantage, in this paper we propose a new alternating
direction method for solving a class of nonlinear monotone variational inequality problems. In each iteration the method just
makes an orthogonal projection to a simple set and some function evaluations. We report some preliminary computational results
to illustrate the efficiency of the method.
Accepted 4 May 2001. Online publication 19 October, 2001. 相似文献
14.
基于光滑Fischer-Burmeister函数,本文给出一个新的求解二阶锥规划的非内部连续化算法.算法对初始点的选取没有任何限制,并且在每一步迭代只需求解一个线性方程组并进行一次线性搜索.在不需要满足严格互补条件下,证明了算法是全局收敛且是局部超线性收敛的.数值试验表明算法是有效的. 相似文献
15.
In this paper we propose a nonmonotone trust region algorithm for optimization with simple bound constraints. Under mild
conditions, we prove the global convergence of the algorithm. For the monotone case it is also proved that the correct active
set can be identified in a finite number of iterations if the strict complementarity slackness condition holds, and so the
proposed algorithm reduces finally to an unconstrained minimization method in a finite number of iterations, allowing a fast
asymptotic rate of convergence. Numerical experiments show that the method is efficient.
Accepted 5 September 2000. Online publication 4 December 2000. 相似文献
16.
17.
Solving a class of linear projection equations 总被引:7,自引:0,他引:7
Binsheng He 《Numerische Mathematik》1994,68(1):71-80
Summary. Many interesting and important constrained
optimization problems in mathematical programming can be translated into an
equivalent linear projection equation
Here,
is the orthogonal projection on some convex set
(e.g. )
and is a positive semidefinite
matrix.
This paper presents some new methods for solving a class of linear projection
equations. The search directions of these methods are straighforward
extensions of
the directions in traditional methods for unconstrained optimization.
Based on the idea of a projection and contraction method [7] we get a
simple step length rule and are able to obtain global linear
convergence.
Received April 19, 1993 / Revised version received February 9,
1994 相似文献
18.
Zhensheng Yu Yangchen Liu Xinyue Gan 《Numerical Functional Analysis & Optimization》2017,38(11):1458-1472
This paper presents a nonmonotone inexact Newton-type method for the extended linear complementarity problem (ELCP). We first reformulate the optimization system of the ELCP problem into a system of smoothed equations. Then we solve this system by a nonmonotone inexact Newton-type algorithm. The global convergence is obtained and numerical tests for some classes of ELCP include linear complementarity, horizontal linear complementarity, and generalized linear complementarity problems are also given to show the e?ciency of the proposed algorithm. 相似文献
19.
研究一类无限维非线性互补问题的光滑化牛顿法.借助于非线性互补函数,将无限维非线性互补问题转化为一个非光滑算子方程.构造光滑算子逼近非光滑算子,在光滑逼近算子满足方向可微相容性的条件下,证明了光滑化牛顿法具有超线性收敛性. 相似文献
20.
Based on the notion of the ε -subgradient, we present a unified technique to establish convergence properties of several methods for nonsmooth convex
minimization problems. Starting from the technical results, we obtain the global convergence of: (i) the variable metric proximal
methods presented by Bonnans, Gilbert, Lemaréchal, and Sagastizábal, (ii) some algorithms proposed by Correa and Lemaréchal,
and (iii) the proximal point algorithm given by Rockafellar. In particular, we prove that the Rockafellar—Todd phenomenon
does not occur for each of the above mentioned methods. Moreover, we explore the convergence rate of {||x
k
|| } and {f(x
k
) } when {x
k
} is unbounded and {f(x
k
) } is bounded for the non\-smooth minimization methods (i), (ii), and (iii).
Accepted 15 October 1996 相似文献