ICCP99

INTERNATIONAL CONFERENCE ON COMPLEMENTARITY PROBLEMS Contemporary Applications and Algorithms Madison, WI, June 9, 10, 11, 12, 1999

Abstract

Kristin P. Bennett

Email	bennek@rpi.edu
Institute	Rensselaer Polytechnic Institute
Title	An Equilibrium Constrained Approach to Semi-Supervised Learning
Co-authors
Abstract	We are examining semi-supervised methods for using unlabeled and label ed data to improve accuracy on classification tasks. In traditional supervised learning, we are given a set of training data consisting of vectors labeled with their class membership. From this training data, a discriminant function is constructed to label future unlabeled data. Unsupervised learning methods try to extract structure from unlabeled data. Semi-supervised learning exploits all available data, both labeled and unlabeled. For many practical problems, such as medical tests for difficult-to-diagnosis diseases, web page classification, and prediction of drug bio-responses, the amount of labeled training data may be relatively small, making prediction difficult. At a minimum the data to be predicted can be used to help improve classification. Frequently, in these applications, large amounts of unlabeled data may be available. By using the information in both the labeled and unlabeled data, our hope is to improve future prediction, especially in cases in which the labeled data are insufficient for training or there are shifts in the input distribution between the labeled an unlabeled data. In this talk, we will show how semi-supervised approaches for training support vector machines and related classification methods can be modeled as mathematical programming problems with equilibrium constraints. Preliminary results support our hypothesis that incorporating unlabeled data can improve performance on classification tasks. The best way to approach these problems, however, is still very much an open question. The challenge is to develop practical computational methods scalable to very high dimensional problems.

Steven Benson

Email benson@mcs.anl.gov

Institute Argonne National Laboratory

Title Solving Large Scale Sparse Semidefinite Programs for Combinatorial Optimization

Co-authors Yinyu Ye, Xiong Zhang

Abstract We present a dual scaling interior point algorithm and show how it exploits structure and sparsity of some large scale problems. We solve the positive semidefinite relaxation of combinatorial and quadratic optimization problems subject to boolean constraints and report computational results of for semidefinite programs with dimension up to 10,000.

Email	benson@mcs.anl.gov
Institute	Argonne National Laboratory
Title	Solving Large Scale Sparse Semidefinite Programs for Combinatorial Optimization
Co-authors	Yinyu Ye, Xiong Zhang
Abstract	We present a dual scaling interior point algorithm and show how it exploits structure and sparsity of some large scale problems. We solve the positive semidefinite relaxation of combinatorial and quadratic optimization problems subject to boolean constraints and report computational results of for semidefinite programs with dimension up to 10,000.

Stephen Billups

Email sbillups@carbon.cudenver.edu

Institute University of Colorado at Denver

Title A Nonmonotone Path Following Method for Complementarity Problems and Nonsmooth Equations

Co-authors Adam Speight, Layne Watson

Abstract We present a homotopy path following method for nonsmooth equations, which is effective at solving highly nonlinear equations for which the norm of the residual has nonglobal local minima. The method is based on a class of homotopy mappings that are smooth in the interior of their domain. Sufficient conditions are presented that guarantee the existence of well-behaved zero curves of these homotopy mappings, which can be followed to a solution. These zero curves need not be monotonic in the homotopy parameter. We specialize the method to solve complementarity problems through the use of MCP functions and associated smoothers.

Email	sbillups@carbon.cudenver.edu
Institute	University of Colorado at Denver
Title	A Nonmonotone Path Following Method for Complementarity Problems and Nonsmooth Equations
Co-authors	Adam Speight, Layne Watson
Abstract	We present a homotopy path following method for nonsmooth equations, which is effective at solving highly nonlinear equations for which the norm of the residual has nonglobal local minima. The method is based on a class of homotopy mappings that are smooth in the interior of their domain. Sufficient conditions are presented that guarantee the existence of well-behaved zero curves of these homotopy mappings, which can be followed to a solution. These zero curves need not be monotonic in the homotopy parameter. We specialize the method to solve complementarity problems through the use of MCP functions and associated smoothers.

Paul Bradley

Email bradley@microsoft.com

Institute Microsoft Research

Title Scalable Probabilistic Clustering

Co-authors U. M. Fayyad, C. Reina

Abstract We address the problem of probabilistically clustering a possibly massive database by estimating the probability density function generating the data. The probability density function is approximated by a mixture model, which handles multiple data types and naturally supports the clustering application. Maximum likelihood mixture model parameters are computed via the Expectation Maximization (EM) algorithm. The algorithm is scaled to address massive databases by selectively compressing redundant data with respect to the mixture model. Performance of this scheme is compared with sampling-based EM and online EM approaches lacking selective data compression.

Email	bradley@microsoft.com
Institute	Microsoft Research
Title	Scalable Probabilistic Clustering
Co-authors	U. M. Fayyad, C. Reina
Abstract	We address the problem of probabilistically clustering a possibly massive database by estimating the probability density function generating the data. The probability density function is approximated by a mixture model, which handles multiple data types and naturally supports the clustering application. Maximum likelihood mixture model parameters are computed via the Expectation Maximization (EM) algorithm. The algorithm is scaled to address massive databases by selectively compressing redundant data with respect to the mixture model. Performance of this scheme is compared with sampling-based EM and online EM approaches lacking selective data compression.

Steven Dirkse

Email sdirkse@gams.com

Institute GAMS Development Corporation

Title Complementarity@GAMS.com

Co-authors

Abstract In the past decade, complementarity programming (CP) has taken its place alongside LP, MIP, and NLP as a staple at GAMS Development. We first describe some core extensions to GAMS that have made CP possible and result in important advantages, both to modelers and algorithm developers. The GAMS/MPSGE system for equilibrium models discussed next builds on the MCP model and greatly expands its usefulness for economists, creating great demand for efficient and robust CP solvers. This need is met currently by MILES and PATH, two CP solvers available within GAMS. Building on past success, current work includes the addition of MPEC to GAMS and reformulation tools (e.g. NLP2MCP, MCP2NLP).

Email	sdirkse@gams.com
Institute	GAMS Development Corporation
Title	Complementarity@GAMS.com
Co-authors
Abstract	In the past decade, complementarity programming (CP) has taken its place alongside LP, MIP, and NLP as a staple at GAMS Development. We first describe some core extensions to GAMS that have made CP possible and result in important advantages, both to modelers and algorithm developers. The GAMS/MPSGE system for equilibrium models discussed next builds on the MCP model and greatly expands its usefulness for economists, creating great demand for efficient and robust CP solvers. This need is met currently by MILES and PATH, two CP solvers available within GAMS. Building on past success, current work includes the addition of MPEC to GAMS and reformulation tools (e.g. NLP2MCP, MCP2NLP).

Francisco Facchinei

Email soler@dis.uniroma1.it

Institute University of Rome La Sapienza

Title An upper-level smoothing method for MPECs

Co-authors Christian Kanzow

