A new smoothing and regularization Newton method for <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-NCP

The nonlinear complementarity problem (denoted by NCP(F)) can be reformulated as the solution of a nonsmooth system of equations. In this paper, we propose a new smoothing and regularization Newton method for solving nonlinear complementarity problem with P ₀-function (P ₀-NCP). Without requiring strict complementarity assumption at the P ₀-NCP solution, the proposed algorithm is proved to be convergent globally and superlinearly under suitable assumptions. Furthermore, the algorithm has local quadratic convergence under mild conditions. Numerical experiments indicate that the proposed method is quite effective. In addition, in this paper, the regularization parameter ε in our algorithm is viewed as an independent variable, hence, our algorithm seems to be simpler and more easily implemented compared to many previous methods.     

Finite termination of a Newton-type algorithm for a class of affine variational inequality problems

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.     

An Affine Scaling Interior Trust Region Method via Optimal Path for Solving Monotone Variational Inequality Problem with Linear Constraints

Based on a differentiable merit function proposed by Taji et al. in ＂Math. Prog. Stud., 58, 1993, 369-383＂, the authors propose an affine scaling interior trust region strategy via optimal path to modify Newton method for the strictly monotone variational inequality problem subject to linear equality and inequality constraints. By using the eigensystem decomposition and affine scaling mapping, the authors form an affine scaling optimal curvilinear path very easily in order to approximately solve the trust region subproblem. Theoretical analysis is given which shows that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions.     

仿射变换内点信赖域类方法解单调变分不等式问题

基于Taji引入的一类可微的简单边界约束的严格单调变分不等式问题的势函数,本文提出了仿射变换内点信赖域类修正牛顿法.进一步,作者不仅从理论上证明了该算法的整体收敛性,并且在合理的假设条件下,给出了算法具有局部二次收敛速率.     

On the <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> affine isoperimetric inequalities

We obtain an isoperimetric inequality which estimate the affine invariant p-surface area measure on convex bodies. We also establish the reverse version of L _p -Petty projection inequality and an affine isoperimetric inequality of Γ_− p K.     

Codimensions of Newton strata for <Emphasis Type="Italic">SL</Emphasis><Subscript>3</Subscript>(<Emphasis Type="Italic">F</Emphasis>) in the Iwahori case

We study the Newton stratification on SL ₃(F), where F is a Laurent power series field. We provide a formula for the codimensions of the Newton strata inside each component of the affine Bruhat decomposition on SL ₃(F). These calculations are related to the study of certain affine Deligne–Lusztig varieties. In particular, we describe a method for determining which of these varieties is non-empty in the case of SL ₃(F).     

A TRUST REGION-TYPE METHOD FOR SOLVINGMONOTONE VARIATIONAL INEQUALITY

1.IntroductionLetSbeanonemptyclosedconvexsubsetofR"andletF:R"-R"beacontinuousmapping.ThevariatiollalillequalityproblemFindx*6Ssuchthat(F(x*),x--x*)20forallxeS(VIP)iswidelyusedtostudyvariousequilibriummodelsarisingilleconomic,operatiollsresearch,transportatiollandregionalsciellces[2'3I?where(.,.)dellotestheinnerproductinR".Manyiterativemethodsfor(VIP)havebeendeveloped,forexample,projectionmethods[7ts],thenonlinearJacobimethod[5],thesuccessiveoverrelaxation.ethod[9]andgeneralizedgradient.…     

New projection-type methods for monotone LCP with finite termination

Summary. In this paper we establish two new projection-type methods for the solution of monotone linear complementarity problem (LCP). The methods are a combination of the extragradient method and the Newton method, in which the active set strategy is used and only one linear system of equations with lower dimension is solved at each iteration. It is shown that under the assumption of monotonicity, these two methods are globally and linearly convergent. Furthermore, under a nondegeneracy condition they have a finite termination property. At last, the methods are extended to solving monotone affine variational inequality problem. Received October 10, 2000 / Revised version received May 22, 2001 / Published online October 17, 2001     

