共查询到20条相似文献,搜索用时 31 毫秒
1.
Juan Carlos De los Reyes Sergio González Andrade 《Journal of Computational and Applied Mathematics》2010,235(1):11-32
This paper is devoted to the numerical simulation of two-dimensional stationary Bingham fluid flow by semismooth Newton methods. We analyze the modeling variational inequality of the second kind, considering both Dirichlet and stress-free boundary conditions. A family of Tikhonov regularized problems is proposed and the convergence of the regularized solutions to the original one is verified. By using Fenchel’s duality, optimality systems which characterize the original and regularized solutions are obtained. The regularized optimality systems are discretized using a finite element method with (cross-grid P1)-Q0 elements for the velocity and pressure, respectively. A semismooth Newton algorithm is proposed in order to solve the discretized optimality systems. Using an additional relaxation, a descent direction is constructed from each semismooth Newton iteration. Local superlinear convergence of the method is also proved. Finally, we perform numerical experiments in order to investigate the behavior and efficiency of the method. 相似文献
2.
We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC1) convex programming problem with fewer variables than the original one. The Karush–Kuhn–Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush–Kuhn–Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems. 相似文献
3.
In this paper, we investigate a class of nonlinear complementarity problems arising from the discretization of the free boundary problem, which was recently studied by Sun and Zeng [Z. Sun, J. Zeng, A monotone semismooth Newton type method for a class of complementarity problems, J. Comput. Appl. Math. 235 (5) (2011) 1261–1274]. We propose a new non-interior continuation algorithm for solving this class of problems, where the full-Newton step is used in each iteration. We show that the algorithm is globally convergent, where the iteration sequence of the variable converges monotonically. We also prove that the algorithm is globally linearly and locally superlinearly convergent without any additional assumption, and locally quadratically convergent under suitable assumptions. The preliminary numerical results demonstrate the effectiveness of the proposed algorithm. 相似文献
4.
We study convergence of a semismooth Newton method for generalized semi-infinite programming problems with convex lower level
problems where, using NCP functions, the upper and lower level Karush-Kuhn-Tucker conditions of the optimization problem are
reformulated as a semismooth system of equations. Nonsmoothness is caused by a possible violation of strict complementarity
slackness. We show that the standard regularity condition for convergence of the semismooth Newton method is satisfied under
natural assumptions for semi-infinite programs. In fact, under the Reduction Ansatz in the lower level and strong stability
in the reduced upper level problem this regularity condition is satisfied. In particular, we do not have to assume strict
complementary slackness in the upper level. Numerical examples from, among others, design centering and robust optimization
illustrate the performance of the method.
相似文献
5.
This paper concerns developing a numerical method of the Newton type to solve systems of nonlinear equations described by nonsmooth continuous functions. We propose and justify a new generalized Newton algorithm based on graphical derivatives, which have never been used to derive a Newton-type method for solving nonsmooth equations. Based on advanced techniques of variational analysis and generalized differentiation, we establish the well-posedness of the algorithm, its local superlinear convergence, and its global convergence of the Kantorovich type. Our convergence results hold with no semismoothness and Lipschitzian assumptions, which is illustrated by examples. The algorithm and main results obtained in the paper are compared with well-recognized semismooth and B-differentiable versions of Newton’s method for nonsmooth Lipschitzian equations. 相似文献
6.
《Numerical Functional Analysis & Optimization》2013,34(7-8):1013-1035
We present a unified framework for the design and convergence analysis of a class of algorithms based on approximate solution of proximal point subproblems. Our development further enhances the constructive approximation approach of the recently proposed hybrid projection–proximal and extragradient–proximal methods. Specifically, we introduce an even more flexible error tolerance criterion, as well as provide a unified view of these two algorithms. Our general method possesses global convergence and local (super)linear rate of convergence under standard assumptions, while using a constructive approximation criterion suitable for a number of specific implementations. For example, we show that close to a regular solution of a monotone system of semismooth equations, two Newton iterations are sufficient to solve the proximal subproblem within the required error tolerance. Such systems of equations arise naturally when reformulating the nonlinear complementarity problem. 相似文献
7.
Liqun Qi 《Journal of Global Optimization》2006,35(2):343-366
The Karush-Kuhn-Tucker (KKT) system of the variational inequality problem over a set defined by inequality and equality constraints
can be reformulated as a system of semismooth equations via an nonlinear complementarity problem (NCP) function. We give a
sufficient condition for boundedness of the level sets of the norm function of this system of semismooth equations when the
NCP function is metrically equivalent to the minimum function; and a sufficient and necessary condition when the NCP function
is the minimum function. Nonsingularity properties identified by Facchinei, Fischer and Kanzow, 1998, SIAM J. Optim. 8, 850–869, for the semismooth reformulation of the variational inequality problem via the Fischer-Burmeister function,
which is an irrational regular pseudo-smooth NCP function, hold for the reformulation based on other regular pseudo-smooth
NCP functions. We propose a new regular pseudo-smooth NCP function, which is piecewise linear-rational and metrically equivalent
to the minimum NCP function. When it is used to the generalized Newton method for solving the variational inequality problem,
an auxiliary step can be added to each iteration to reduce the value of the merit function by adjusting the Lagrangian multipliers
only.
This work is supported by the Research Grant Council of Hong Kong
This paper is dedicated to Alex Rubinov on the occasion of his 65th Birthday 相似文献
8.
We consider the application of the globalized semismooth Newton method to the solution of (the KKT conditions of) quasi variational inequalities. We show that the method is globally and locally superlinearly convergent for some important classes of quasi variational inequality problems. We report numerical results to illustrate the practical behavior of the method. 相似文献
9.
In this paper we consider optimal control problems subject to a semilinear elliptic state equation together with the control constraints 0≤u≤1 and ∫u=m. Optimality conditions for this problem are derived and reformulated as a nonlinear, nonsmooth equation which is solved using a semismooth Newton method. A regularization of the nonsmooth equation is necessary to obtain the superlinear convergence of the semismooth Newton method. We prove that the solutions of the regularized problems converge to a solution of the original problem and a path-following technique is used to ensure a constant decrease rate of the residual. We show that, in certain situations, the optimal controls take 0–1 values, which amounts to solving a topology optimization problem with volume constraint. 相似文献
10.
An implementable augmented Lagrange method for solving fixed point problems with coupled constraints
Li Wang Feng ShanLiwei Zhang 《Nonlinear Analysis: Theory, Methods & Applications》2011,74(5):1761-1768
An augmented Lagrange function method for solving fixed point problems with coupled constraints is studied, and a theorem of its global convergence is demonstrated. The semismooth Newton method is used to solve the inner problems for obtaining approximate solutions, and numerical results are reported to verify the effectiveness of the augmented Lagrange function method for solving three examples with more than 1000 variables. 相似文献
11.
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. 相似文献
12.
A generalized Newton method for absolute value equations associated with second order cones 总被引:1,自引:0,他引:1
Sheng-Long Hu 《Journal of Computational and Applied Mathematics》2011,235(5):1490-1501
In this paper, we introduce the absolute value equations associated with second order cones (SOCAVE in short), which is a generalization of the absolute value equations discussed recently in the literature. It is proved that the SOCAVE is equivalent to a class of second order cone linear complementarity problems (SOCLCP in short). In particular, we propose a generalized Newton method for solving the SOCAVE and show that the proposed method is globally linearly and locally quadratically convergent under suitable assumptions. We also report some preliminary numerical results of the proposed method for solving the SOCAVE and the SOCLCP, which show the efficiency of the proposed method. 相似文献
13.
Liu YangYanping Chen Xiaojiao TongChunlin Deng 《Applied mathematics and computation》2011,217(24):9855-9863
In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well. 相似文献
14.
Na Zhao 《Applied mathematics and computation》2010,217(7):3368-3378
Many optimization problems can be reformulated as a system of equations. One may use the generalized Newton method or the smoothing Newton method to solve the reformulated equations so that a solution of the original problem can be found. Such methods have been powerful tools to solve many optimization problems in the literature. In this paper, we propose a Newton-type algorithm for solving a class of monotone affine variational inequality problems (AVIPs for short). In the proposed algorithm, the techniques based on both the generalized Newton method and the smoothing Newton method are used. In particular, we show that the algorithm can find an exact solution of the AVIP in a finite number of iterations under an assumption that the solution set of the AVIP is nonempty. Preliminary numerical results are reported. 相似文献
15.
求解半光滑方程组的近似Newton法 总被引:1,自引:0,他引:1
赵曰堂 《应用数学与计算数学学报》2002,16(2):15-22
本文提出了求解半光滑方程组的近似Newton法,并证明了该算法的局部超线性收敛性。数值结果表明 该算法是有效的。 相似文献
16.
Convergence of Newton's method for convex best interpolation 总被引:7,自引:0,他引:7
Summary. In this paper, we consider the problem of finding a convex function which interpolates given points and has a minimal norm of the second derivative. This problem reduces to a system of equations involving semismooth functions. We study a Newton-type
method utilizing Clarke's generalized Jacobian and prove that its local convergence is superlinear. For a special choice of
a matrix in the generalized Jacobian, we obtain the Newton method proposed by Irvine et al. [17] and settle the question of
its convergence. By using a line search strategy, we present a global extension of the Newton method considered. The efficiency
of the proposed global strategy is confirmed with numerical experiments.
Received October 26, 1998 / Revised version received October 20, 1999 / Published online August 2, 2000 相似文献
17.
Exact penalties for variational inequalities with applications to nonlinear complementarity problems
Thiago A. de André Paulo J. S. Silva 《Computational Optimization and Applications》2010,47(3):401-429
In this paper, we present a new reformulation of the KKT system associated to a variational inequality as a semismooth equation.
The reformulation is derived from the concept of differentiable exact penalties for nonlinear programming. The best theoretical
results are presented for nonlinear complementarity problems, where simple, verifiable, conditions ensure that the penalty
is exact. We close the paper with some preliminary computational tests on the use of a semismooth Newton method to solve the
equation derived from the new reformulation. We also compare its performance with the Newton method applied to classical reformulations
based on the Fischer-Burmeister function and on the minimum. The new reformulation combines the best features of the classical
ones, being as easy to solve as the reformulation that uses the Fischer-Burmeister function while requiring as few Newton
steps as the one that is based on the minimum. 相似文献
18.
M. Hintermüller V. A. Kovtunenko K. Kunisch 《Numerical Methods for Partial Differential Equations》2005,21(3):586-610
A class of semismooth Newton methods for unilaterally constrained variational problems modeling cracks under a nonpenetration condition is introduced and investigated. On the continuous level, a penalization technique is applied that allows to argue generalized differentiability of the nonlinear mapping associated to its first‐order optimality characterization. It is shown that the corresponding semismooth Newton method converges locally superlinearly. For the discrete version of the problem, fast local as well as global and monotonous convergence of a discrete semismooth Newton method are proved. A comprehensive report on numerical tests for the two‐dimensional Lamé problem with three collinear cracks under the nonpenetration condition ends the article. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005 相似文献
19.
A feasible semismooth asymptotically Newton method for mixed complementarity problems 总被引:2,自引:0,他引:2
Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research
on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible
region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region.
As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods.
In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges
to the Newton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method,
which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior
to doing (curved) line searches.
As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration.
The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must
be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates
being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical
results are reported on all problems from the MCPLIB collection [8].
Received: December 1999 / Accepted: March 2002 Published online: September 5, 2002
RID="★"
ID="★" This work was supported in part by the Australian Research Council.
Key Words. mixed complementarity problems – semismooth equations – projected Newton method – convergence
AMS subject classifications. 90C33, 90C30, 65H10 相似文献
20.
We consider a class of stochastic linear complementarity problems (SLCPs) with finitely many realizations. In this paper we
reformulate this class of SLCPs as a constrained minimization (CM) problem. Then, we present a feasible semismooth Newton
method to solve this CM problem. Preliminary numerical results show that this CM reformulation may yield a solution with high
safety for SLCPs. 相似文献