Abstract We present preliminary results on an exact penalty approach to the solution of MPECs. We consider the case of nonlinear complementarity constraints and establish when the minimization of a nondifferentiable penalty function is fully equivalent to the solution of the original problem. Then we outline a general smoothing method for the minimization of the penalty function which includes appropriate rules for the updating of the penalty and smoothing parameters and prove convergence to stationary points.

Email	soler@dis.uniroma1.it
Institute	University of Rome La Sapienza
Title	An upper-level smoothing method for MPECs
Co-authors	Christian Kanzow
Abstract	We present preliminary results on an exact penalty approach to the solution of MPECs. We consider the case of nonlinear complementarity constraints and establish when the minimization of a nondifferentiable penalty function is fully equivalent to the solution of the original problem. Then we outline a general smoothing method for the minimization of the penalty function which includes appropriate rules for the updating of the penalty and smoothing parameters and prove convergence to stationary points.

Masao Fukushima

Email fuku@kuamp.kyoto-u.ac.jp

Institute Kyoto University

Title Convergence of a Smoothing Continuation Method for Mathematical Programs with Complementarity Constraints

Co-authors Jong-Shi Pang

Abstract We study the behavior of a sequence generated by a smoothing continuation method for mathematical programs with equilibrium constraints (MPEC ). In particular, we show that under the linear independence constraint qualification and an additional condition called the asymptotic weak nondegeneracy, the limit of KKT points satisfying the second-order necessary conditions for the perturbed problems is a B-stationary point of the original MPEC. The notable fact is that this result does not rely on the strict complementarity assumption at the limit point.

Email	fuku@kuamp.kyoto-u.ac.jp
Institute	Kyoto University
Title	Convergence of a Smoothing Continuation Method for Mathematical Programs with Complementarity Constraints
Co-authors	Jong-Shi Pang
Abstract	We study the behavior of a sequence generated by a smoothing continuation method for mathematical programs with equilibrium constraints (MPEC ). In particular, we show that under the linear independence constraint qualification and an additional condition called the asymptotic weak nondegeneracy, the limit of KKT points satisfying the second-order necessary conditions for the perturbed problems is a B-stationary point of the original MPEC. The notable fact is that this result does not rely on the strict complementarity assumption at the limit point.

David M. Gay

Email dmg@research.bell-labs.com

Institute Bell Labs

Title New AMPL Notation for Complementarity Problems

Co-authors Michael Ferris, Robert Fourer

Abstract Some problems involve complementarity constraints: pairs of inequalities, at least one of which must be tight. New, flexible AMPL syntax provides a convenient way to state such constraints, which are turned into a canonical form for solvers. This extends AMPL to (non)linear complementarity problems and optimization problems with equilibrium constraints.

Email	dmg@research.bell-labs.com
Institute	Bell Labs
Title	New AMPL Notation for Complementarity Problems
Co-authors	Michael Ferris, Robert Fourer
Abstract	Some problems involve complementarity constraints: pairs of inequalities, at least one of which must be tight. New, flexible AMPL syntax provides a convenient way to state such constraints, which are turned into a canonical form for solvers. This extends AMPL to (non)linear complementarity problems and optimization problems with equilibrium constraints.

M. Seetharama Gowda

Email gowda@math.umbc.edu

Institute University of Maryland Baltimore County

Title Semidefinite linear complementarity problems and a theorem of Lyapunov

Co-authors Y. Song

Abstract In this talk, we describe ${\bf P}$-, ${\bf Q}$-, and ${\bf GUS}$-properties for semidefinite linear complementarity problems. For a matrix $A\in R^{n\times n}$, we consider the linear transformation $L_A$ defined, on the space ${\cal S}^n$ of all real symmetric $n\times n$ matrices, by $L_A(X)=AX+XA^T$ and show that the ${\bf P}$- and ${\bf Q}$-properties for $L_A$ are equivalent to $A$ being positive stable, i.e., real parts of eigenvalues of $A$ are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.

Email	gowda@math.umbc.edu
Institute	University of Maryland Baltimore County
Title	Semidefinite linear complementarity problems and a theorem of Lyapunov
Co-authors	Y. Song
Abstract	In this talk, we describe ${\bf P}$-, ${\bf Q}$-, and ${\bf GUS}$-properties for semidefinite linear complementarity problems. For a matrix $A\in R^{n\times n}$, we consider the linear transformation $L_A$ defined, on the space ${\cal S}^n$ of all real symmetric $n\times n$ matrices, by $L_A(X)=AX+XA^T$ and show that the ${\bf P}$- and ${\bf Q}$-properties for $L_A$ are equivalent to $A$ being positive stable, i.e., real parts of eigenvalues of $A$ are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.

Jacqueline Huang

Email jhuang@brutus.mts.jhu.edu

Institute Johns Hopkins University

Title An MPEC approach to inverse pricing of American options: the case of implied volatilities

Co-authors Jong-Shi Pang

Abstract We present a novel approach to deal with the computation of implied volatilities of American options written on a risky asset. The approach is based on the simple observation that this computational problem is the inverse of the forward pricing problem of American options. The latter forward problem can be modeled by a discretized partial differential linear complementarity system. As such, the inverse problem, i.e., the implied volatility problem, becomes an instance of a {\bf M}athematical {\bf P}rogram with {\bf E}quilibrium {\bf C}onstraints, which is a class of constrained optimization problem with a finite-dimensional parametric linear complementarity system as part of its constraints. Two methods for solving an MPEC are described and applied to the problem of computing implied volatilities of American options. Some computational results on experimental data are reported.

Email	jhuang@brutus.mts.jhu.edu
Institute	Johns Hopkins University
Title	An MPEC approach to inverse pricing of American options: the case of implied volatilities
Co-authors	Jong-Shi Pang
Abstract	We present a novel approach to deal with the computation of implied volatilities of American options written on a risky asset. The approach is based on the simple observation that this computational problem is the inverse of the forward pricing problem of American options. The latter forward problem can be modeled by a discretized partial differential linear complementarity system. As such, the inverse problem, i.e., the implied volatility problem, becomes an instance of a {\bf M}athematical {\bf P}rogram with {\bf E}quilibrium {\bf C}onstraints, which is a class of constrained optimization problem with a finite-dimensional parametric linear complementarity system as part of its constraints. Two methods for solving an MPEC are described and applied to the problem of computing implied volatilities of American options. Some computational results on experimental data are reported.

Christian Kanzow

Email kanzow@math.uni-hamburg.de

Institute University of Hamburg

Title Strictly Feasible Equation-Based Methods for Mixed Complementarity Problems

Co-authors

Abstract We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively complicated subproblems (like quadratic programs or linear complementarity problems), or they have to solve relatively simple subproblems (like linear systems of equations) but do not necessarily generate feasible iterates. The method to be presented here combines the nice features of these two types of methods: It has to solve only one linear system of equations (of reduced dimension) at each iteration and it generates only feasible (more precisely: strictly feasible) iterates. The method will be shown to have some strong global and local convergence properties. Some preliminary numerical results will also be given.

