Extended LQP Method for Monotone Nonlinear Complementarity Problems

To solve nonlinear complementarity problems (NCP), the logarithmic-quadratic proximal (LQP) method solves a system of nonlinear equations at each iteration. In this paper, the iterates generated by the original LQP method are extended by explicit formulas and thus an extended LQP method is presented. It is proved theoretically that the lower bound of the progress obtained by the extended LQP method is greater than that by the original LQP method. Preliminary numerical results are provided to verify the theoretical assertions and the effectiveness of both the original and the extended LQP method.     

A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

On the O(1/t) convergence rate of the LQP prediction–correction method

The logarithmic-quadratic proximal (abbreviated by LQP) prediction–correction method is attractive for structured monotone variational inequalities, and it ensures the global convergence under some suitable conditions. In this paper, we are interested in investigating the convergence rate of the LQP prediction–correction method. Motivated by the research work about the convergence rate or iteration complexity for various first-order algorithms in the literature, we provide a simple proof to show the $O(1/t)$ convergence rate for the LQP prediction–correction method.     

A new criterion for the inexact logarithmic-quadratic proximal method and its derived hybrid methods

To solve nonlinear complementarity problems, the inexact logarithmic-quadratic proximal (LQP) method solves a system of nonlinear equations (LQP system) approximately at each iteration. Therefore, the efficiencies of inexact-type LQP methods depend greatly on the involved inexact criteria used to solve the LQP systems. This paper relaxes inexact criteria of existing inexact-type LQP methods and thus makes it easier to solve the LQP system approximately. Based on the approximate solutions of the LQP systems, a descent method, and a prediction–correction method are presented. Convergence of the new methods are proved under mild assumptions. Numerical experiments for solving traffic equilibrium problems demonstrate that the new methods are more efficient than some existing methods and thus verify that the new inexact criterion is attractive in practice.     

A new LQP alternating direction method for solving variational inequality problems with separable structure

We presented a new logarithmic-quadratic proximal alternating direction scheme for the separable constrained convex programming problem. The predictor is obtained by solving series of related systems of non-linear equations in a parallel wise. The new iterate is obtained by searching the optimal step size along a new descent direction. The new direction is obtained by the linear combination of two descent directions. Global convergence of the proposed method is proved under certain assumptions. We show the O(1 / t) convergence rate for the parallel LQP alternating direction method.     

关于一类变分不等式的LQP算法

本文研究一类ξ-单调的变分不等式问题.利用KKT条件将原问题转换为非线性互补问题(nonlinear complementarity problem,NCP)的方法,获得了基于logarithmic-quadratic proximal(LQP)的算法及其改进形式,推广了LQP算法的适用范围.     

A LQP BASED INTERIOR PREDICTION-CORRECTION METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

To solve nonlinear complementarity problems （NCP）, at each iteration, the classical proximal point algorithm solves a well-conditioned sub-NCP while the Logarithmic-Quadratic Proximal （LQP） method solves a system of nonlinear equations （LQP system）. This paper presents a practical LQP method-based prediction-correction method for NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed restriction, and the new iterate （the corrector） is computed directly by an explicit formula derived from the original LQP method. The implementations are very easy to be carried out. Global convergence of the method is proved under the same mild assumptions as the original LQP method. Finally, numerical results for traffic equilibrium problems are provided to verify that the method is effective for some practical problems.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

Perturbation Lemma for the Newton Method with Application to the SQP Newton Method

We study the convergence of a general perturbation of the Newton method for solving a nonlinear system of equations. As an application, we show that the augmented Lagrangian successive quadratic programming is locally and q-quadratically convergent in the variable x to the solution of an equality constrained optimization problem, under a mild condition on the penalty parameter and the choice of the Lagrange multipliers.     

A hybrid inexact Logarithmic-Quadratic Proximal method for nonlinear complementarity problems

Inspired by the Logarithmic-Quadratic Proximal method [A. Auslender, M. Teboulle, S. Ben-Tiba, A logarithmic-quadratic proximal method for variational inequalities, Comput. Optim. Appl. 12 (1999) 31-40], we present a new prediction-correction method for solving the nonlinear complementarity problems. In our method, an intermediate point is produced by approximately solving a nonlinear equation system based on the Logarithmic-Quadratic Proximal method; and the new iterate is obtained by convex combination of the previous point and the one generated by the improved extragradient method at each iteration. The proposed method allows for constant relative errors and this yields a more practical Logarithmic-Quadratic Proximal type method. The global convergence is established under mild conditions. Preliminary numerical results indicate that the method is effective for large-scale nonlinear complementarity problems.     

Interior Proximal Algorithm for Quasiconvex Programming Problems and Variational Inequalities with Linear Constraints

In this paper, we propose two interior proximal algorithms inspired by the logarithmic-quadratic proximal method. The first method we propose is for general linearly constrained quasiconvex minimization problems. For this method, we prove global convergence when the regularization parameters go to zero. The latter assumption can be dropped when the function is assumed to be pseudoconvex. We also obtain convergence results for quasimonotone variational inequalities, which are more general than monotone ones.     

An LQP-based descent method for structured monotone variational inequalities

