Equivalence of Two Nondegeneracy Conditions for Semidefinite Programs

Nondegeneracy assumptions are often needed in order to prove the local fast convergence of suitable algorithms as well as in the sensitivity analysis for semidefinite programs. One of the more standard nondegeneracy conditions is the geometric condition used by Alizadeh et al. (Math. Program. 77:111–128, 1997). On the other hand, Kanzow and Nagel (SIAM J. Optim. 15:654–672, 2005) recently introduced an algebraic condition that was used in order to prove, for the first time, the local quadratic convergence of a suitable algorithm for the solution of semidefinite programs without using the strict complementarity assumption. The aim of this paper is to show that these two nondegeneracy conditions are equivalent.     

Additive Schwarz algorithm for the nonlinear complementarity problem with M-function

In this paper, an additive Schwarz algorithm is considered for solving the finite-dimensional nonlinear complementarity problem with M-function. The monotone convergence of the algorithm is obtained with special choices of initial values. Moreover, the weighted max-norm bound is obtained for the iterative errors.     

A continuation method for monotone variational inequalities

This paper presents a continuation method for monotone variational inequality problems based on a new smooth equation formulation. The existence, uniqueness and limiting behavior of the path generated by the method are analyzed.This work was supported by the National Science Foundation Presidential Young Investigator Award ECE-8552773 and by a grant from the Burlington Northern Railroad.     

A nonsmooth Newton method for variational inequalities,I: Theory

This paper presents a modified damped Newton algorithm for solving variational inequality problems based on formulating this problem as a system of equations using the Minty map. The proposed modified damped-Newton method insures convergence and locally quadratic convergence under the assumption of regularity. Under the assumption ofweak regularity and some mild conditions, the modified algorithm is shown to always create a descent direction and converge to the solution. Hence, this new algorithm is often suitable for many applications where regularity does not hold. Part II of this paper presents the results of extensive computational testing of this new method.Corresponding author.     

The linear complementarity problem as a separable bilinear program

The nonmonotone linear complementarity problem (LCP) is formulated as a bilinear program with separable constraints and an objective function that minimizes a natural error residual for the LCP. A linear-programming-based algorithm applied to the bilinear program terminates in a finite number of steps at a solution or stationary point of the problem. The bilinear algorithm solved 80 consecutive cases of the LCP formulation of the knapsack feasibility problem ranging in size between 10 and 3000, with almost constant average number of major iterations equal to four.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9322479 and CDA-9024618.     

A new method for a class of linear variational inequalities

In this paper we introduce a new iterative scheme for the numerical solution of a class of linear variational inequalities. Each iteration of the method consists essentially only of a projection to a closed convex set and two matrix-vector multiplications. Both the method and the convergence proof are very simple.This work is supported by the National Natural Science Foundation of the P.R. China and NSF of Jiangsu.     

Vector complementarity problems with a variable ordering relation

In this paper, we investigate vector complementarity problems with a variable ordering relation. We establish existence results of a solution of a vector complementarity problem under an inclusive type condition. We obtain equivalence results among a vector complementarity problem, a vector variational inequality problem and other related problems.     

New Type of Generalized Vector Quasiequilibrium Problem

In this paper, we introduce a new type of vector quasiequilibrium problem with set-valued mappings and moving cones. By using the scalarization method and fixed-point theorem, we obtain its existence theorem. As applications, we derive some existence theorems for vector variational inequalities and vector complementarity problems. This work was supported by the National Natural Science Foundation of China. The authors are grateful to Professor X.Q. Yang and the referees for valuable comments and suggestions improving the original draft.     

Computational schemes for large-scale problems in extended linear-quadratic programming

Numerical approaches are developed for solving large-scale problems of extended linear-quadratic programming that exhibit Lagrangian separability in both primal and dual variables simultaneously. Such problems are kin to large-scale linear complementarity models as derived from applications of variational inequalities, and they arise from general models in multistage stochastic programming and discrete-time optimal control. Because their objective functions are merely piecewise linear-quadratic, due to the presence of penalty terms, they do not fit a conventional quadratic programming framework. They have potentially advantageous features, however, which so far have not been exploited in solution procedures. These features are laid out and analyzed for their computational potential. In particular, a new class of algorithms, called finite-envelope methods, is described that does take advantage of the structure. Such methods reduce the solution of a high-dimensional extended linear-quadratic program to that of a sequence of low-dimensional ordinary quadratic programs.This work was supported in part by grants AFOSR 87-0821 and AFOSR 89-0081 from the Air Force Office of Scientific Research.     

Solution differentiability for variational inequalities

In this paper we study solution differentiability properties for variational inequalities. We characterize Fréchet differentiability of perturbed solutions to parametric variational inequality problems defined on polyhedral sets. Our result extends the recent result of Pang and it directly specializes to nonlinear complementarity problems, variational inequality problems defined on perturbed sets and to nonlinear programming problems.