Email	kanzow@math.uni-hamburg.de
Institute	University of Hamburg
Title	Strictly Feasible Equation-Based Methods for Mixed Complementarity Problems
Co-authors
Abstract	We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively complicated subproblems (like quadratic programs or linear complementarity problems), or they have to solve relatively simple subproblems (like linear systems of equations) but do not necessarily generate feasible iterates. The method to be presented here combines the nice features of these two types of methods: It has to solve only one linear system of equations (of reduced dimension) at each iteration and it generates only feasible (more precisely: strictly feasible) iterates. The method will be shown to have some strong global and local convergence properties. Some preliminary numerical results will also be given.

Masakazu Kojima

Email kojima@is.titech.ac.jp

Institute Tokyo Institute of Technology

Title Successive convex relaxation methods and their application to bilevel optimization problems.

Co-authors Akiko Takeda

Abstract We first explain successive convex relaxation methods proposed by Kojima and Tuncel for general quadratic optimization problems, and then discuss how we adapt the methods for bilevel optimization problems.

Email	kojima@is.titech.ac.jp
Institute	Tokyo Institute of Technology
Title	Successive convex relaxation methods and their application to bilevel optimization problems.
Co-authors	Akiko Takeda
Abstract	We first explain successive convex relaxation methods proposed by Kojima and Tuncel for general quadratic optimization problems, and then discuss how we adapt the methods for bilevel optimization problems.

Patrice Marcotte

Email marcotte@iro.umontreal.ca

Institute DIRO, Universite de Montreal

Title A strategic approach to network equilibrium under rigid capacity constraints.

Co-authors Sang Nguyen, Alexandre Schoeb

Abstract We consider a network equilibrium model where the arcs of the underlying transportation network have rigid capacities that cannot be exceeded, and where travel costs are fixed. Whenever shortest paths cannot accommodate all traffic, then it is clear that no feasible flow assignment can meet Wardrop`s criterion of equal and minimum travel times on all paths carrying positive flow. To circumvent that situation, we propose a model where the users' decision variables (paths) are replaced by travel strategies. In this framework, the set of paths may be identified with the subset of `pure' strategies. We show that a mixed strategy equilibrium can be characterized as the solution of some nonmonotone variational inequality for which algorithms have been implemented and tested. If time permits, we will consider the situation where priority rules are present and outline the close relationship between the resulting model and a continuous-time formulation of the dynamic traffic assignment with affine delay functions.

Email	marcotte@iro.umontreal.ca
Institute	DIRO, Universite de Montreal
Title	A strategic approach to network equilibrium under rigid capacity constraints.
Co-authors	Sang Nguyen, Alexandre Schoeb
Abstract	We consider a network equilibrium model where the arcs of the underlying transportation network have rigid capacities that cannot be exceeded, and where travel costs are fixed. Whenever shortest paths cannot accommodate all traffic, then it is clear that no feasible flow assignment can meet Wardrop`s criterion of equal and minimum travel times on all paths carrying positive flow. To circumvent that situation, we propose a model where the users' decision variables (paths) are replaced by travel strategies. In this framework, the set of paths may be identified with the subset of `pure' strategies. We show that a mixed strategy equilibrium can be characterized as the solution of some nonmonotone variational inequality for which algorithms have been implemented and tested. If time permits, we will consider the situation where priority rules are present and outline the close relationship between the resulting model and a continuous-time formulation of the dynamic traffic assignment with affine delay functions.

J.A.C. MARTINS

Email jmartins@civil.ist.utl.pt

Institute INSTITUTO SUPERIOR TECNICO,Portugal

Title A Complementarity Eigenproblem in the Stability Analysis of Finite Dimensional Elastic Systems with Frictional Contact

Co-authors A.Costa, I.Figueiredo, J.J�dice

Abstract The instability of configurations of static equilibrium of finite dimensional plane linearly elastic systems in frictional contact with a flat obstacle and subjected to constant applied forces was recently discussed by Martins, Barbarin, Raous and Costa (1998). Some of their results were generalized in Martins and Costa (1998) for the case of nonlinear elastic systems in frictional contact with curved obstacles. The typical situations in mind and the largest examples solved in the present paper involve finite element discretizations of linearly elastic bodies. In the first of the above papers it is shown that a necessary and sufficient condition for the occurrence of divergence instability along a constant admissible direction, is that an appropriate eigenproblem with the form of an inclusion or a variational inequality is solved with an appropriate sign of the corresponding real eigenvalue. In the same paper a necessary condition and a sufficient condition for this type of instability were presented, both of which can be easily checked. However, in many circumstances, those conditions do not yield sufficiently sharp results, in particular the necessary condition frequently gives a poor lower bound estimate for the onset of instability. For this reason we propose in the present paper a procedure for the numerical solution of the governing inclusion or variational eigenproblem. This is achieved by transforming that problem into a complementarity eigenproblem by means of an appropriate change of the contact related variables (Klarbring, 1997). The problem is subsequently transformed into a non--monotone {\it mixed nonlinear complementarity problem}, in which the unknown eigenvalue is treated as a nonnegative variable that is complementary with an additional variable involved in a normalizing constraint that prevents the trivial solution. The algorithm {\it PATH} (Dirkse and Ferris, 1995) has been successfully applied to solve some small sized examples discussed in Martins and Costa (1998) and some f.e.m. examples taken from Martins, Barbarin, Raous and Costa (1998).
REFERENCES
J.A.C. Martins, S. Barbarin, M. Raous, A. Pinto da Costa, {\it Dynamic stability of finite dimensional linearly elastic systems with unilateral contact and Coulomb friction} - {\bf Computer Methods in Applied Mechanics and Engineering} (accepted for publication).
J.A.C. Martins, A. Pinto da Costa, {\it Stability of finite dimensional nonlinear elastic systems with unilateral contact and friction} - {\bf Int. J. Solids Structures} (submitted and accepted in 1998).
A. Klarbring, {\it Contact, Friction, Discrete Mechanical Structures and Mathematical Programming} - Lecture notes for the CISM course {\bf Contact Problems: Theory, Methods, Applications}, 1997.
S.P. Dirkse, M.C. Ferris, {\it The PATH solver: A non--monotone stabilization scheme for mixed complementarity problems} - {\bf Optimization Methods and Software}, 5:123--156, 1995.

