Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben

2001 | Buch

Approximating Maximum Stable Set and Minimum Graph Coloring Problems with the Positive Semidefinite Relaxation Kapitel lesen Erstes Kapitel lesen

Complementarity: Applications, Algorithms and Extensions

herausgegeben von: Michael C. Ferris, Olvi L. Mangasarian, Jong-Shi Pang

Verlag: Springer US

Buchreihe : Applied Optimization

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This volume presents state-of-the-art complementarity applications, algorithms, extensions and theory in the form of eighteen papers. These at the International Conference on Com­ invited papers were presented plementarity 99 (ICCP99) held in Madison, Wisconsin during June 9-12, 1999 with support from the National Science Foundation under Grant DMS-9970102. Complementarity is becoming more widely used in a variety of appli­ cation areas. In this volume, there are papers studying the impact of complementarity in such diverse fields as deregulation of electricity mar­ kets, engineering mechanics, optimal control and asset pricing. Further­ more, application of complementarity and optimization ideas to related problems in the burgeoning fields of machine learning and data mining are also covered in a series of three articles. In order to effectively process the complementarity problems that arise in such applications, various algorithmic, theoretical and computational extensions are covered in this volume. Nonsmooth analysis has an im­ portant role to play in this area as can be seen from articles using these tools to develop Newton and path following methods for constrained nonlinear systems and complementarity problems. Convergence issues are covered in the context of active set methods, global algorithms for pseudomonotone variational inequalities, successive convex relaxation and proximal point algorithms. Theoretical contributions to the connectedness of solution sets and constraint qualifications in the growing area of mathematical programs with equilibrium constraints are also presented. A relaxation approach is given for solving such problems. Finally, computational issues related to preprocessing mixed complementarity problems are addressed.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Approximating Maximum Stable Set and Minimum Graph Coloring Problems with the Positive Semidefinite Relaxation
Abstract
We compute approximate solutions to the maximum stable set problem and the minimum graph coloring problem using a positive semidefinite relaxation. The positive semidefinite programs are solved using an implementation of the dual scaling algorithm that takes advantage of the sparsity inherent in most graphs and the structure inherent in the problem formulation. Prom the solution to the relaxation, we apply a randomized algorithm to find approximate maximum stable sets and a modification of a popular heuristic to find graph colorings. We obtained high quality answers for graphs with over 1000 vertices and over 6000 edges.
S. J. Benson, Y. Ye
Chapter 2. Nonmonotone Path Following Methods for Nonsmooth Equations and Complementarity Problems
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. The method is specialized to solve complementarity problems through the use of MCP functions and associated smoothers.
Stephen C. Billups, Adam L. Speight, Layne T. Watson
Chapter 3. Scalable Probabilistic Clustering
Abstract
The Expectation-Maximization (EM) algorithm is a popular approach to probabilistic database clustering. A database of observations is clustered by identifying k sub-populations and summarizing each sub- population with a model or probability density function. The EM algorithm is an approach that iteratively estimates the memberships of the observations in each cluster and the parameters of the k density functions for each cluster. Typical EM implementations require a full database scan at each iteration and the number of iterations required to converge is arbitrary. For large databases, these scans become prohibitively expensive. We present a scalable implementation of the EM algorithm based upon identifying regions of the data that are compressible and regions that must be maintained in memory. The approach operates within the confines of a limited main memory buffer. Data resolution is preserved to the extent possible based upon the size of the memory buffer and the fit of the current clustering model to the data. We extend the framework to update multiple cluster models simultaneously. Computational tests indicate that this scalable scheme outperforms sampling-based and incremental approaches — the straightforward alternatives to “scaling” existing traditional in-memory implementations to large databases.
P. S. Bradley, U. M. Fayyad, C. A. Reina
Chapter 4. A Complementarity Eigenproblem in the Stability Analysis of Finite Dimensional Elastic Systems with Frictional Contact
Abstract
In this paper a mixed complementarity eigenproblem (MCEIP) is formulated and a method is proposed for its numerical solution. This mathematical problem is motivated by the study of divergence instabilities of static equilibrium states of finite dimensional mechanical systems with unilateral frictional contact. The complementarity eigenproblem is solved by transforming it into a non-monotone mixed complementarity problem (MCP), which is then solved by using the algorithm PATH. The proposed method is used to study some small sized examples and some large finite element problems.
A. Pinto da Costa, I. N. Figueiredo, J. J. Júdice, J. A. C. Martins
Chapter 5. Variational Inequality Models of Restructured Electricity Systems
Abstract
Electricity systems are being restructured throughout the world (see [18, 34] for general overviews of the phenomenon). The literature on the subject is now plentiful; it is directed to both academic and professional audiences. It embraces texts on systems descriptions, antitrust and regulatory cases, as well as economic or computational models. Some publications like the Electricity Journal appear to be almost entirely devoted to the various issues generated by the reorganization of the electricity industry. This explosion of interest is due to a major feature of electricity restructuring: the overall process appears to be unusually difficult (see [31] for a discussion of the origins of these difficulties). As a result different paradigms have been proposed and no two systems, even when inspired by the same principles, are identical. Experience with existing systems is now growing but many questions remain. This diversity of paradigms and situations, with no clear cut indication of what is right and wrong, is at the origin of this explosion of interest.
Olivier Daxhelet, Yves Smeers
Chapter 6. Optimization Approaches to Semi-Supervised Learning
Abstract
We examine mathematical models for semi-supervised support vector machines (S3VM). Given a training set of labeled data and a working set of unlabeled data, S3VM constructs a support vector machine using both the training and working sets. We use S3VM to solve the transductive inference problem posed by Vapnik. In transduction, the task is to estimate the value of a classification function at the given points in the working set. This contrasts with inductive inference which estimates the classification function at all possible values. We propose a general S3VM model that minimizes both the misclassification error and the function capacity based on all the available data. Depending on how poorly-estimated unlabeled data are penalized, different mathematical models result. We examine several practical algorithms for solving these model. The first approach utilizes the S3VM model for 1-norm linear support vector machines converted to a mixed-integer program (MIP). A global solution of the MIP is found using a commercial integer programming solver. The second approach uses a nonconvex quadratic program. Variations of block-coordinate-descent algorithms are used to find local solutions of this problem. Using this MIP within a local learning algorithm produced the best results. Our experimental study on these statistical learning methods indicates that incorporating working data can improve generalization.
Ayhan Demiriz, Kristin P. Bennett
Chapter 7. Preprocessing Complementarity Problems
Abstract
Preprocessing techniques are extensively used in the linear and integer programming communities as a means to improve model formulation by reducing size and complexity. Adaptations and extensions of these methods for use within the complementarity framework are detailed and shown to be effective on practical models. The preprocessor developed is comprised of two phases. The first recasts a complementarity problem as a variational inequality over a polyhedral set and exploits the uncovered structure to fix variables and remove constraints. The second discovers information about the function and utilizes complementarity theory to eliminate variables. The methodology is successfully employed to preprocess several models.
Michael C. Ferris, Todd S. Munson
Chapter 8. On the Connectedness of Solution Sets of Parametrized Equations and of Solution Sets in Linear Complementarity Problems
Abstract
In this article, we prove, under certain conditions, the connectedness of sets of the form {x: f(x, y) = 0, y ∈ E} where f is a function with x varying over an open set in R n and the parameter y varying over a topological space. Based on this, we show that the partitioned matrix
$$M = \left[ \begin{gathered} A\,\,\,\,\,\,B \hfill \\ B\,\,\,\,\,\,D \hfill \\\end{gathered} \right]$$
is (LCP) connected (i.e., for all q, the solution set of LCP(q, M) is connected) when A ∈ P 0 ∩ Q, C = 0, and D is connected. We also show that (a) any nonnegative P 0 ∩ Q 0-matrix is connected and (b) any matrix M partitioned as above with C and D nonnegative, and A ∈ P 0 ∩ Q is connected.
M. Seetharama Gowda, G. S. R. Murthy, T. Parthasarathy
Chapter 9. An Active Set-Type Newton Method for Constrained Nonlinear Systems
Abstract
We consider the problem of finding a solution of a nonlinear system of equations subject to some box constraints. To this end, we introduce a new active set-type Newton method. This method is shown to be globally convergent in the sense that every accumulation point is a stationary point of a corresponding box constrained optimization problem. Moreover, the method is locally superlinearly or quadratically convergent under a suitable regularity condition. Furthermore the method generates feasible iterates and has to solve only one linear system of equations at each iteration. Due to our active set strategy, this linear system is of reduced dimension. Some preliminary numerical results are included.
Christian Kanzow
Chapter 10. Mathematical Programming in Engineering Mechanics: Some Current Problems
Abstract
The application of mathematical programming methods in a variety of practically motivated engineering mechanics problems provides a fertile field for interdisciplinary interaction between the mathematical programming and engineering communities. This paper briefly outlines several topical problems in engineering mechanics involving the use of mathematical programming techniques. The intention is to attract the attention of mathematical programming experts to some of the still open questions in the intersection of the two fields.
G. Maier, G. Bolzon, F. Tin-Loi
Chapter 11. Data Discrimination via Nonlinear Generalized Support Vector Machines
Abstract
The main purpose of this paper 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) [21] which employ possibly indefinite kernels. The GSVM training procedure is carried out by either a simple successive overrelaxation (SOR) [22] iterative method or by linear programming. This novel combination of powerful support vector machines [28, 7] with the highly effective SOR computational algorithm [19, 20, 17], 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.
O. L. Mangasarian, David R. Musicant
Chapter 12. On Constraint Qualifications for Mathematical Programs with Mixed Complementarity Constraints
Abstract
The contribution concerns mathematical programs, where a mixed complementarity problem arises as a side constraint. The attention is paid above all to optimality conditions and to the respective constraint qualifications. In addition, we propose an exact penalty approach to the numerical solution of such problems.
J. V. Outrata
Chapter 13. A Generation Operation Planning Model in Deregulated Electricity Markets Based on the Complementarity Problem
Abstract
Throughout the world, the electricity industry is currently undergoing a significant restructuring process toward deregulation and competition. In the new deregulated power markets, electric firms assume much more risk and become highly responsible for their own decisions, and therefore they need decision-support models that fulfill their new requirements. This paper proposes a new approach for long-term operation-planning models, fully adapted to represent an annual or hyperannual power generation scheduling in a competitive framework. The method explicitly states the Cournot market equilibrium by analytically formulating the equations defining the optimal behavior of any strategic generation company. The technical constraints relevant to the time scope studied are also taken into account. The subsequent system of non-linear equations has the structure of a Complementarity Problem and can be solved directly. The model includes a technologically detailed representation of the generation firms, the treatment of hydro operations and of non-linear cost functions. A detailed case study illustrates how this model works, and how different generation technologies are optimally operated. An application to the Spanish electric market is also briefly presented in order to show that the model is also able to deal with large-scale electric systems.
Michel Rivier, Mariano Ventosa, Andrés Ramos, Francisco Martínez-Córcoles, Ángel Chiarri Toscano
Chapter 14. A Class of Globally Convergent Algorithms for Pseudomonotone Variational Inequalities
Abstract
We describe a fairly broad class of algorithms for solving variational inequalities, global convergence of which is based on the strategy of generating a hyperplane separating the current iterate from the solution set. The methods are shown to converge under very mild assumptions. Specifically, the problem mapping is only assumed to be continuous and pseudomonotone with respect to at least one solution. The strategy to obtain (super)linear rate of convergence is also discussed. 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 super linearly convergent Josephy-Newton-type method, a certain minimization-based method, and a splitting technique.
M. V. Solodov
Chapter 15. Successive Convex Relaxation Approach to Bilevel Quadratic Optimization Problems
Abstract
The bilevel quadratic optimization problem is an instance of a hierarchical decision process where the lower level constraint set is dependent on decisions taken at the upper level. By replacing the lower level problem by the corresponding KKT optimality condition, the entire problem is transformed into a single level yet non-convex quadratic optimization problem involving the complementarity condition. In this paper, we adopt the successive convex relaxation method given by Kojima and Tunçel for approximating a nonconvex feasible region. By further exploiting the special structure of the bilevel quadratic optimization problem, we present new techniques which enable the efficient implementation of the successive convex relaxation method for the problem. The performance of these techniques is tested in a number of problems, and compared with some other procedures.
Akiko Takeda, Masakazu Kojima
Chapter 16. On a Nonsmooth Newton Method for Nonlinear Complementarity Problems in Function Space with Applications to Optimal Control
Abstract
Many applications in mathematical modeling and optimal control lead to problems that are posed in function spaces and contain pointwise complementarity conditions. In this paper, a projected Newton method for nonlinear complementarity problems in the infinite dimensional function space L p is proposed and analyzed. Hereby, an NCP-function is used to reformulate the problem as a nonsmooth operator equation. The method stays feasible with respect to prescribed bound-constraints. The convergence analysis is based on semismoothness results for superposition operators in function spaces. The proposed algorithm is shown to converge locally q-superlinearly to a regular solution. As an important tool for applications, we establish a sufficient condition for regularity. The application of the algorithm to the distributed bound-constrained control of an elliptic partial differential equation is discussed in detail. Numerical results confirm the efficiency of the method.
Michael Ulbrich
Chapter 17. The Proximal Point Algorithm for the P 0 Complementarity Problem
Abstract
In this paper we consider a proximal point algorithm (PPA) for solving the nonlinear complementarity problem (NCP) with a P 0 function. PPA was originally proposed by Martinet and further developed by Rockafellar for monotone variational inequalities and monotone operator problems. PPA is known to have nice convergence properties under mild conditions. However, until now, it has been applied mainly to monotone problems. In this paper, we propose a PPA for the NCP involving a P 0 function and establish its global convergence under appropriate conditions by using the Mountain Pass Theorem. Moreover, we give conditions under which it has a superlinear rate of convergence.
Nobuo Yamashita, Junji Imai, Masao Fukushima
Chapter 18. Free Boundary Problems in Asset Pricing with Transaction Costs
Abstract
This presentation provides an overview of a class of free boundary problems that arise in valuation models in markets with transaction costs. Transaction costs are a realistic feature in numerous financial transactions and their presence affects considerably the theoretical asset and derivative prices.
In the area of optimal portfolio management, the valuation models give rise to singular stochastic control problems and the goal is to characterize the value function (maximal utility) and to specify the optimal control policies.
In the area of derivative pricing, the classical Black and Scholes valuation theory, based on exact replication, breaks down completely when transaction costs are present. Various approaches have been developed which lead to free boundary problems for the derivative prices. These methods include among others, the method of super-replicating strategies and the utility maximization theory.
Thaleia Zariphopoulou
Backmatter
Metadaten
Titel
Complementarity: Applications, Algorithms and Extensions
herausgegeben von
Michael C. Ferris
Olvi L. Mangasarian
Jong-Shi Pang
Copyright-Jahr
2001
Verlag
Springer US
Electronic ISBN
978-1-4757-3279-5
Print ISBN
978-1-4419-4847-2
DOI
https://doi.org/10.1007/978-1-4757-3279-5