共查询到20条相似文献,搜索用时 578 毫秒
1.
Analogous to the nonlinear complementarity problem and the semi-definite complementarity problem, a popular approach to solving the second-order cone complementarity problem (SOCCP) is to reformulate it as an unconstrained minimization of a certain merit function over Rn. In this paper, we present a descent method for solving the unconstrained minimization reformulation of the SOCCP which is based on the Fischer–Burmeister merit function (FBMF) associated with second-order cone [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Programming 104 (2005) 293–327], and prove its global convergence. Particularly, we compare the numerical performance of the method for the symmetric affine SOCCP generated randomly with the FBMF approach [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Programming 104 (2005) 293–327]. The comparison results indicate that, if a scaling strategy is imposed on the test problem, the descent method proposed is comparable with the merit function approach in the CPU time for solving test problems although the former may require more function evaluations. 相似文献
2.
Jein-Shan Chen 《Mathematical Methods of Operations Research》2006,64(3):495-519
Recently Tseng (Math Program 83:159–185, 1998) extended a class of merit functions, proposed by Luo and Tseng (A new class of merit functions for the nonlinear complementarity problem, in Complementarity and Variational Problems: State of the Art, pp. 204–225, 1997), for the nonlinear complementarity problem (NCP) to the semidefinite complementarity problem (SDCP) and showed several related properties. In this paper, we extend this class of merit functions to the second-order cone complementarity problem (SOCCP) and show analogous properties as in NCP and SDCP cases. In addition, we study another class of merit functions which are based on a slight modification of the aforementioned class of merit functions. Both classes of merit functions provide an error bound for the SOCCP and have bounded level sets.Member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work is partially supported by National Science Council of Taiwan. 相似文献
3.
We investigate a one-parametric class of merit functions for the second-order cone complementarity problem (SOCCP) which is
closely related to the popular Fischer–Burmeister (FB) merit function and natural residual merit function. In fact, it will
reduce to the FB merit function if the involved parameter τ equals 2, whereas as τ tends to zero, its limit will become a multiple of the natural residual merit function. In this paper, we show that this
class of merit functions enjoys several favorable properties as the FB merit function holds, for example, the smoothness.
These properties play an important role in the reformulation method of an unconstrained minimization or a nonsmooth system
of equations for the SOCCP. Numerical results are reported for some convex second-order cone programs (SOCPs) by solving the
unconstrained minimization reformulation of the KKT optimality conditions, which indicate that the FB merit function is not
the best. For the sparse linear SOCPs, the merit function corresponding to τ=2.5 or 3 works better than the FB merit function, whereas for the dense convex SOCPs, the merit function with τ=0.1, 0.5 or 1.0 seems to have better numerical performance. 相似文献
4.
《Optimization》2012,61(8):1173-1197
We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the Fischer–Burmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function ψFB as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan P-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by Chen and Tseng (An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104(2005), pp. 293–327), which confirm the theoretical results and the effectiveness of the algorithm. 相似文献
5.
6.
Juhe Sun 《Numerical Functional Analysis & Optimization》2013,34(4):387-413
In this article, we extend two classes of merit functions for the second-order complementarity problem (SOCP) to infinite-dimensional SOCP. These two classes of merit functions include several popular merit functions, which are used in nonlinear complementarity problem, (NCP)/(SDCP) semidefinite complementarity problem, and SOCP, as special cases. We give conditions under which the infinite-dimensional SOCP has a unique solution and show that all these merit functions provide an error bound for infinite-dimensional SOCP and have bounded level sets. These results are very useful for designing solution methods for infinite-dimensional SOCP. 相似文献
7.
Shaohua Pan Jein-Shan Chen Sangho Kum Yongdo Lim 《Computational Optimization and Applications》2011,49(3):457-491
In this paper, we study the properties of the penalized Fischer-Burmeister (FB) second-order cone (SOC) complementarity function.
We show that the function possesses similar desirable properties of the FB SOC complementarity function for local convergence;
for example, with the function the second-order cone complementarity problem (SOCCP) can be reformulated as a (strongly) semismooth
system of equations, and the corresponding nonsmooth Newton method has local quadratic convergence without strict complementarity
of solutions. In addition, the penalized FB merit function has bounded level sets under a rather weak condition which can
be satisfied by strictly feasible monotone SOCCPs or SOCCPs with the Cartesian R
01-property, although it is not continuously differentiable. Numerical results are included to illustrate the theoretical considerations. 相似文献
8.
Nan LuZheng-Hai Huang 《Journal of Computational and Applied Mathematics》2011,235(8):2270-2276
In this paper, we first investigate the invertibility of a class of matrices. Based on the obtained results, we then discuss the solvability of Newton equations appearing in the smoothing-type algorithm for solving the second-order cone complementarity problem (SOCCP). A condition ensuring the solvability of such a system of Newton equations is given. In addition, our results also show that the assumption that the Jacobian matrix of the function involved in the SOCCP is a P0-matrix is not enough for ensuring the solvability of such a system of Newton equations, which is different from the one of smoothing-type algorithms for solving many traditional optimization problems in ℜn. 相似文献
9.
In this paper, we present a detailed investigation for the properties of a one-parametric class of SOC complementarity functions,
which include the globally Lipschitz continuity, strong semismoothness, and the characterization of their B-subdifferential.
Moreover, for the merit functions induced by them for the second-order cone complementarity problem (SOCCP), we provide a
condition for each stationary point to be a solution of the SOCCP and establish the boundedness of their level sets, by exploiting
Cartesian P-properties. We also propose a semismooth Newton type method based on the reformulation of the nonsmooth system of equations
involving the class of SOC complementarity functions. The global and superlinear convergence results are obtained, and among
others, the superlinear convergence is established under strict complementarity. Preliminary numerical results are reported
for DIMACS second-order cone programs, which confirm the favorable theoretical properties of the method. 相似文献
10.
Yungyen Chiang Shaohua Pan Jein-Shan Chen 《Journal of Mathematical Analysis and Applications》2011,383(1):159-178
We introduce the Jordan product associated with the second-order cone K into the real Hilbert space H, and then define a one-parametric class of complementarity functions Φt on H×H with the parameter t∈[0,2). We show that the squared norm of Φt with t∈(0,2) is a continuously F(réchet)-differentiable merit function. By this, the second-order cone complementarity problem (SOCCP) in H can be converted into an unconstrained smooth minimization problem involving this class of merit functions, and furthermore, under the monotonicity assumption, every stationary point of this minimization problem is shown to be a solution of the SOCCP. 相似文献
11.
Xin-He Miao Yu-Lin Chang Jein-Shan Chen 《Computational Optimization and Applications》2017,67(1):155-173
Merit function approach is a popular method to deal with complementarity problems, in which the complementarity problem is recast as an unconstrained minimization via merit function or complementarity function. In this paper, for the complementarity problem associated with p-order cone, which is a type of nonsymmetric cone complementarity problem, we show the readers how to construct merit functions for solving p-order cone complementarity problem. In addition, we study the conditions under which the level sets of the corresponding merit functions are bounded, and we also assert that these merit functions provide an error bound for the p-order cone complementarity problem. These results build up a theoretical basis for the merit method for solving p-order cone complementarity problem. 相似文献
12.
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. 相似文献
13.
Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem 总被引:3,自引:0,他引:3
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. 相似文献
14.
《Optimization》2012,61(5):661-676
In this article, we show that a one-parametric class of SOC merit functions has a Lipschitz continuous gradient; and moreover, the Lipschitz constant is related to the parameter in this class of SOC merit functions. This fact will lay a building block when the merit function approach as well as the Newton-type method are employed for solving the second-order cone complementarity problem with this class of merit functions. 相似文献
15.
In this paper, we extend the one-parametric class of merit functions proposed by Kanzow and Kleinmichel [C. Kanzow, H. Kleinmichel, A new class of semismooth Newton-type methods for nonlinear complementarity problems, Comput. Optim. Appl. 11 (1998) 227-251] for the nonnegative orthant complementarity problem to the general symmetric cone complementarity problem (SCCP). We show that the class of merit functions is continuously differentiable everywhere and has a globally Lipschitz continuous gradient mapping. From this, we particularly obtain the smoothness of the Fischer-Burmeister merit function associated with symmetric cones and the Lipschitz continuity of its gradient. In addition, we also consider a regularized formulation for the class of merit functions which is actually an extension of one of the NCP function classes studied by [C. Kanzow, Y. Yamashita, M. Fukushima, New NCP functions and their properties, J. Optim. Theory Appl. 97 (1997) 115-135] to the SCCP. By exploiting the Cartesian P-properties for a nonlinear transformation, we show that the class of regularized merit functions provides a global error bound for the solution of the SCCP, and moreover, has bounded level sets under a rather weak condition which can be satisfied by the monotone SCCP with a strictly feasible point or the SCCP with the joint Cartesian R02-property. All of these results generalize some recent important works in [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104 (2005) 293-327; C.-K. Sim, J. Sun, D. Ralph, A note on the Lipschitz continuity of the gradient of the squared norm of the matrix-valued Fischer-Burmeister function, Math. Program. 107 (2006) 547-553; P. Tseng, Merit function for semidefinite complementarity problems, Math. Program. 83 (1998) 159-185] under a unified framework. 相似文献
16.
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. 相似文献
17.
For the nonlinear complementarity problem (NCP), Chen et al. (Math. Program., 88:211–216, 2000) proposed a penalized Fischer-Burmeister (FB) function that has most desirable properties among complementarity functions (C-functions). Motivated by their work, the authors showed
(Kum and Lim in Penalized Complementarity Functions on Symmetric Cones, submitted, 2009) that this function naturally extends to a C-function for the symmetric cone complementarity problem (SCCP). In this note, we show that the main coercivity property of this function for NCP also extends to the SCCP. The proof
uses a new trace inequality on Euclidean Jordan algebras. We also show that the penalized FB function is strongly semismooth
in the case of a semidefinite cone and a second-order cone.
This work was supported by the Korea Research Foundation Grant KRF-2008-314-C00039. 相似文献
18.
《Optimization》2012,61(9):1935-1955
The second-order cone complementarity problem (denoted by SOCCP) can be effectively solved by smoothing-type algorithms, which in general are designed based on some monotone line search. In this paper, based on a new smoothing function of the Fischer–Burmeister function, we propose a smoothing-type algorithm for solving the SOCCP. The proposed algorithm uses a new nonmonotone line search scheme, which contains the usual monotone line search as a special case. Under suitable assumptions, we show that the proposed algorithm is globally and locally quadratically convergent. Some numerical results are reported which indicate the effectiveness of the proposed algorithm. 相似文献
19.
Yasushi Narushima Nobuko Sagara Hideho Ogasawara 《Journal of Optimization Theory and Applications》2011,149(1):79-101
The second-order cone complementarity problem (SOCCP) is an important class of problems containing a lot of optimization problems.
The SOCCP can be transformed into a system of nonsmooth equations. To solve this nonsmooth system, smoothing techniques are
often used. Fukushima, Luo and Tseng (SIAM J. Optim. 12:436–460, 2001) studied concrete theories and properties of smoothing functions for the SOCCP. Recently, a practical computational method
using the smoothed natural residual function to solve the SOCCP was given by Chen, Sun and Sun (Comput. Optim. Appl. 25:39–56,
2003). In the present paper, we propose an algorithm to solve the SOCCP by using the smoothed Fischer-Burmeister function. Some
preliminary numerical results are given. 相似文献
20.
《Journal of Computational and Applied Mathematics》2005,175(2):335-353
The affine second-order cone complementarity problem (SOCCP) is a wide class of problems that contains the linear complementarity problem (LCP) as a special case. The purpose of this paper is to propose an iterative method for the symmetric affine SOCCP that is based on the idea of matrix splitting. Matrix-splitting methods have originally been developed for the solution of the system of linear equations and have subsequently been extended to the LCP and the affine variational inequality problem. In this paper, we first give conditions under which the matrix-splitting method converges to a solution of the affine SOCCP. We then present, as a particular realization of the matrix-splitting method, the block successive overrelaxation (SOR) method for the affine SOCCP involving a positive definite matrix, and propose an efficient method for solving subproblems. Finally, we report some numerical results with the proposed algorithm, where promising results are obtained especially for problems with sparse matrices. 相似文献