Email	jmartins@civil.ist.utl.pt
Institute	INSTITUTO SUPERIOR TECNICO,Portugal
Title	A Complementarity Eigenproblem in the Stability Analysis of Finite Dimensional Elastic Systems with Frictional Contact
Co-authors	A.Costa, I.Figueiredo, J.J�dice
Abstract	The instability of configurations of static equilibrium of finite dimensional plane linearly elastic systems in frictional contact with a flat obstacle and subjected to constant applied forces was recently discussed by Martins, Barbarin, Raous and Costa (1998). Some of their results were generalized in Martins and Costa (1998) for the case of nonlinear elastic systems in frictional contact with curved obstacles. The typical situations in mind and the largest examples solved in the present paper involve finite element discretizations of linearly elastic bodies. In the first of the above papers it is shown that a necessary and sufficient condition for the occurrence of divergence instability along a constant admissible direction, is that an appropriate eigenproblem with the form of an inclusion or a variational inequality is solved with an appropriate sign of the corresponding real eigenvalue. In the same paper a necessary condition and a sufficient condition for this type of instability were presented, both of which can be easily checked. However, in many circumstances, those conditions do not yield sufficiently sharp results, in particular the necessary condition frequently gives a poor lower bound estimate for the onset of instability. For this reason we propose in the present paper a procedure for the numerical solution of the governing inclusion or variational eigenproblem. This is achieved by transforming that problem into a complementarity eigenproblem by means of an appropriate change of the contact related variables (Klarbring, 1997). The problem is subsequently transformed into a non--monotone {\it mixed nonlinear complementarity problem}, in which the unknown eigenvalue is treated as a nonnegative variable that is complementary with an additional variable involved in a normalizing constraint that prevents the trivial solution. The algorithm {\it PATH} (Dirkse and Ferris, 1995) has been successfully applied to solve some small sized examples discussed in Martins and Costa (1998) and some f.e.m. examples taken from Martins, Barbarin, Raous and Costa (1998). REFERENCES J.A.C. Martins, S. Barbarin, M. Raous, A. Pinto da Costa, {\it Dynamic stability of finite dimensional linearly elastic systems with unilateral contact and Coulomb friction} - {\bf Computer Methods in Applied Mechanics and Engineering} (accepted for publication). J.A.C. Martins, A. Pinto da Costa, {\it Stability of finite dimensional nonlinear elastic systems with unilateral contact and friction} - {\bf Int. J. Solids Structures} (submitted and accepted in 1998). A. Klarbring, {\it Contact, Friction, Discrete Mechanical Structures and Mathematical Programming} - Lecture notes for the CISM course {\bf Contact Problems: Theory, Methods, Applications}, 1997. S.P. Dirkse, M.C. Ferris, {\it The PATH solver: A non--monotone stabilization scheme for mixed complementarity problems} - {\bf Optimization Methods and Software}, 5:123--156, 1995.

Todd S. Munson

Email tmunson@cs.wisc.edu

Institute University of Wisconsin

Title PATH and the MERGE Model

Co-authors Michael C. Ferris

Abstract We have recently encountered several new models with characteristics different from those in the MCPLIB collection. One of these is the MERGE model, an influential problem used to evaluate the effects of economic reform on greenhouse gas production. We outline the difficulties in solving this model, describe changes to the PATH code to overcome them, and detail how underlying problem structure can be communicated and exploited in the solver. Most of the mechanisms developed are applicable to general complementarity problems and polyhedral constrained variational inequalities and lead to performance improvements even on the MCPLIB and NETLIB collections.

Email	tmunson@cs.wisc.edu
Institute	University of Wisconsin
Title	PATH and the MERGE Model
Co-authors	Michael C. Ferris
Abstract	We have recently encountered several new models with characteristics different from those in the MCPLIB collection. One of these is the MERGE model, an influential problem used to evaluate the effects of economic reform on greenhouse gas production. We outline the difficulties in solving this model, describe changes to the PATH code to overcome them, and detail how underlying problem structure can be communicated and exploited in the solver. Most of the mechanisms developed are applicable to general complementarity problems and polyhedral constrained variational inequalities and lead to performance improvements even on the MCPLIB and NETLIB collections.

David R. Musicant

Email musicant@cs.wisc.edu

Institute University of Wisconsin

Title Nonlinear Data Discrimination via Generalized Support Vector Machines

Co-authors Olvi L. Mangasarian

Abstract The main purpose of this talk is to show that new formulations of support vector machines can generate nonlinear separating surfaces which can discriminate between elements of a given set better than a linear surface. The principal approach used is that of generalized support vector machines (GSVMs) which employ possibly indefinite kernels. The GSVM training procedure is carried out by either the simple successive overrelaxation (SOR) iterative method or by linear programming. This novel combination of powerful support vector machines with the highly effective SOR computational algorithm or with linear programming allows us to use a nonlinear surface to discriminate between elements of a dataset that belong to one of two categories. Numerical results on a number of datasets show improved testing set correctness, by as much as a factor of two, when comparing the nonlinear GSVM surface to a linear separating surface.

Email	musicant@cs.wisc.edu
Institute	University of Wisconsin
Title	Nonlinear Data Discrimination via Generalized Support Vector Machines
Co-authors	Olvi L. Mangasarian
Abstract	The main purpose of this talk is to show that new formulations of support vector machines can generate nonlinear separating surfaces which can discriminate between elements of a given set better than a linear surface. The principal approach used is that of generalized support vector machines (GSVMs) which employ possibly indefinite kernels. The GSVM training procedure is carried out by either the simple successive overrelaxation (SOR) iterative method or by linear programming. This novel combination of powerful support vector machines with the highly effective SOR computational algorithm or with linear programming allows us to use a nonlinear surface to discriminate between elements of a dataset that belong to one of two categories. Numerical results on a number of datasets show improved testing set correctness, by as much as a factor of two, when comparing the nonlinear GSVM surface to a linear separating surface.

Jiri V. Outrata

Email outrata@utia.cas.cz

Institute Czech Academy of Sciences

Title On mathematical programs with mixed complementarity constraints

Co-authors none

Abstract The contribution deals with optimization problems, where a parameter-dependent mixed complementarity problem arises among the constraints. Using the generalized differential calculus of B.Mordukhovich, we derive 1st-order necessary optimality conditions. A special attention is paid to the used constraint qualification. In particular, criteria are presented ensuring that this constraint qualification is fulfilled. Finally, we propose an exact penalty method for the numerical solution of such problems which is applicable under the mentioned constraint qualification.

Email	outrata@utia.cas.cz
Institute	Czech Academy of Sciences
Title	On mathematical programs with mixed complementarity constraints
Co-authors	none
Abstract	The contribution deals with optimization problems, where a parameter-dependent mixed complementarity problem arises among the constraints. Using the generalized differential calculus of B.Mordukhovich, we derive 1st-order necessary optimality conditions. A special attention is paid to the used constraint qualification. In particular, criteria are presented ensuring that this constraint qualification is fulfilled. Finally, we propose an exact penalty method for the numerical solution of such problems which is applicable under the mentioned constraint qualification.

Jong-Shi Pang

Email jsp@vicp1.mts.jhu.edu

Institute The Johns Hopkins University

Title Complementarity Problems: 35 Years Later

Co-authors

Abstract We give an overview of the main developments of complementarity problems since its inception 35 years ago, and discuss opportunities for continued research in this fruitful subject of mathematical programming.

