共查询到20条相似文献,搜索用时 31 毫秒
1.
Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search 总被引:1,自引:0,他引:1
In this paper, we propose a smoothing algorithm for solving the monotone symmetric cone complementarity problems (SCCP for
short) with a nonmonotone line search. We show that the nonmonotone algorithm is globally convergent under an assumption that
the solution set of the problem concerned is nonempty. Such an assumption is weaker than those given in most existing algorithms
for solving optimization problems over symmetric cones. We also prove that the solution obtained by the algorithm is a maximally
complementary solution to the monotone SCCP under some assumptions.
This work was supported by National Natural Science Foundation of China (Grant Nos. 10571134, 10671010) and Natural Science
Foundation of Tianjin (Grant No. 07JCYBJC05200) 相似文献
2.
3.
In this paper, we present a predictor-corrector smoothing Newton method for solving nonlinear symmetric cone complementarity problems (SCCP) based on the symmetrically perturbed smoothing function. Under a mild assumption, the solution set of the problem concerned is just nonempty, we show that the proposed algorithm is globally and locally quadratic convergent. Also, the algorithm finds a maximally complementary solution to the SCCP. Numerical results for second order cone complementarity problems (SOCCP), a special case of SCCP, show that the proposed algorithm is effective. 相似文献
4.
In this paper, two nonmonotone Levenberg–Marquardt algorithms for unconstrained nonlinear least-square problems with zero or small residual are presented. These algorithms allow the sequence of objective function values to be nonmonotone, which accelerates the iteration progress, especially in the case where the objective function is ill-conditioned. Some global convergence properties of the proposed algorithms are proved under mild conditions which exclude the requirement for the positive definiteness of the approximate Hessian T(x). Some stronger global convergence properties and the local superlinear convergence of the first algorithm are also proved. Finally, a set of numerical results is reported which shows that the proposed algorithms are promising and superior to the monotone Levenberg–Marquardt algorithm according to the numbers of gradient and function evaluations. 相似文献
5.
Xiuyun Zheng Jiarong Shi Wei Yang Qingyan Yin 《Journal of Applied Mathematics and Computing》2017,54(1-2):277-295
Based on a new symmetrically perturbed smoothing function, the generalized nonlinear complementarity problem defined on a polyhedral cone is reformulated as a system of smoothing equations. Then we suggest a new nonmonotone derivative-free line search and combine it into the smoothing Broyden-like method. The proposed algorithm contains the usual monotone line search as a special case and can overcome the difficult of smoothing Newton methods in solving the smooth equations to some extent. Under mild conditions, we prove that the proposed algorithm has global and local superlinear convergence. Furthermore, the algorithm is locally quadratically convergent under suitable assumptions. Preliminary numerical results are also reported. 相似文献
6.
In this paper, we focus on solving a class of nonlinear complementarity problems with non-Lipschitzian functions. We first introduce a generalized class of smoothing functions for the plus function. By combining it with Robinson's normal equation, we reformulate the complementarity problem as a family of parameterized smoothing equations. Then, a smoothing Newton method combined with a new nonmonotone line search scheme is employed to compute a solution of the smoothing equations. The global and local superlinear convergence of the proposed method is proved under mild assumptions. Preliminary numerical results obtained applying the proposed approach to nonlinear complementarity problems arising in free boundary problems are reported. They show that the smoothing function and the nonmonotone line search scheme proposed in this paper are effective. 相似文献
7.
Ruijuan Liu 《Journal of Applied Mathematics and Computing》2017,55(1-2):79-97
Based on a regularized Chen–Harker–Kanzow–Smale (CHKS) smoothing function, we propose a new smoothing and regularization Newton method for solving the symmetric cone complementarity problem. By using the theory of Euclidean Jordan algebras, we establish the global and local quadratic convergence of the method on certain assumptions. The proposed method uses a nonmonotone line search technique which includes the usual monotone line search as a special case. In addition, our method treats both the smoothing parameter \(\mu \) and the regularization parameter \(\varepsilon \) as independent variables. Preliminary numerical results are reported which indicate that the proposed method is effective. 相似文献
8.
Chungen Shen Sven Leyffer Roger Fletcher 《Computational Optimization and Applications》2012,52(3):583-607
We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a standard, global g-filter for global convergence, and a local nonmonotone l-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we prove global and superlinear local convergence. A special feature of the proposed method is that it does not require second-order correction steps. We present preliminary numerical results comparing our implementation with a classical filter SQP method. 相似文献
9.
PSB (Powell-Symmetric-Broyden) algorithm is a very important algorithm and has been extensively used in trust region methods. However, there are few studies on the line search type PSB algorithm. The primary reason is that the direction generated by this class of algorithms is not necessarily a descent direction of the objective function. In this paper, by combining a nonmonotone line search technique with the PSB method, we propose a nonmonotone PSB algorithm for solving unconstrained optimization. Under proper conditions, we establish global convergence and superlinear convergence of the proposed algorithm. At the same time we verify the efficiency of the proposed algorithm by some numerical experiments. 相似文献
10.
Xiangsong Zhang Sanyang Liu Zhenhua Liu 《Nonlinear Analysis: Real World Applications》2011,12(1):731-740
In this paper, the second-order cone complementarity problem is studied. Based on the Fischer–Burmeister function with a perturbed parameter, which is also called smoothing parameter, a regularization smoothing Newton method is presented for solving the sequence of regularized problems of the second-order cone complementarity problem. Under proper conditions, the global convergence and local superlinear convergence of the proposed algorithm are obtained. Moreover, the local superlinear convergence is established without strict complementarity conditions. Preliminary numerical results suggest the effectiveness of the algorithm. 相似文献
11.
In this paper, a new hybrid method is proposed for solving nonlinear complementarity problems (NCP) with P
0 function. In the new method, we combine a smoothing nonmonotone trust region method based on a conic model and line search
techniques. We reformulate the NCP as a system of semismooth equations using the Fischer-Burmeister function. Using Kanzow’s
smooth approximation function to construct the smooth operator, we propose a smoothing nonmonotone trust region algorithm
of a conic model for solving the NCP with P
0 functions. This is different from the classical trust region methods, in that when a trial step is not accepted, the method
does not resolve the trust region subproblem but generates an iterative point whose steplength is defined by a line search.
We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity
condition, the superlinear convergence of the algorithm is established without a strict complementarity condition. 相似文献
12.
13.
A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization 总被引:1,自引:0,他引:1
This paper proposes a primal-dual interior point method for solving large scale nonlinearly constrained optimization problems. To solve large scale problems, we use a trust region method that uses second derivatives of functions for minimizing the barrier-penalty function instead of line search strategies. Global convergence of the proposed method is proved under suitable assumptions. By carefully controlling parameters in the algorithm, superlinear convergence of the iteration is also proved. A nonmonotone strategy is adopted to avoid the Maratos effect as in the nonmonotone SQP method by Yamashita and Yabe. The method is implemented and tested with a variety of problems given by Hock and Schittkowskis book and by CUTE. The results of our numerical experiment show that the given method is efficient for solving large scale nonlinearly constrained optimization problems.Acknowledgement The authors would like to thank anonymous referees for their valuable comments to improve the paper. 相似文献
14.
Hongchao Zhang 《Computational Optimization and Applications》2014,57(1):27-43
A new nonmonotone algorithm is proposed and analyzed for unconstrained nonlinear optimization. The nonmonotone techniques applied in this algorithm are based on the estimate sequence proposed by Nesterov (Introductory Lectures on Convex Optimization: A Basic Course, 2004) for convex optimization. Under proper assumptions, global convergence of this algorithm is established for minimizing general nonlinear objective function with Lipschitz continuous derivatives. For convex objective function, this algorithm maintains the optimal convergence rate of convex optimization. In numerical experiments, this algorithm is specified by employing safe-guarded nonlinear conjugate gradient search directions. Numerical results show the nonmonotone algorithm performs significantly better than the corresponding monotone algorithm for solving the unconstrained optimization problems in the CUTEr (Bongartz et al. in ACM Trans. Math. Softw. 21:123–160, 1995) library. 相似文献
15.
Ju-liangZhang Xiang-sunZhang Yong-meiSu 《应用数学学报(英文版)》2004,20(4):557-572
In this paper, we analyze the global and local convergence properties of two predictor-corrector smoothing methods, which are based on the framework of the method in [1], for monotone linear complementarity problems (LCPs). The difference between the algorithm in [1] and our algorithms is that the neighborhood of smoothing central path in our paper is different to that in [1]. In addition, the difference between Algorithm 2.1 and the algorithm in [1] exists in the calculation of the predictor step. Comparing with the results in [1],the global and local convergence of the two methods can be obtained under very mild conditions. The global convergence of the two methods do not need the boundness of the inverse of the Jacobian. The superlinear convergence of Algorithm 2.1‘ is obtained under the assumption of nonsingularity of generalized Jacobian of Φ(x,y) at the limit point and Algorithm 2.1 obtains superlinear convergence under the assumption of strict complementarity at the solution. The efficiency of the two methods is tested by numerical experiments. 相似文献
16.
17.
Non-Interior continuation methods for solving semidefinite complementarity problems 总被引:13,自引:0,他引:13
There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity
problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric
positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed
Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and
local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported.
Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002
RID="⋆"
ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273.
Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear
convergence 相似文献
18.
In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP. 相似文献
19.
In this article, unconstrained minimax problems are discussed, and a sequential quadratic programming (SQP) algorithm with a new nonmonotone linesearch is presented. At each iteration, a search direction of descent is obtained by solving a quadratic programming (QP). To circumvent the Maratos effect, a high-order correction direction is achieved by solving another QP and a new nonmonotone linesearch is performed. Under reasonable conditions, the global convergence and the rate of superlinear convergence are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm. 相似文献
20.
Jingyong Tang Guoping He Li Dong Liang Fang Jinchuan Zhou 《Applications of Mathematics》2013,58(2):223-247
In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising. 相似文献