盒子型区域上变分不等式的一个光滑牛顿法(英文)

The box constrained variational inequality problem can be reformulated as a nonsmooth equation by using median operator.In this paper,we present a smoothing Newton method for solving the box constrained variational inequality problem based on a new smoothing approximation function.The proposed algorithm is proved to be well defined and convergent globally under weaker conditions.     

求解不可微箱约束变分不等式的下降算法

1 引 论 设X(?)Rn是非空闭集,F:Rn→Rn连续映射,变分不等式问题VI(X,F)是指:求x∈X,使 F(x)T(y-x)≥0,　 (?)y∈X,(1)记指标集N=(1,2,…,n},当 X=[a,b]≡{x∈Rn|a≤xi≤bi,i∈N},(2)其中a={a1,a2,…,an}T,b={b1,b2,…,bn}T∈Rn时,VI(X,F)化为箱约束变分不等式VI(a,b,F).若ai=0,bi=+∞,i∈N,即X=R+n≡{x∈Rn|x≥0}时,VI(a,b,F)化为非线性     

基于时间敏感产品的多厂商供应链管理

本文主要研究基于时间敏感产品的多厂商供应链网络模型。在该模型中,每个厂商都希望自己的运营成本和时间消耗最少,但目标函数和约束条件都受到竞争对手决策的影响,因此属于广义纳什均衡问题的范畴。在过去的文献中,这类问题通常被转化成一般形式的变分不等式来处理。本文中,注意到模型中所涉及的约束函数都是线性函数,我们将问题转化成混合互补系统来求解。与一般形式的变分不等式问题相比,混合互补系统要容易处理得多。借助于所谓Fischer-Burmeister函数,我们将混合互补系统转化成非线性方程组,然后利用半光滑牛顿法进行求解。初步的数值实验表明,本文提出的方法是切实可行的。     

A B-differentiable equation-based,globally and locally quadratically convergent algorithm for nonlinear programs,complementarity and variational inequality problems

This paper presents a globally convergent, locally quadratically convergent algorithm for solving general nonlinear programs, nonlinear complementarity and variational inequality problems. The algorithm is based on a unified formulation of these three mathematical programming problems as a certain system of B-differentiable equations, and is a modification of the damped Newton method described in Pang (1990) for solving such systems of nonsmooth equations. The algorithm resembles several existing methods for solving these classes of mathematical programs, but has some special features of its own; in particular, it possesses the combined advantage of fast quadratic rate of convergence of a basic Newton method and the desirable global convergence induced by one-dimensional Armijo line searches. In the context of a nonlinear program, the algorithm is of the sequential quadratic programming type with two distinct characteristics: (i) it makes no use of a penalty function; and (ii) it circumvents the Maratos effect. In the context of the variational inequality/complementarity problem, the algorithm provides a Newton-type descent method that is guaranteed globally convergent without requiring the F-differentiability assumption of the defining B-differentiable equations.This work was based on research supported by the National Science Foundation under Grant No. ECS-8717968.     

Compression and denoising using <Emphasis Type="Italic">l</Emphasis><Subscript>0</Subscript>-norm

In this paper, we deal with l ₀-norm data fitting and total variation regularization for image compression and denoising. The l ₀-norm data fitting is used for measuring the number of non-zero wavelet coefficients to be employed to represent an image. The regularization term given by the total variation is to recover image edges. Due to intensive numerical computation of using l ₀-norm, it is usually approximated by other functions such as the l ₁-norm in many image processing applications. The main goal of this paper is to develop a fast and effective algorithm to solve the l ₀-norm data fitting and total variation minimization problem. Our idea is to apply an alternating minimization technique to solve this problem, and employ a graph-cuts algorithm to solve the subproblem related to the total variation minimization. Numerical examples in image compression and denoising are given to demonstrate the effectiveness of the proposed algorithm.     