Email	jsp@vicp1.mts.jhu.edu
Institute	The Johns Hopkins University
Title	Complementarity Problems: 35 Years Later
Co-authors
Abstract	We give an overview of the main developments of complementarity problems since its inception 35 years ago, and discuss opportunities for continued research in this fruitful subject of mathematical programming.

T. Parthasarathy

Email tps@isid1.isid.ac.in

Institute Indian Statistical Institute

Title On Connected Solution Sets of Linear Complementarity Problems

Co-authors

Abstract In this talk we consider the problem concerning the connectedness of solution set of Linear Complementarity Problem. Even if the matrix is a $P_0$-matrix, the solution set need not be connected in general. We give various sufficient conditions under which the solution set is connected.

Email	tps@isid1.isid.ac.in
Institute	Indian Statistical Institute
Title	On Connected Solution Sets of Linear Complementarity Problems
Co-authors
Abstract	In this talk we consider the problem concerning the connectedness of solution set of Linear Complementarity Problem. Even if the matrix is a $P_0$-matrix, the solution set need not be connected in general. We give various sufficient conditions under which the solution set is connected.

Liqun Qi

Email L.Qi@unsw.edu.au

Institute University of New South Wales

Title Solving Nonlinear Complementarity Problems with Neural Networks: A Reformulation Method Approach

Co-authors Li-Zhi Liao and Houduo Qi

Abstract In this paper, we present a neural network approach for solving nonlinear complementarity problems. The neural network model is derived from an unconstrained minimization reformulation of the complementarity problem. The existence and the convergence of the trajectory of the neural network are addressed in detail. In addition, we also explore the stability properties, such as the stability in the sense of Lyapunov, the asymptotic stability and the exponent stability, for the neural network model. The theory developed here is also valid for neural network models derived from a number of reformulation methods for nonlinear complementarity problems. Simulation results are also reported.

Email	L.Qi@unsw.edu.au
Institute	University of New South Wales
Title	Solving Nonlinear Complementarity Problems with Neural Networks: A Reformulation Method Approach
Co-authors	Li-Zhi Liao and Houduo Qi
Abstract	In this paper, we present a neural network approach for solving nonlinear complementarity problems. The neural network model is derived from an unconstrained minimization reformulation of the complementarity problem. The existence and the convergence of the trajectory of the neural network are addressed in detail. In addition, we also explore the stability properties, such as the stability in the sense of Lyapunov, the asymptotic stability and the exponent stability, for the neural network model. The theory developed here is also valid for neural network models derived from a number of reformulation methods for nonlinear complementarity problems. Simulation results are also reported.

Danny Ralph

Email danny@ms.unimelb.edu.au

Institute The University of Melbourne

Title Stability or Regularity of Nonsmooth Feasibility Problems

Co-authors

Abstract We consider approximation of a nonsmooth feasibility problem, e.g.~a system of nondifferentiable equalities and inequalities, and discuss its stability or (metric) regularity properties. This is directly motivated by the classical stability results of Graves-Lyusternik and Robinson which deal with smooth feasibility systems. Recent work by Dontchev and Kummer is especially valuable. An application is regularity of equilibrium constraints which appear in bilevel optimization; formulation of the lower-level equilibrium problem as a nonsmooth equation has better stability properties than the formulation that uses standard differentiable complementarity conditions.

Email	danny@ms.unimelb.edu.au
Institute	The University of Melbourne
Title	Stability or Regularity of Nonsmooth Feasibility Problems
Co-authors
Abstract	We consider approximation of a nonsmooth feasibility problem, e.g.~a system of nondifferentiable equalities and inequalities, and discuss its stability or (metric) regularity properties. This is directly motivated by the classical stability results of Graves-Lyusternik and Robinson which deal with smooth feasibility systems. Recent work by Dontchev and Kummer is especially valuable. An application is regularity of equilibrium constraints which appear in bilevel optimization; formulation of the lower-level equilibrium problem as a nonsmooth equation has better stability properties than the formulation that uses standard differentiable complementarity conditions.

Michel Rivier

Email michel.rivier@iit.upco.es

Institute Instituto de Investigacion Tecnologica, Universidad Pontificia Comillas, SPAIN

Title A Generation Operation Planning Model in Deregulated Electricity Markets based on the Complementary Problem

Co-authors Mariano Ventosa, Andres Ramos

Abstract Throughout the world, the electricity industry is currently undergoing a significant restructuring toward deregulation and competition. In the new context, generation of electricity becomes an unbundled activity subject to a strong liberalization in which both expansion and operation decisions no longer depend upon administrative and centralized procedures -usually based on cost minimization schemes-, but rather on the managerial decisions of the generation companies looking forward to maximize their own profits. Therefore, in the new deregulated power markets, electric firms assume much more risk and become highly responsible for their own decisions. Companies need decision support models that fulfill these new requirements. An important developmental effort is needed either to adapt the traditional mode based on cost minimization schemes to the new context or to design new models and tools that explicitly model the electricity generation market behavior. The market behavior will depend on companies' production cost profiles, on companies' technical operation constraints, and on the economic market equilibria resulting from the interaction of all market participants. Several approaches dealing with this problem have been proposed so far depending on the time horizon, the generation technologies and the operation constraints considered. This paper proposes a new methodology for long term operation planning models, fully adapted to represent an annual or hyperannual generation scheduling in a competitive framework. The method states explicitly the market equilibrium by formulating analytically the equations defining the optimal behavior of any generation company. The technical constraints relevant for the time scope studied are also taken into account. The subsequent system of nonlinear equations has the structure of a Complementary Problem (CP) and can be solved directly. This paper presents therefore an CP application to solve electrical generation market models. The model has been implemented in GAMS language, and the CP solvers are MILES and PATH. The model has been applied to a large-scale electric energy system such as the Spanish one. The detailed analysis of the optimality conditions, carefully developed to apply this methodology, has also allowed a better understanding of the role of each generation technology in reaching the maximum profit policy for each company.

Email	michel.rivier@iit.upco.es
Institute	Instituto de Investigacion Tecnologica, Universidad Pontificia Comillas, SPAIN
Title	A Generation Operation Planning Model in Deregulated Electricity Markets based on the Complementary Problem
Co-authors	Mariano Ventosa, Andres Ramos
Abstract	Throughout the world, the electricity industry is currently undergoing a significant restructuring toward deregulation and competition. In the new context, generation of electricity becomes an unbundled activity subject to a strong liberalization in which both expansion and operation decisions no longer depend upon administrative and centralized procedures -usually based on cost minimization schemes-, but rather on the managerial decisions of the generation companies looking forward to maximize their own profits. Therefore, in the new deregulated power markets, electric firms assume much more risk and become highly responsible for their own decisions. Companies need decision support models that fulfill these new requirements. An important developmental effort is needed either to adapt the traditional mode based on cost minimization schemes to the new context or to design new models and tools that explicitly model the electricity generation market behavior. The market behavior will depend on companies' production cost profiles, on companies' technical operation constraints, and on the economic market equilibria resulting from the interaction of all market participants. Several approaches dealing with this problem have been proposed so far depending on the time horizon, the generation technologies and the operation constraints considered. This paper proposes a new methodology for long term operation planning models, fully adapted to represent an annual or hyperannual generation scheduling in a competitive framework. The method states explicitly the market equilibrium by formulating analytically the equations defining the optimal behavior of any generation company. The technical constraints relevant for the time scope studied are also taken into account. The subsequent system of nonlinear equations has the structure of a Complementary Problem (CP) and can be solved directly. This paper presents therefore an CP application to solve electrical generation market models. The model has been implemented in GAMS language, and the CP solvers are MILES and PATH. The model has been applied to a large-scale electric energy system such as the Spanish one. The detailed analysis of the optimality conditions, carefully developed to apply this methodology, has also allowed a better understanding of the role of each generation technology in reaching the maximum profit policy for each company.

