共查询到20条相似文献,搜索用时 718 毫秒
1.
本文给出新的NCP函数,这些函数是分段线性有理正则伪光滑的,且具有良好的性质.把这些NCP函数应用到解非线性优化问题的方法中.例如,把求解非线性约束优化问题的KKT点问题分别用QP-free方法,乘子法转化为解半光滑方程组或无约束优化问题.然后再考虑用非精确牛顿法或者拟牛顿法来解决该半光滑方程组或无约束优化问题.这个方法是可实现的,且具有全局收敛性.可以证明在一定假设条件下,该算法具有局部超线性收敛性. 相似文献
2.
This paper is concerned with numerical methods for solving a semi-infinite programming problem. We reformulate the equations and nonlinear complementarity conditions of the first order optimality condition of the problem into a system of semismooth equations. By using a perturbed Fischer–Burmeister function, we develop a smoothing Newton method for solving this system of semismooth equations. An advantage of the proposed method is that at each iteration, only a system of linear equations is solved. We prove that under standard assumptions, the iterate sequence generated by the smoothing Newton method converges superlinearly/quadratically. 相似文献
3.
A Smoothing Newton Method for Semi-Infinite Programming 总被引:5,自引:0,他引:5
This paper is concerned with numerical methods for solving a semi-infinite programming problem. We reformulate the equations and nonlinear complementarity conditions of the first order optimality condition of the problem into a system of semismooth equations. By using a perturbed Fischer–Burmeister function, we develop a smoothing Newton method for solving this system of semismooth equations. An advantage of the proposed method is that at each iteration, only a system of linear equations is solved. We prove that under standard assumptions, the iterate sequence generated by the smoothing Newton method converges superlinearly/quadratically. 相似文献
4.
在大数据时代,随着数据采集手段的不断提升,大规模复合凸优化问题大量的出现在包括统计数据分析,机器与统计学习以及信号与图像处理等应用中.本文针对大规模复合凸优化问题介绍了一类快速邻近点算法.在易计算的近似准则和较弱的平稳性条件下,本文给出了该算法的全局收敛与局部渐近超线性收敛结果.同时,我们设计了基于对偶原理的半光滑牛顿法来高效稳定求解邻近点算法所涉及的重要子问题.最后,本文还讨论了如何通过深入挖掘并利用复合凸优化问题中由非光滑正则函数所诱导的非光滑二阶信息来极大减少半光滑牛顿算法中求解牛顿线性系统所需的工作量,从而进一步加速邻近点算法. 相似文献
5.
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 相似文献
6.
7.
This paper will consider the problem of solving the nonlinear system of equations with block-triangular structure. A generalized block Newton method for semismooth sparse system is presented and a locally superlinear convergence is proved. Moreover, locally linear convergence of some parameterized Newton method is shown. 相似文献
8.
The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem (NEP),in which both the utility function and the strategy space of each player depend on the strategies chosen by all other players.This problem has been used to model various problems in applications.However,the convergent solution algorithms are extremely scare in the literature.In this paper,we present an incremental penalty method for the GNEP,and show that a solution of the GNEP can be found by solving a sequence of smooth NEPs.We then apply the semismooth Newton method with Armijo line search to solve latter problems and provide some results of numerical experiments to illustrate the proposed approach. 相似文献
9.
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. 相似文献
10.
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 相似文献
11.
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. 相似文献
12.
Yan Gao 《Journal of Applied Mathematics and Computing》1999,6(3):513-522
The Newton method and the quasi-Newton method for solving equations of smooth compositions of semismooth functions are proposed. The Q-superlinear convergence of the Newton method and the Q-linear convergence of the quasi-Newton method are proved. The present methods can be more easily implemented than previous ones for this class of nonsmooth equations. 相似文献
13.
Semismooth Newton method is an effective method for solving a nonsmooth equation, which arises from a reformulation of the
complementarity problem. Under appropriate conditions, we verify the monotone convergence of the method. We also present semismooth
Newton Schwarz iterative methods for the nonsmooth equation. Under suitable conditions, the methods exhibit monotone and superlinear
convergence properties. 相似文献
14.
J. C. De Los Reyes S. González Andrade 《Numerical Methods for Partial Differential Equations》2012,28(3):834-860
This article is devoted to the numerical simulation of time‐dependent convective Bingham flow in cavities. Motivated by a primal‐dual regularization of the stationary model, a family of regularized time‐dependent problems is introduced. Well posedness of the regularized problems is proved, and convergence of the regularized solutions to a solution of the original multiplier system is verified. For the numerical solution of each regularized multiplier system, a fully discrete approach is studied. A stable finite element approximation in space together with a second‐order backward differentiation formula for the time discretization are proposed. The discretization scheme yields a system of Newton differentiable nonlinear equations in each time step, for which a semismooth Newton algorithm is used. We present two numerical experiments to verify the main properties of the proposed approach. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011 相似文献
15.
M. M. Golishnikov A. F. Izmailov 《Computational Mathematics and Mathematical Physics》2006,46(8):1299-1319
The most important classes of Newton-type methods for solving constrained optimization problems are discussed. These are the sequential quadratic programming methods, active set methods, and semismooth Newton methods for Karush-Kuhn-Tucker systems. The emphasis is placed on the behavior of these methods and their special modifications in the case where assumptions concerning constraint qualifications are relaxed or altogether dropped. Applications to optimization problems with complementarity constraints are examined. 相似文献
16.
Marek J. ?mietański 《Numerical Algorithms》2009,50(4):401-415
In this paper, we consider two versions of the Newton-type method for solving a nonlinear equations with nondifferentiable
terms, which uses as iteration matrices, any matrix from B-differential of semismooth terms. Local and global convergence
theorems for the generalized Newton and inexact generalized Newton method are proved. Linear convergence of the algorithms
is obtained under very mild assumptions. The superlinear convergence holds under some conditions imposed on both terms of
equation. Some numerical results indicate that both algorithms works quite well in practice.
相似文献
17.
《Journal of Computational and Applied Mathematics》2002,138(1):127-150
We study the problem of minimizing a sum of Euclidean norms. This nonsmooth optimization problem arises in many different kinds of modern scientific applications. In this paper we first transform this problem and its dual problem into a system of strongly semismooth equations, and give some uniqueness theorems for this problem. We then present a primal–dual algorithm for this problem by solving this system of strongly semismooth equations. Preliminary numerical results are reported, which show that this primal–dual algorithm is very promising. 相似文献
18.
A mesh-independent, robust, and accurate multigrid scheme to solve a linear state-constrained
parabolic optimal control problem is presented. We first consider a Lavrentiev regularization of the
state-constrained optimization problem. Then, a multigrid scheme is designed for the numerical
solution of the regularized optimality system. Central to this scheme is the construction of an
iterative pointwise smoother which can be formulated as a local semismooth Newton iteration. Results
of numerical experiments and theoretical two-grid local Fourier analysis estimates demonstrate that
the proposed scheme is able to solve parabolic state-constrained optimality systems with textbook
multigrid efficiency. 相似文献
19.
A class of stochastic linear complementarity problems (SLCPs) with finitely many realizations is considered. We first formulate the problem as a new constrained minimization problem. Then, we propose a feasible semismooth Newton method which yields a stationary point of the constrained minimization problem. We study the condition for the level set of the objective function to be bounded. As a result, the condition for the solution set of the constrained minimization problem is obtained. The global and quadratic convergence of the proposed method is proved under certain assumptions. Preliminary numerical results show that this method yields a reasonable solution with high safety and within a small number of iterations. 相似文献
20.
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. 相似文献