Convergence of a non-interior smoothing method for variational inequality problems

The variational inequality problem can be reformulated as a system of equations. One can solve the reformulated equations to obtain a solution of the original problem. In this paper, based on a symmetric perturbed min function, we propose a new smoothing function, which has some nice properties. By which we propose a new non-interior smoothing algorithm for solving the variational inequality problem, which is based on both the non-interior continuation method and the smoothing Newton method. The proposed algorithm only needs to solve at most one system of equations at each iteration. In particular, we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions. The preliminary numerical results are reported.     

A matrix-splitting method for symmetric affine second-order cone complementarity problems

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.     

The <Emphasis Type="Italic">(S)</Emphasis><Stack><Subscript>+</Subscript><Superscript>1</Superscript></Stack>Condition for Generalized Vector Variational Inequalities

In this paper, we extend the (S) ₊ ¹ condition to multivalued mappings in an ordered Hausdorff topological vector space and we derive some existence results for generalized vector variational inequalities associated with multivalued mappings satisfying the (S) ₊ ¹ condition. We generalize also an existence result of Cubiotti and Yao for generalized variational inequalities of class (S) ₊ ¹ to barreled normed spaces. As consequences, some existence results for vector variational inequalities are established.This work was partially supported by grants from the National Science Council of the Republic of China. Communicated by H. P. Benson     

A note on the complexity of <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> minimization

We discuss the L _p (0 ≤ p < 1) minimization problem arising from sparse solution construction and compressed sensing. For any fixed 0 < p < 1, we prove that finding the global minimal value of the problem is strongly NP-Hard, but computing a local minimizer of the problem can be done in polynomial time. We also develop an interior-point potential reduction algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm.     

Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming

A classical method for solving the variational inequality problem is the projection algorithm. We show that existing convergence results for this algorithm follow from one given by Gabay for a splitting algorithm for finding a zero of the sum of two maximal monotone operators. Moreover, we extend the projection algorithm to solveany monotone affine variational inequality problem. When applied to linear complementarity problems, we obtain a matrix splitting algorithm that is simple and, for linear/quadratic programs, massively parallelizable. Unlike existing matrix splitting algorithms, this algorithm converges under no additional assumption on the problem. When applied to generalized linear/quadratic programs, we obtain a decomposition method that, unlike existing decomposition methods, can simultaneously dualize the linear constraints and diagonalize the cost function. This method gives rise to highly parallelizable algorithms for solving a problem of deterministic control in discrete time and for computing the orthogonal projection onto the intersection of convex sets.This research is partially supported by the U.S. Army Research Office, contract DAAL03-86-K-0171 (Center for Intelligent Control Systems), and by the National Science Foundation under grant NSF-ECS-8519058.Thanks are due to Professor J.-S. Pang for his helpful comments.     

The iterative methods for monotone generalized variational inequalities

A new class of iterative methods are presented for monotone generalized variational inequality problems. These methods, which base on an equivalent formulation of the original problem, can be viewed as the extension of the symmetric projection rnethod for monotone variational inequalities. The global convergence of the methods is estab-lished under the monotonicity assumption on the functions associated the problem.Specialization of the proposed algorithms and related results to several special cases are also discussed. Moreover, two combination methods are presented for affine monotone problems. and their global and Q-linear convergence are also established     

Superlinear convergence of affine scaling interior point newton method for linear inequality constrained minimization without strict complementarity

In this paper we extend and improve the classical affine scaling interior-point Newton method for solving nonlinear optimization subject to linear inequality constraints in the absence of the strict complementarity assumption. Introducing a computationally efficient technique and employing an identification function for the definition of the new affine scaling matrix, we propose and analyze a new affine scaling interior-point Newton method which improves the Coleman and Li affine sealing matrix in [2] for solving the linear inequlity constrained optimization. Local superlinear and quadratical convergence of the proposed algorithm is established under the strong second order sufficiency condition without assuming strict complementarity of the solution.