Sherman Robinson

Email S.ROBINSON@CGIAR.ORG

Institute CGIAR

Title Parameter Estimation Using Maximum Entropy Econometrics in a Data-Poor Environment

Co-authors Rebecca Harris

Abstract Maximum entropy econometric methods are starting to be used widely in economics for parameter estimation in "data poor" environments. The estimation approach is based on information theory, following the work of Shannon, and involves either maximizing an entropy measure of information (Shannon entropy) in a set of discrete probabilities or minimizing the entropy difference between an estimated and prior discrete distribution of probabilities (Kullback-Leibler cross-entropy measure), given knowledge expressed as a set of constraints on the estimated probabilities. The estimation problem cannot be solved analytically --there is no closed form solution. The problem is formulated as a Kuhn-Tucker nonlinear programming (NLP) problem and solved numerically using standard NLPpackages. In most economic estimation problems, however, the NLP problem is both large and badly scaled, and standard solvers such as MINOS and CONOPT do not work well. In this paper, we describe experience converting the NLP problem to a mixed complementarity problem (MCP) and solving it using the PATH solver. Experience indicates that the PATH solver does very well when compared to standard NLP solvers.

Email	S.ROBINSON@CGIAR.ORG
Institute	CGIAR
Title	Parameter Estimation Using Maximum Entropy Econometrics in a Data-Poor Environment
Co-authors	Rebecca Harris
Abstract	Maximum entropy econometric methods are starting to be used widely in economics for parameter estimation in "data poor" environments. The estimation approach is based on information theory, following the work of Shannon, and involves either maximizing an entropy measure of information (Shannon entropy) in a set of discrete probabilities or minimizing the entropy difference between an estimated and prior discrete distribution of probabilities (Kullback-Leibler cross-entropy measure), given knowledge expressed as a set of constraints on the estimated probabilities. The estimation problem cannot be solved analytically --there is no closed form solution. The problem is formulated as a Kuhn-Tucker nonlinear programming (NLP) problem and solved numerically using standard NLPpackages. In most economic estimation problems, however, the NLP problem is both large and badly scaled, and standard solvers such as MINOS and CONOPT do not work well. In this paper, we describe experience converting the NLP problem to a mixed complementarity problem (MCP) and solving it using the PATH solver. Experience indicates that the PATH solver does very well when compared to standard NLP solvers.

Stephen M. Robinson

Email smrobins@facstaff.wisc.edu

Institute University of Wisconsin-Madison

Title Composition duality and complementarity

Co-authors

Abstract The recently proposed method of composition duality provides a technique for dualizing very general multifunction inclusions. When it is specialized to variational inequalities, additional structure appears and a number of previously known duality schemes can be recovered as special cases. These include in particular Rockafellar's perturbational duality for convex programming problems. In this talk we give a brief introduction to composition duality and then explore some ways in which it can be applied to complementarity problems.

Email	smrobins@facstaff.wisc.edu
Institute	University of Wisconsin-Madison
Title	Composition duality and complementarity
Co-authors
Abstract	The recently proposed method of composition duality provides a technique for dualizing very general multifunction inclusions. When it is specialized to variational inequalities, additional structure appears and a number of previously known duality schemes can be recovered as special cases. These include in particular Rockafellar's perturbational duality for convex programming problems. In this talk we give a brief introduction to composition duality and then explore some ways in which it can be applied to complementarity problems.

Thomas F. Rutherford

Email rutherford@colorado.edu

Institute University of Colorado

Title Dynamic Economic Equilibrium Modeling in a Complementarity Format: Formulations, Applications, and Test Problems

Co-authors

Abstract This paper surveys four recent applications of dynamic general equilibrium analysis for economic policy analysis which rely upon the complementarity programming format for model specification and solution. The purpose of the paper is to outline a range of new models which are of interest to economists and to provide test problems illustrating the numerical difficulties they represent.
Models included in this review are:
(i) a global (multi-sectoral, multi-regional) model of carbon emissions abatement, international trade and economic growth;
(ii) a multi-sectoral, open-economy overlapping generations model designed for studying the intergenerational equity effects of environmental tax policy,
(iii) a model of trade policy and endogenous growth, and
(iv) a model of foreign direct investment in skill-intensive services and human capital formation in a transition economy.
A primary objective of this survey is provide a set of clearly documented test problems for complementarity algorithm developers. Several unsolved instances of these models are provided, as well as several problems which are not easily solved on defaults.

Email	rutherford@colorado.edu
Institute	University of Colorado
Title	Dynamic Economic Equilibrium Modeling in a Complementarity Format: Formulations, Applications, and Test Problems
Co-authors
Abstract	This paper surveys four recent applications of dynamic general equilibrium analysis for economic policy analysis which rely upon the complementarity programming format for model specification and solution. The purpose of the paper is to outline a range of new models which are of interest to economists and to provide test problems illustrating the numerical difficulties they represent. Models included in this review are: (i) a global (multi-sectoral, multi-regional) model of carbon emissions abatement, international trade and economic growth; (ii) a multi-sectoral, open-economy overlapping generations model designed for studying the intergenerational equity effects of environmental tax policy, (iii) a model of trade policy and endogenous growth, and (iv) a model of foreign direct investment in skill-intensive services and human capital formation in a transition economy. A primary objective of this survey is provide a set of clearly documented test problems for complementarity algorithm developers. Several unsolved instances of these models are provided, as well as several problems which are not easily solved on defaults.

Stefan Scholtes

Email s.scholtes@jims.cam.ac.uk

Institute University of Cambridge

Title How typical are regular MPECs?

Co-authors Michael Stohr

Abstract A variety of regularity conditions for MPECs, many of which are similar to those known from standard nonlinear programming, have been introduced in the recent past. Their main purpose is to distinguish tractable from intractable MPECs and they are used prominently in convergence theorems for MPEC algorithms. A typical example is the linear independence condition which allows an easy verification of B-stationarity. In this talk we will discuss how typical some of these conditions are. The basis for our study is an extension of Sard's theorem to MPEC constraints. This allows a generalization of Jongen's genericity analysis from standard nonlinear programs to MPECs.

