A Smoothing Newton Method for Semi-Infinite Programming

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.     

A new smoothing Newton method for solving constrained nonlinear equations

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.     

Semismooth Newton Methods for Solving Semi-Infinite Programming Problems

In this paper we present some semismooth Newton methods for solving the semi-infinite programming problem. We first reformulate the equations and nonlinear complementarity conditions derived from the problem into a system of semismooth equations by using NCP functions. Under some conditions a solution of the system of semismooth equations is a solution of the problem. Then some semismooth Newton methods are proposed for solving this system of semismooth equations. These methods are globally and superlinearly convergent. Numerical results are also given.     

A partial proximal point algorithm for nuclear norm regularized matrix least squares problems

We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner subproblems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint non-degeneracy condition, together with the strong semi-smoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from low-rank approximations of transition matrices show that our algorithm is efficient and robust.     

A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

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 (SC¹${\text{SC}}^1$) 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.     

A generalized Jacobian based Newton method for semismooth block-triangular system of equations

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.     

求解广义纳什均衡问题的指数型惩罚函数方法

本文利用指数型惩罚函数部分地惩罚耦合约束,从而将广义纳什均衡问题(GNEP)的求解转化为求解一系列光滑的惩罚纳什均衡问题 (NEP)。我们证明了若光滑的惩罚NEP序列的解序列的聚点处EMFCQ成立,则此聚点是 GNEP的一个解。进一步,我们把惩罚 NEP的KKT条件转化为一个非光滑方程系统,然后应用带有 Armijo 线搜索的半光滑牛顿法来求解此系统。最后,数值结果表明我们的指数型惩罚函数方法是有效的。     

One-step smoothing Newton method for solving the mixed complementarity problem with a function

The mixed complementarity problem (denote by MCP(F)) can be reformulated as the solution of a smooth system of equations. In the paper, based on a perturbed mid function, we propose a new smoothing function, which has an important property, not satisfied by many other smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P₀ function are discussed. Then we presented a one-step smoothing Newton algorithm to solve the MCP with a P₀ function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the rate of convergence of the method is proved under some suitable assumptions.     

解非负约束图像去模糊问题的积极集方法

研究非负约束全变分图像去模糊问题,提出了一个基于增广拉格朗日方法的积极集方法,并证明了该方法在有限步内可求解,进一步推出该方法等价于解非光滑方程组的半光滑牛顿法.     

A feasible semismooth asymptotically Newton method for mixed complementarity problems

 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     

求解半光滑方程组的近似Newton法

本文提出了求解半光滑方程组的近似Newton法，并证明了该算法的局部超线性收敛性。数值结果表明 该算法是有效的。     

The semismooth approach for semi-infinite programming under the Reduction Ansatz

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.      

Smoothing Newton method for nonsmooth second-order cone complementarity problems with application to electric power markets

This paper is dedicated to solving a nonsmooth second-order cone complementarity problem, in which the mapping is assumed to be locally Lipschitz continuous, but not necessarily to be continuously differentiable everywhere. With the help of the vector-valued Fischer-Burmeister function associated with second-order cones, the nonsmooth second-order cone complementarity problem can be equivalently transformed into a system of nonsmooth equations. To deal with this reformulated nonsmooth system, we present an approximation function by smoothing the inner mapping and the outer Fischer-Burmeister function simultaneously. Different from traditional smoothing methods, the smoothing parameter introduced is treated as an independent variable. We give some conditions under which the Jacobian of the smoothing approximation function is guaranteed to be nonsingular. Based on these results, we propose a smoothing Newton method for solving the nonsmooth second-order cone complementarity problem and show that the proposed method achieves globally superlinear or quadratic convergence under suitable assumptions. Finally, we apply the smoothing Newton method to a network Nash-Cournot game in oligopolistic electric power markets and report some numerical results to demonstrate its effectiveness.

     

A nonmonotone smoothing Newton method for circular cone programming

The circular cone programming (CCP) problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of circular cones. In this paper, we study nondegeneracy and strict complementarity for the CCP, and present a nonmonotone smoothing Newton method for solving the CCP. We reformulate the CCP as a second-order cone programming (SOCP) problem using the algebraic relation between the circular cone and the second-order cone. Then based on a one parametric class of smoothing functions for the SOCP, a smoothing Newton method is developed for the CCP by adopting a new nonmonotone line search scheme. Without restrictions regarding its starting point, our algorithm solves one linear system of equations approximately and performs one line search at each iteration. Under mild assumptions, our algorithm is shown to possess global and local quadratic convergence properties. Some preliminary numerical results illustrate that our nonmonotone smoothing Newton method is promising for solving the CCP.     

Global and Finite Convergence of a Generalized Newton Method for Absolute Value Equations

We investigate an efficient method for solving the absolute value equation Ax−|x|=b when the interval matrix [A−I,A+I] is regular. A generalized Newton method which combines the semismooth and the smoothing Newton steps is proposed. We establish global and finite convergence of the method. Preliminary numerical results indicate that the generalized Newton method is promising.     

Smoothing Newton method for operator equations in Banach spaces

In this paper, the global and superlinear convergence of smoothing Newton method for solving nonsmooth operator equations in Banach spaces are shown. The feature of smoothing Newton method is to use a smooth function to approximate the nonsmooth mapping. Under suitable assumptions, we prove that the smoothing Newton method is superlinearly convergent. As an application, we use the smoothing Newton method to solve a constrained optimal control problem.     

Boundedness and Regularity Properties of Semismooth Reformulations of Variational Inequalities

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     

An iterative method for solving semismooth equations

In this paper, we combine trust region technique with line search technique to develop an iterative method for solving semismooth equations. At each iteration, a trust region subproblem is solved. The solution of the trust region subproblem provides a descent direction for the norm of a smoothing function. By using a backtracking line search, a steplength is determined. The proposed method shares advantages of trust region methods and line search methods. Under appropriate conditions, the proposed method is proved to be globally and superlinearly convergent. In particular, we show that after finitely many iterations, the unit step is always accepted and the method reduces to a smoothing Newton method.     

Pseudotransient Continuation for Solving Systems of Nonsmooth Equations with Inequality Constraints

This paper investigates a pseudotransient continuation algorithm for solving a system of nonsmooth equations with inequality constraints. We first transform the inequality constrained system of nonlinear equations to an augmented nonsmooth system, and then employ the pseudotransient continuation algorithm for solving the corresponding augmented nonsmooth system. The method gets its global convergence properties from the dynamics, and inherits its local convergence properties from the semismooth Newton method. Finally, we illustrate the behavior of our approach by some numerical experiments.     

Smoothing Newton-Like Method for the Solution of Nonlinear Systems of Equalities and Inequalities

In this paper, we present a smoothing Newton-like method for solving non-linear systems of equalities and inequalities. By using the so-called max function, we transfer the inequalities into a system of semismooth equalities. Then a smoothing Newton-like method is proposed for solving the reformulated system, which only needs to solve one system of linear equations and to perform one line search at each iteration. The global and local quadratic convergence are studied under appropriate assumptions. Numerical examples show that the new approach is effective.