This paper proposes a descent method to solve a class of structured monotone variational inequalities. The descent directions are constructed from the iterates generated by a prediction-correction method [B.S. He, Y. Xu, X.M. Yuan, A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities, Comput. Optim. Appl. 35 (2006) 19-46], which is based on the logarithmic-quadratic proximal method. In addition, the optimal step-sizes along these descent directions are identified to accelerate the convergence of the new method. Finally, some numerical results for solving traffic equilibrium problems are reported.     

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 inexact parallel splitting augmented Lagrangian method for monotone variational inequalities with separable structures

Splitting methods have been extensively studied in the context of convex programming and variational inequalities with separable structures. Recently, a parallel splitting method based on the augmented Lagrangian method (abbreviated as PSALM) was proposed in He (Comput. Optim. Appl. 42:195?C212, 2009) for solving variational inequalities with separable structures. In this paper, we propose the inexact version of the PSALM approach, which solves the resulting subproblems of PSALM approximately by an inexact proximal point method. For the inexact PSALM, the resulting proximal subproblems have closed-form solutions when the proximal parameters and inexact terms are chosen appropriately. We show the efficiency of the inexact PSALM numerically by some preliminary numerical experiments.     

An improved LQP-based method for solving nonlinear complementarity problems

The well-known logarithmic-quadratic proximal (LQP)method has motivated a number of efficient numerical algorithms for solving nonlinear complementarity problems (NCPs). In this paper,we aim at improving one of them, i.e., the LQP-based interior prediction-correction method proposed in [He, Liao and Yuan, J. Comp. Math., 2006, 24(1): 33–44], via identifying more appropriate step-sizes in the correction steps. Preliminary numerical results for solving some NCPs arising in traffic equilibrium problems are reported to verify the theoretical assertions.     

带新NCP函数的Lagrangian乘子方法

在经营管理、工程设计、科学研究、军事指挥等方面普遍存在着最优化问题,而实际问题中出现的绝大多数问题都被归纳为非线性规划问题之中。作为带等式、不等式约束的复杂事例,最优化问题的求解向来较为繁琐、困难。适当条件下,非线性互补函数(NCP)可以与约束优化问题相结合,其中NCP函数的无约束极小解对应原约束问题的解及其乘子。本文提出了一类新的NCP函数用于解决等式和不等式约束非线性规划问题,结合新的NCP函数构造了增广Lagrangian函数。在适当假设条件下,证明了增广Lagrangian函数与原问题的解之间的一一对应关系。同时构造了相应算法,并证明了该算法的收敛性和有效性。     

Algorithms for solutions of extended general mixed variational inequalities and fixed points

In this paper, we introduce and study a new class of extended general nonlinear mixed variational inequalities and a new class of extended general resolvent equations and establish the equivalence between the extended general nonlinear mixed variational inequalities and implicit fixed point problems as well as the extended general resolvent equations. Then by using this equivalent formulation, we discuss the existence and uniqueness of solution of the problem of extended general nonlinear mixed variational inequalities. Applying the aforesaid equivalent alternative formulation and a nearly uniformly Lipschitzian mapping S, we construct some new resolvent iterative algorithms for finding an element of set of the fixed points of nearly uniformly Lipschitzian mapping S which is the unique solution of the problem of extended general nonlinear mixed variational inequalities. We study convergence analysis of the suggested iterative schemes under some suitable conditions. We also suggest and analyze a class of extended general resolvent dynamical systems associated with the extended general nonlinear mixed variational inequalities and show that the trajectory of the solution of the extended general resolvent dynamical system converges globally exponentially to the unique solution of the extended general nonlinear mixed variational inequalities. The results presented in this paper extend and improve some known results in the literature.     

解约束优化的分段线性有理NCP函数

本文给出新的NCP函数,这些函数是分段线性有理正则伪光滑的,且具有良好的性质.把这些NCP函数应用到解非线性优化问题的方法中.例如,把求解非线性约束优化问题的KKT点问题分别用QP-free方法,乘子法转化为解半光滑方程组或无约束优化问题.然后再考虑用非精确牛顿法或者拟牛顿法来解决该半光滑方程组或无约束优化问题.这个方法是可实现的,且具有全局收敛性.可以证明在一定假设条件下,该算法具有局部超线性收敛性.     

A Logarithmic-Quadratic Proximal Method for Variational Inequalities

We present a new method for solving variational inequalities on polyhedra. The method is proximal based, but uses a very special logarithmic-quadratic proximal term which replaces the usual quadratic, and leads to an interior proximal type algorithm. We allow for computing the iterates approximately and prove that the resulting method is globally convergent under the sole assumption that the optimal set of the variational inequality is nonempty.     

A Logarithmic-Quadratic Proximal Prediction-Correction Method for Structured Monotone Variational Inequalities

Inspired by the Logarithmic-Quadratic Proximal (LQP) method for variational inequalities, we present a prediction-correction method for structured monotone variational inequalities. Each iteration of the new method consists of a prediction and a correction. Both the predictor and the corrector are obtained easily with tiny computational load. In particular, the LQP system that appears in the prediction is approximately solved under significantly relaxed inexactness restriction. Global convergence of the new method is proved under mild assumptions. In addition, we present a self-adaptive version of the new method that leads to easier implementations. Preliminary numerical experiments for traffic equilibrium problems indicate that the new method is effectively applicable in practice. Presented at the 6th International conference on Optimization: Techniques and Applications, Ballarat Australia, December 9–11, 2004. This author was supported by NSFC Grant 10571083, the MOEC grant 20020284027 and Jiangsu NSF grant BK2002075