Yves Smeers

Email smeers@core.ucl.ac.be

Institute CORE, Universite catholique de Louvain

Title Variational inequality models of restructured electricity systems

Co-authors Olivier Daxhelet

Abstract We consider organisations of the electricity systems that differ by the type of agents involved, the institutional design and transmission pricing. We relate these organisations to various restructuring approaches currently in place or being put in place in the US and in Europe. We also discuss these models by reference to the literature on the subject. These different models are cast in a common variational inequality framework for numerical treatment. Numerical results are reported for some of these organisations on real world networks.

Michael V. Solodov

Email solodov@impa.br

Institute IMPA, Rio de Janeiro

Title A class of separation--projection algorithms for (pseudo-)monotone variational inequalities

Co-authors

Abstract We describe a fairly broad class of algorithms for (pseudo-)monotone variational inequalities based on the strategy of generating a hyperplane which separates the current iterate from the solution set. We show that this strategy is useful for ensuring global convergence of some iterative schemes which otherwise may not converge; and also for relaxing tolerance conditions in solving the subproblems within some convergent methods. The algorithms in this class differ in the tools which are used to construct the separating hyperplane. Our general scheme subsumes an extragradient-type projection method, a globally and locally superlinearly convergent Josephy-Newton-type method, a certain minimization-based method, and some splitting techniques.

David Stewart

Email dstewart@math.uiowa.edu

Institute University of Iowa

Title Recent news on rigid-body dynamics

Co-authors

Abstract Recent results on formulations, theory and computation for rigid body dynamics will be presented. These include nonlinear complementarity formulations (based in part on work with J.-S. Pang), convergence theory, and variants on the scheme presented at ICCP95. Some open questions will be posed.

Francis Tin-Loi

Email f.tinloi@unsw.edu.au

Institute School of Civil and Environmental Engineering, University of New South Wales

Title Identification of fracture parameters as an MPEC

Co-authors Giulio Maier and Gabriella Bolzon

Abstract An important requirement in the safety assessment of structures made o f quasibrittle (concrete-like) materials is the engineer's ability to simulate the fracture processes that may occur. The discrete cohesive crack model, in which all nonlinearities are relegated to a locus of potential crack, is widely used for this purpose. Unfortunately, the parameters characterizing this model cannot be obtained directly by experiment. The presentation focuses on an inverse approach aimed at identifying the necessary parameters, given some information on the load-displacement response from a standard test. The formulation takes the form of an MPEC. We also present some numerical results, albeit still preliminary, on various simple, essentially NLP-based, schemes for solving this MPEC. Illustration is by means of actual test data, modeled within GAMS, on a composite polymeric material.

Paul Tseng

Email tseng@math.washington.edu

Institute University of Washington

Title Smoothing methods for Semidefinite Complementarity Problems

Co-authors Xin Chen

Abstract We study extension of some smoothing methods to complementarity problems defined on the space of symmetric matrices. Issues such as existence of Newton direction and convergence will be discussed. Preliminary numerical experience will also be presented.

Michael Ulbrich

Email mulbrich@mathematik.tu-muenchen.de

Institute Technische Universitaet Muenchen

Title Nonsmooth Projected Newton Methods for Nonlinear Mixed Complementarity Problems in Function Space

Co-authors

Abstract Many problems in engineering, economics, and sciences can be modeled as problems involving complementarity conditions. Often, these problems originally live in infinite-dimensional function spaces. In particular, this applies to obstacle, continuum contact, optimal control, and structural continuum design problems. In this talk we present and analyze a Newton-type method with projection for the solution of infinite-dimensional mixed nonlinear complementarity problems (MCP) in the function space $L^p$. Hereby, we use NCP-functions to reformulate the MCP as a nonsmooth nonlinear operator equation. On the basis of an appropriately chosen pseudoderivative of the underlying operator, a Newton-like iteration is derived. We augment this iteration by a projection to maintain feasibility with respect to the nonnegativity constraints. We prove that near a regular solution the resulting iteration mapping is two-norm contracting with superlinear rate. Hereby, the two-norm approach is required to compensate the non-equivalence of norms in infinite dimensions. In order to obtain a superlinearly convergent algorithm, a smoothing step is introduced to close this gap of norms. The availability of an infinite-dimensional convergence theory is of significant importance for the robustness of the algorithm with respect to the mesh size of the numerical discretization. Numerical results confirm our theoretical findings.

Stephen Wright

Email wright@mcs.anl.gov

Institute Argonne National Laboratory

Title Using Complementarity and Optimization Methods in Statistics

Co-authors

Abstract Regression problems in statistics have traditionally been solved by using least squares algorithms, where regularization are used often to combat the ill conditioning inherent in many problems. Recently, regularization techniques that take the form of special norm constraints on the solutions have been investigated. We show how the resulting problems can be formulated as optimization or complementarity problems and solved via interior-point techniques. We focus on a simultaneous variable selection technique that was investigated in recent work with B. Turlach and W. Venables. We also outline the optimization issues in the use of estimators such as $\ell_1$ and Huber's robust estimator.

Nobuo Yamashita

Email nobuo@kuamp.kyoto-u.ac.jp

Institute Kyoto University

Title The Proximal Point Method for the $P_0$ Complementarity Problem

Co-authors Junji Imai and Masao Fukushima

Abstract In this talk we propose a proximal point algorithm (PPA) for the nonlinear complementarity problem (NCP) with a $P_0$ function. By using the Mountain Pass Theorem, we show that the proposed algorithm has a global convergence property when $F$ is a continuously differentiable $P_0$ function and the solution set of NCP is bounded. This is the first convergence result for PPA designed to solve $P_0$ complementarity problems. Moreover we show that it has a superlinear convergence property under appropriate conditions. Particularly we give conditions under which a single Newton iteration for subproblems suffices to ensure convergence of the algorithm.

Thaleia Zariphopoulou

Email zariphop@math.wisc.edu

Institute University of Wisconsin

Title Stochastic Optimization and Asset Valuation in Incomplete Markets

Co-authors

Abstract This talk is an overview of asset valuation models in Mathematical Finance and Insurance Theory in incomplete markets. The incompleteness stems from stochastic volatility, trading constraints, transaction costs and incomplete information. These asset pricing models give rise to (singular) stochastic control problems and stochastic differential games whose value functions are related to optimal expected utilities, derivative prices and hedging strategies. A novel approach for asset valuation based on the propagation of the relevant level curves will be also introduced.

Michael Ferris
Computer Sciences Department
University of Wisconsin, Madison
ferris@cs.wisc.edu

Olvi Mangasarian
Computer Sciences Department
University of Wisconsin, Madison
olvi@cs.wisc.edu

Jong-Shi Pang
Department of Mathematical Sciences
The Johns Hopkins University, Baltimore
jsp@vicp.mts.jhu.edu

