ABSTRACTS AND INFO ON REPORTS AND PREPRINTS SORTED BY ENTRY DATE, NEWEST TO OLDEST LAST UPDATE: 16 SEPTEMBER 1999 ********************************************* FORMAT: Compressed postscript AUTHOR(S): Todd S. Munson, F. Facchinei, Michael C. Ferris, Andreas Fischer, Christian Kanzow TITLE: The semismooth algorithm for large scale complementarity problems ABSTRACT: Complementarity solvers are continually being challenged by modelers demanding improved reliability and scalability. Building upon a strong theoretical background, the semismooth algorithm has the potential to meet both of these requirements. We briefly discuss relevant theory associated with the algorithm and describe a sophisticated implementation in detail. Particular emphasis is given to robust methods for dealing with singularities in the linear system and to large scale issues. Results on the MCPLIB test suite indicate that the code is robust and efficient, and scales well to very large problems. STATUS: DIS Technical Report 25.99, Universita' di Roma "La Sapienza" DATE OF ENTRY: 9 September 1999 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei, S. Lucidi and L. Palagi TITLE: A truncated Newton algorithm for large scale box constrained optimization ABSTRACT: A new method for the solution of minimization problems with simple bounds is presented. Global convergence of a general scheme requiring the approximate solution of a single linear system at each iteration is proved and a superlinear convergence rate is established without requiring the strict complementarity assumption. The algorithm proposed is based on a simple, smooth unconstrained reformulation of the bound constrained problem and may produce a sequence of points that are not feasible. Numerical results are reported. STATUS: DIS Technical Report 15.99, Universita' di Roma "La Sapienza" DATE OF ENTRY: 6 August 1999 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei and J.-S. Pang TITLE: Total stability of variational inequalities ABSTRACT: This paper studies the total stability of the solution set of a variational inequality when both the defining function and set are perturbed. Using a degree theoretic approach and variational analytic tools, we establish a general stability result for a variational inequality with a bounded solution set. We apply the main stability result to parametric variational inequalities. We also consider the class of generalized P$_0$ variational inequalities and show that for these problems the boundedness of solutions is a necessary and sufficient condition for their total stability. Finally we study the existence and convergence of the Tikhonov trajectory of a generalized P$_0$ variational inequality. STATUS: DIS Technical Report 09.98, Universita' di Roma "La Sapienza" DATE OF ENTRY: 31 August 1998 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei, A. Fischer and C. Kanzow TITLE: On the identification of zero variables in an interior-point framework ABSTRACT: We consider column sufficient linear complementarity problems and study the problem of identifying those variables that are zero at a solution. To this end we propose a new, computationally inexpensive technique that is based on growth functions. We analyze in detail the theoretical properties of the identification technique and test it numerically. The identification technique is particularly suited to interior-point methods but can be applied to a wider class of methods. STATUS: To appear in SIAM J. on Optimization DATE OF ENTRY: 28 May 1998 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei, A. Fischer and C. Kanzow TITLE: On the identification of zero variables in an interior-point framework: Complete numerical results ABSTRACT: This report only contains the numerical results of the report On the identification of zero variables in an interior-point framework. STATUS: Mathematical Programming TR 98-06-results, Computer Sciences Department, University of Wisconsins, Madison, WI DATE OF ENTRY: 28 May 1998 ********************************************* FORMAT: Compressed postscript AUTHOR(S): T. De Luca, F. Facchinei and C. Kanzow TITLE: A theoretical and numerical comparison of some semismooth algorithms for complementarity problems ABSTRACT: In this paper we introduce a general line search scheme which easily allows us to define and analyze known and new semismooth algorithms for the solution of nonlinear complementarity problems. We enucleate the basic assumptions that a search direction to be used in the general scheme has to enjoy in order to guarantee global convergence, local superlinear/quadratic convergence or finite convergence. We examine in detail several different semismooth algorithms and compare their theoretical features and their practical behavior on a set of large-scale problems. STATUS: To appear in Computational Optimization and Applications DATE OF ENTRY: 22 January 1998 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei TITLE: Structural and stability properties of $P_0$ nonlinear complementarity problems ABSTRACT: We consider $P_0$ nonlinear complementarity problems and study the connectedness and stability of the solutions by applying degree theory and the Mountain Pass Theorem to a smooth reformulation of the complementarity problem. We show that the solution set is connected and bounded if a bounded isolated component of the solution set exists and that a solution is locally unique if and only if it is globally unique. Furthermore, we prove that a solution is stable in Ha's sense if and only if it is globally unique, while the complementarity problem is stable if and only if the solution set is bounded. STATUS: Mathematics of Operations Research, 23, pp. 735-745 DATE OF ENTRY: 26 may 1997 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei and C. Kanzow TITLE: Beyond monotonicity in regularization methods for nonlinear complementarity problems ABSTRACT: Regularization methods for the solution of nonlinear complementarity problems are standard methods for the solution of monotone complementarity problems and possess strong convergence properties. In this paper, we replace the monotonicity assumption by a $ P_0 $-function condition. We show that many properties of regularization methods still hold for this larger class of problems. However, we also provide some counterexamples which indicate that not all results carry over from monotone to $P_0$-function complementarity problems. STATUS: SIAM Journal on Control and Optimization, 37, pp. 1150-1161 DATE OF ENTRY: 26 may 1997 ********************************************* FORMAT: Compressed postscript AUTHOR(S): V.F. Demyanov, G. Di Pillo and F. Facchinei TITLE: Exact penalization via Dini and Hadamard constrained derivatives ABSTRACT: Exact penalty functions for nonsmooth constrained optimization problems are analyzed by using the notion of (Dini) Hadamard directional derivative with respect to the constraint set. Weak conditions are given guaranteeing equivalence of the sets of stationary, global minimum, local minimum points of the constrained problem and of the penalty function. STATUS: Optimization Methods and Software, 9, 19-36, 1998 DATE OF ENTRY: 8 January 1997 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei, A. Fischer, C. Kanzow and J.-M. Peng TITLE: A simply constrained optimization reformulation of KKT systems arising from variational inequalities ABSTRACT: The Karush-Kuhn-Tucker (KKT) conditions can be regarded as optimality conditions for both variational inequalities and constrained optimization problems. In order to overcome some drawbacks of recently proposed reformulations of KKT systems, we propose to cast KKT systems as a minimization problem with nonnegativity constraints on some of the variables. We prove that, under fairly mild assumptions, every stationary point of this constrained minimization problem is a solution of the KKT conditions. Based on this reformulation, a new algorithm for the solution of the KKT conditions is suggested and shown to have some strong global and local convergence STATUS: Applied Mathematics and Optimization, 40, pp.19-37 DATE OF ENTRY: 14 November 1996 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei and S. Lucidi TITLE: Convergence to second order stationary points in inequality constrained optimization ABSTRACT: We propose a new algorithm for the nonlinear inequality constrained minimization problem, and prove that it generates a sequence converging to points satisfying the KKT second order necessary conditions for optimality. The algorithm is a line search algorithm using directions of negative curvature and it can be viewed as a non trivial extension of corresponding known techniques from unconstrained to constrained problems. The main tools employed in the definition and in the analysis of the algorithm are a differentiable exact penalty function and results from the theory of LC$^1$ functions. STATUS: Mathematics of Operations Research, 23, pp. 746-766 DATE OF ENTRY: 23 September 1996 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei, H. Jiang and L. Qi TITLE: A smoothing method for mathematical programs with equilibrium constraints ABSTRACT: The mathematical program with equilibrium constraints (MPEC) is an optimization problem with variational inequality constraints. MPEC problems include bilevel programming problems as a particular case and have a wide range of applications. MPEC problems with strongly monotone variational inequalities are considered in this paper. They are transformed into an equivalent one-level nonsmooth optimization problem. Then, a sequence of smooth, regular problems that progressively approximate the nonsmooth problem and that can be solved by standard available software for constrained optimization is introduced. It is shown that the solutions (stationary points) of the approximate problems converge to a solution (stationary point) of the original MPEC problem. Numerical results showing viability of the approach are reported. STATUS: Mathematical Programming, 85, 107-134 DATE OF ENTRY: 4 march 1996 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei and S. Lucidi TITLE: An unconstrained minimization approach to the solution of optimization problems with simple bounds ABSTRACT: A new method for the solution of minimization problems with simple bounds is presented. Global convergence of a general scheme requiring the solution of a single linear system at each iteration is proved and a superlinear convergence rate is established without requiring the strict complementarity assumption. The theory presented covers Newton and Quasi-Newton methods, allows rapid changes in the active set estimate and is based on a smooth unconstrained reformulation of the bound constrained problem. STATUS: Revised version of the IASI-CNR Technical report R.336. DATE OF ENTRY: 8 January 1996 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei, A. Fischer and C. Kanzow TITLE: A semismooth Newton method for variational inequalities: Theoretical results and preliminary numerical experience ABSTRACT: Variational inequalities over sets defined by systems of equalities and inequalities are considered. A continuously differentiable merit function is proposed whose unconstrained minima coincide with the KKT-points of the variational inequality. A detailed study of its properties is carried out showing that under mild assumptions this reformulation possesses many desirable features. A simple algorithm is proposed for which it is possible to prove global convergence and a fast local convergence rate. Preliminary numerical results showing viability of the approach are reported. STATUS: Appeared, in revised form and with the title "Regularity properties of a semismooth reformualtion of variational inequalities, in SIAM J. on Optimization, 8, pp. 850-869 DATE OF ENTRY: 8 January 1996 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei, A. Fischer and C. Kanzow TITLE: A semismooth Newton method for variational inequalities: The case of box constraints ABSTRACT: We consider a semismooth Newton method for the solution of box constrained variational inequalities. The algorithm is a specialization of a more general one introduced by the authors for arbitrarily constrained variational inequalities. Exploiting the special structure of the box constraints, stronger convergence results are obtained than for the general algorithm. Moreover, numerical results are reported for all examples from the MCPLIB and GAMSLIB test problem collections. STATUS: In "Complementairty and Variational Problems, State of the Art", M.C. Ferris and J.-S. Pang editors, SIAM, 1997, pp. 76-90. DATE OF ENTRY: 8 January 1996 ********************************************* FORMAT: Compressed postscript AUTHOR(S): F. Facchinei, A. Fischer and C. Kanzow TITLE: Inexact Newton methods for semismooth equations with applications to variational inequality problems ABSTRACT: We consider the local behaviour of inexact Newton methods for the solution of a semismooth system of equations. In particular, we give a complete characterization of the Q-superlinear and Q-quadratic convergence of inexact Newton methods. We then apply these results to a particular semismooth system of equations arising from variational inequality problems, and present a globally and locally fast convergent algorithm for its solution. STATUS: In 'Nonlinear Optimization and Applications', G.Di Pillo and F. Giannessi editors, Plenum Press. DATE OF ENTRY: 8 January 1996 ********************************************* AUTHOR(S): F. Facchinei and C. Kanzow TITLE: When are the (un)constrained stationary points of the implicit Lagrangian global solutions? ABSTRACT: Mangasarian and Solodov [Mathematical Programming, Vol. 62, pp. 277--297, 1993] proposed to solve nonlinear complementarity problems by seeking the unconstrained global minima of a new merit function which they called implicit Lagrangian. A crucial point in such an approach is to determine conditions which guarantee that every unconstrained stationary point of the implicit Lagrangian is a global solution, since standard unconstrained minimization techniques are only able to locate stationary points. Some authors partially answered this question by giving sufficient conditions which guarantee this key property. In this paper we settle the issue by giving a necessary and sufficient condition for a stationary point of the implicit Lagrangian to be a global solution and, hence, a solution of the nonlinear complementarity problem. We show that this new condition easily allows us to recover all previous results and to establish new sufficient conditions. We then consider a constrained reformulation based on the implicit Lagrangian in which nonnegative constraints on the variables are added to the original unconstrained reformulation. This is motivated by the fact that often, in applications, the function which defines the complementarity problem is defined only on the nonnegative orthant. We consider the KKT-points of this new reformulation and show that the same necessary and sufficient condition which guarantees, in the unconstrained case, that every unconstrained stationary point is a global solution, also guarantees that every KKT-point of the new problem is a global solution. STATUS: Appeared, in revised form and with a different title, in Journal of Optimization Theory and Applications, 92, 99-115, 1997. DATE OF ENTRY: 31 July 1995 ********************************************* AUTHOR(S): F. Facchinei and C. Kanzow TITLE: A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems ABSTRACT: A new algorithm for the solution of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to 10000 variables are presented. STATUS: Mathematical Programming 76, 493-512, 1997. DATE OF ENTRY: 25 May 1995 ********************************************* AUTHOR(S): F. Facchinei TITLE: On the convergence to a unique point of minimization algorithms ABSTRACT: We give a new sufficient condition for a sequence produced by a minimization algorithm to have a unique limit point. This condition extends and improves known results and allows us to deal with a wide range of problems. STATUS: DIS Technical Report 06.95. DATE OF ENTRY: 23 May 1995 ********************************************* AUTHOR(S): G. Di Pillo and F. Facchinei TITLE: Exact barrier function methods for Lipschitz programs ABSTRACT: The purpose of this paper is twofold. First we consider a class of nondifferentiable penalty functions for constrained Lipschitz programs and then we show how these penalty functions can be employed to actually solve a constrained Lipschitz program. The penalty functions considered incorporate a barrier term which makes their value go to infinity on the boundary of a perturbation of the feasible set. Exploiting this fact it is possible to prove, under mild compactness and regularity assumptions, a complete correspondence between the unconstrained minimization of the penalty functions and the solutions of the constrained program, thus showing that the penalty functions are exact according to the definition introduced in [17]. Motivated by these results, we then propose some algorithm models and study their convergence properties. We show that, even when the assumptions used to establish the exactness of the penalty functions are not satisfied, every limit point of the sequence produced by a basic algorithm model is an extended stationary point according to the definition given in [8]. Then, based on this analysis and on the one previously carried out on the penalty function, we study the consequences on the convergence properties of increasingly demanding assumptions. In particular we show that under the same assumptions used to establish the exactness properties of the penalty functions, it is possible to guarantee that a limit point at least exists, and that any such limit point is a KKT point for the constrained problem. STATUS: Applied Mathematics and Optimization 32, pp. 1-31, 1995. DATE OF ENTRY: 7 april 1995 ********************************************* AUTHOR(S): J. Soares, J. J\'udice and F. Facchinei TITLE: An active set Newton's algorithm for large-scale nonlinear programs with box constraints ABSTRACT: A new algorithm for large-scale nonlinear programs with box constraints is introduced. The algorithm is based on an efficient identification technique of the active set at the solution and on a nonmonotone stabilization technique. It possesses global and superlinear convergence properties under standard, mild assumptions. A new technique for generating test problems with known characteristics is also introduced. The implementation of the method is described along with computational results for large-scale problems. STATUS: SIAM J. on Optimization, 7, 225-247, 1997. DATE OF ENTRY: 7 march 1995 ********************************************* AUTHOR(S): T.De Luca, F. Facchinei and C. Kanzow TITLE: A semismooth equation approach to the solution of nonlinear complementarity problems ABSTRACT: In this paper we present a new algorithm for the solution of nonlinear complementarity problems. The algorithm is based on a semismooth equation reformulation of the complementarity problem. We exploit the recent extension of Newton's method to semismooth systems of equations and the fact that the natural merit function associated to the equation reformulation is continuously differentiable to develop an algorithm whose global and quadratic convergence properties can be established under very mild assumptions. Other interesting features of the new algorithm are an extreme simplicity along with a low computational burden per iteration. We include numerical tests which show the viability of the approach. STATUS: Mathematical Programming, 75, 407-439, 1996 DATE OF ENTRY: 19 February 1995 ********************************************* AUTHOR(S): F. Facchinei and J.Soares TITLE: Testing a new class of algorithms for nonlinear complementarity problems. ABSTRACT: We investigate the numerical behavior of a new, simple algorithm for the solution of nonlinear complementarity problems. The algorithm is based on a recently proposed merit function which possesses some interesting theoretical properties. One of the aims of the paper is to show that algorithms based on this merit function can be viable also from the numerical point of view. STATUS: In 'Variational Inequalities and Network Equilibrium Problems', F, Giannessi ed., Plenum Press. DATE OF ENTRY: 22 February 1995 ********************************************* AUTHOR(S): F. Facchinei and S.Lucidi TITLE: Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems. ABSTRACT: In this paper some Newton and quasi-Newton algorithms for the solution of inequality constrained minimization problems are considered. All the algorithms described produce sequences $\{x_k\}$ converging $q$-superlinearly to the solution. Furthermore, under mild assumptions, a $q$-quadratic convergence rate in $x$ is also attained. Other features of these algorithms are that the solution of linear systems of equations only is required at each iteration and that the strict complementarity assumption is never invoked. First the superlinear or quadratic convergence rate of a Newton-like algorithm is proved. Then, a simpler version of this algorithm is studied and it is shown that it is superlinearly convergent. Finally, quasi-Newton versions of the previous algorithms are considered and, provided the sequence defined by the algorithms converges, a characterization of superlinear convergence extending the result of Boggs, Tolle and Wang is given. STATUS: Journal of Optimization Theory and Applications 85, pp. 265-289, 1994 . DATE OF ENTRY: 19 February 1995 ********************************************* AUTHOR(S): F. Facchinei and S.Lucidi TITLE: A Newton-like algorithm for the solution of inequality constrained minimization problems. ABSTRACT: We describe a new Newton-type algorithm for the solution of inequality constrained minimization problems. The algorithm is based on an active-set strategy and, at each iteration, only requires the solution of one linear system. Under mild assumptions, and without requiring strict complementarity, we prove q-quadratic convergence of the primal variables towards the solution. STATUS: 'Operations Research 94', U.Derigs, A. Bachem and A. Drexl editors, pp. 33-38, Springer Verlag, Heidelberg, 1995. Springer-Verlag DATE OF ENTRY: 19 February 1995 ********************************************* AUTHOR(S): F. Facchinei and J. Soares TITLE: A new merit function for nonlinear complementarity problems and a related algorithm. ABSTRACT: We investigate the properties of a new merit function which allows us to reduce a nonlinear complementarity problem to an unconstrained global minimization one. Assuming that the complementarity problem is defined by a $P_0$-function we prove that every stationary point of the unconstrained problem is a global solution; furthermore, if the complementarity problem is defined by a uniform $P$-function, the level sets of the merit function are bounded. The properties of the new merit function are compared with those of the Mangasarian-Solodov's implicit Lagrangian and Fukushima's regularized gap function. We also introduce a new, simple, active-set local method for the solution of complementarity problems and show how this local algorithm can be made globally convergent by using the new merit function. STATUS: SIAM J. on Optimization, 7, 225-247, 1997. DATE OF ENTRY: 19 February 1995 ********************************************* AUTHOR(S): F. Facchinei TITLE: Minimization of SC^1 functions and the Maratos effect. ABSTRACT: We consider the unconstrained minimization of a continuously differentiable function with semismooth gradient by line search methods; in particular we focus on the problem of the acceptance of the unit stepsize. We show that, under mild conditions, if the full search direction brings superlinear convergence, then the unit stepsize is eventually accepted so that the Maratos effect does not occur. The relevance to this issue of a generalization of the classical second order sufficient condition for optimality is pointed out. STATUS: Operations Research Letters 17, pp. 131-137, 1995. DATE OF ENTRY: 19 February 1995