Email	s.scholtes@jims.cam.ac.uk
Institute	University of Cambridge
Title	How typical are regular MPECs?
Co-authors	Michael Stohr
Abstract	A variety of regularity conditions for MPECs, many of which are similar to those known from standard nonlinear programming, have been introduced in the recent past. Their main purpose is to distinguish tractable from intractable MPECs and they are used prominently in convergence theorems for MPEC algorithms. A typical example is the linear independence condition which allows an easy verification of B-stationarity. In this talk we will discuss how typical some of these conditions are. The basis for our study is an extension of Sard's theorem to MPEC constraints. This allows a generalization of Jongen's genericity analysis from standard nonlinear programs to MPECs.

Email	smeers@core.ucl.ac.be
Institute	CORE, Universite catholique de Louvain
Title	Variational inequality models of restructured electricity systems
Co-authors	Olivier Daxhelet
Abstract	We consider organisations of the electricity systems that differ by the type of agents involved, the institutional design and transmission pricing. We relate these organisations to various restructuring approaches currently in place or being put in place in the US and in Europe. We also discuss these models by reference to the literature on the subject. These different models are cast in a common variational inequality framework for numerical treatment. Numerical results are reported for some of these organisations on real world networks.

Email	solodov@impa.br
Institute	IMPA, Rio de Janeiro
Title	A class of separation--projection algorithms for (pseudo-)monotone variational inequalities
Co-authors
Abstract	We describe a fairly broad class of algorithms for (pseudo-)monotone variational inequalities based on the strategy of generating a hyperplane which separates the current iterate from the solution set. We show that this strategy is useful for ensuring global convergence of some iterative schemes which otherwise may not converge; and also for relaxing tolerance conditions in solving the subproblems within some convergent methods. The algorithms in this class differ in the tools which are used to construct the separating hyperplane. Our general scheme subsumes an extragradient-type projection method, a globally and locally superlinearly convergent Josephy-Newton-type method, a certain minimization-based method, and some splitting techniques.

Email	dstewart@math.uiowa.edu
Institute	University of Iowa
Title	Recent news on rigid-body dynamics
Co-authors
Abstract	Recent results on formulations, theory and computation for rigid body dynamics will be presented. These include nonlinear complementarity formulations (based in part on work with J.-S. Pang), convergence theory, and variants on the scheme presented at ICCP95. Some open questions will be posed.

Email	f.tinloi@unsw.edu.au
Institute	School of Civil and Environmental Engineering, University of New South Wales
Title	Identification of fracture parameters as an MPEC
Co-authors	Giulio Maier and Gabriella Bolzon
Abstract	An important requirement in the safety assessment of structures made o f quasibrittle (concrete-like) materials is the engineer's ability to simulate the fracture processes that may occur. The discrete cohesive crack model, in which all nonlinearities are relegated to a locus of potential crack, is widely used for this purpose. Unfortunately, the parameters characterizing this model cannot be obtained directly by experiment. The presentation focuses on an inverse approach aimed at identifying the necessary parameters, given some information on the load-displacement response from a standard test. The formulation takes the form of an MPEC. We also present some numerical results, albeit still preliminary, on various simple, essentially NLP-based, schemes for solving this MPEC. Illustration is by means of actual test data, modeled within GAMS, on a composite polymeric material.

Email	tseng@math.washington.edu
Institute	University of Washington
Title	Smoothing methods for Semidefinite Complementarity Problems
Co-authors	Xin Chen
Abstract	We study extension of some smoothing methods to complementarity problems defined on the space of symmetric matrices. Issues such as existence of Newton direction and convergence will be discussed. Preliminary numerical experience will also be presented.

Email	mulbrich@mathematik.tu-muenchen.de
Institute	Technische Universitaet Muenchen
Title	Nonsmooth Projected Newton Methods for Nonlinear Mixed Complementarity Problems in Function Space
Co-authors
Abstract	Many problems in engineering, economics, and sciences can be modeled as problems involving complementarity conditions. Often, these problems originally live in infinite-dimensional function spaces. In particular, this applies to obstacle, continuum contact, optimal control, and structural continuum design problems. In this talk we present and analyze a Newton-type method with projection for the solution of infinite-dimensional mixed nonlinear complementarity problems (MCP) in the function space $L^p$. Hereby, we use NCP-functions to reformulate the MCP as a nonsmooth nonlinear operator equation. On the basis of an appropriately chosen pseudoderivative of the underlying operator, a Newton-like iteration is derived. We augment this iteration by a projection to maintain feasibility with respect to the nonnegativity constraints. We prove that near a regular solution the resulting iteration mapping is two-norm contracting with superlinear rate. Hereby, the two-norm approach is required to compensate the non-equivalence of norms in infinite dimensions. In order to obtain a superlinearly convergent algorithm, a smoothing step is introduced to close this gap of norms. The availability of an infinite-dimensional convergence theory is of significant importance for the robustness of the algorithm with respect to the mesh size of the numerical discretization. Numerical results confirm our theoretical findings.

Email	wright@mcs.anl.gov
Institute	Argonne National Laboratory
Title	Using Complementarity and Optimization Methods in Statistics
Co-authors
Abstract	Regression problems in statistics have traditionally been solved by using least squares algorithms, where regularization are used often to combat the ill conditioning inherent in many problems. Recently, regularization techniques that take the form of special norm constraints on the solutions have been investigated. We show how the resulting problems can be formulated as optimization or complementarity problems and solved via interior-point techniques. We focus on a simultaneous variable selection technique that was investigated in recent work with B. Turlach and W. Venables. We also outline the optimization issues in the use of estimators such as $\ell_1$ and Huber's robust estimator.

Email	nobuo@kuamp.kyoto-u.ac.jp
Institute	Kyoto University
Title	The Proximal Point Method for the $P_0$ Complementarity Problem
Co-authors	Junji Imai and Masao Fukushima
Abstract	In this talk we propose a proximal point algorithm (PPA) for the nonlinear complementarity problem (NCP) with a $P_0$ function. By using the Mountain Pass Theorem, we show that the proposed algorithm has a global convergence property when $F$ is a continuously differentiable $P_0$ function and the solution set of NCP is bounded. This is the first convergence result for PPA designed to solve $P_0$ complementarity problems. Moreover we show that it has a superlinear convergence property under appropriate conditions. Particularly we give conditions under which a single Newton iteration for subproblems suffices to ensure convergence of the algorithm.

Email	zariphop@math.wisc.edu
Institute	University of Wisconsin
Title	Stochastic Optimization and Asset Valuation in Incomplete Markets
Co-authors
Abstract	This talk is an overview of asset valuation models in Mathematical Finance and Insurance Theory in incomplete markets. The incompleteness stems from stochastic volatility, trading constraints, transaction costs and incomplete information. These asset pricing models give rise to (singular) stochastic control problems and stochastic differential games whose value functions are related to optimal expected utilities, derivative prices and hedging strategies. A novel approach for asset valuation based on the propagation of the relevant level curves will be also introduced.