Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2012 | Book

Chapter 1 Representation of Positive Polynomials Read chapter Read first chapter

Modern Optimization Modelling Techniques

Authors: Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre

Publisher: Springer Basel

Book Series : Advanced Courses in Mathematics - CRM Barcelona

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

The theory of optimization, understood in a broad sense, is the basis of modern applied mathematics, covering a large spectrum of topics from theoretical considerations (structure, stability) to applied operational research and engineering applications. The compiled material of this book puts on display this versatility, by exhibiting the three parallel and complementary components of optimization: theory, algorithms, and practical problems.

The book contains an expanded version of three series of lectures delivered by the authors at the CRM in July 2009. The first part is a self-contained course on the general moment problem and its relations with semidefinite programming. The second part is dedicated to the problem of determination of Nash equilibria from an algorithmic viewpoint. The last part presents congestion models for traffic networks and develops modern optimization techniques for finding traffic equilibria based on stochastic optimization and game theory.

Table of Contents

Frontmatter

Moments and Positive Polynomials for Optimization

Frontmatter
Chapter 1 Representation of Positive Polynomials
Abstract
In one dimension, the ring \({\mathbb{R}} [x]\) of real polynomials in a single variable has the fundamental property (Theorem 1.6) that every nonnegative polynomial \(p \in \mathbb{R} [x]\) is a sum of squares of polynomials, that is, \(p(x) \geq 0, \forall_{x} \in \mathbb{R}\,\,\,\Longleftrightarrow\,\,\,p(x) = \sum\limits_{i=1}^{k} h_i(x)^{2}, \forall_{x} \in \mathbb{R}\), for finitely many polynomials (h i).
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 2 Moments
Abstract
Most results of this chapter are dual analogues of those described in Chapter 1. Indeed, the problem of representing polynomials that are positive on a set K \(\subset \mathbb{R}^{n}\) has a dual facet which is the problem of characterizing sequences of reals that are moment sequences of some finite Borel measure supported on K.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 3 Polynomial Optimization
Abstract
In this chapter, we consider the following polynomial optimization problem: \(f^{\ast} = {\text{min}} \{f(x) : x \in K\}\), where \(f \in \mathbb{R}[x]\) is a real-valued polynomial and \({\rm K}\,\subset \mathbb{R}^{n}\) is the basic semi-algebraic set defined by \(K = \{x \in \mathbb{R}^n : g_i(x) \geq 0, i=1,\ldots,m\}\), with \(g_i \in \mathbb{R}[x], i=1,\ldots,m\).
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 4 Convexity in Polynomial Optimization
Abstract
If on the one hand practice seems to reveal that convergence of the semidefinite relaxations (3.14) is often fast and even finite, on the other hand we have seen that their size grows rapidly with the rank in the hierarchy. And so, if sparsity in the original problem data is not exploited, the approach is limited to small or to medium size problems only. On the other hand, it is well known that a large class of convex optimization problems can be solved efficiently.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 5 Parametric Polynomial Optimization
Abstract
Roughly speaking, given a set of parameters Y and an optimization problem whose description depends on \(y \in Y\) (call it P y), parametric optimization is concerned with the behavior and properties of the optimal value as well as primal (and possibly dual) optimal solutions of P y, when y varies in Y. This is a quite challenging problem for which in general only local information around some nominal value y0 of the parameter can be obtained. Sometimes, in the context of optimization with data uncertainty, some probability distribution on the parameter set Y is available and in this context one is also interested in, e.g., the distributions of the optimal value and optimal solutions, all viewed as random variables.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre

Computation of Generalized Nash Equilibria: Recent Advancements

Frontmatter
Chapter 1 Some Telecommunication Applications
Abstract
As we have already mentioned, Computer Science and Telecommunications are probably the two overlapping fields where GNEPs are currently being used more extensively and with more effectiveness. In this chapter we describe some problems in telecommunications in order to give the reader a feel of current trends in the field. The description of these problems would benefit greatly from a knowledge of basic information theory.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 2 NEPs and Jointly Convex GNEPs
Abstract
The GNEP is a very general model, encompassing very many different kinds of problems. It may be useful then to preliminarily consider some special cases, which have a somewhat simpler structure. This will be useful also to the end of devising algorithms for the solution of general GNEPs, since in many cases the strategy adopted consists in some way of transforming the general gnep to a simpler instance.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 3 Jointly Convex Nash Equilibrium Problems
Abstract
Jointly convex (JC) GNEPs are by far the most studied class of gneps where there actually is an interaction among players at the feasible set level. In spite of this (relative) popularity, we will see that there are several open problmes yet. We begin with a formal definition.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 4 GNEPs with No Special Structure
Abstract
As we saw in the previous chapter, there are some sound proposals for the analysis and solution of standard Nash problems and of jointly convex problems. However, when it comes to the analysis and solution of a gnep in its full generality, the situation is much bleaker. A gnep cannot be reduced to a VI, but it can be reduced to a quasi-variational inequality, as first noted in [14]. A quasi-variational inequality is a problem formally similar to a VI where, however, the feasible set K is not fixed but depends on x. Since the theory of quasi-variational inequalities is not nearly as developed as that of VIs, this reduction is not very useful, especially from the computational point of view. So we do not pursue this issue further. In this chapter, instead, after discussing very briefly some existence results, we consider in some detail two recent algorithmic developments that seem promising.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre

Equilibrium and Learning in Traffic Networks

Frontmatter
Chapter 1 Wardrop and Stochastic User Equilibrium
Abstract
This chapter provides a short overview of two classical models for traffic equilibrium: Wardrop equilibrium and stochastic user equilibrium.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 2 Markovian Traffic Equilibrium
Abstract
As pointed out at the end of the previous chapter, route-based equilibrium models present several drawbacks from the modeling and computational viewpoints. In particular, the independence of route travel times is not well suited when dealing with overlapping paths.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Chapter 3 Adaptive Dynamics in Traffic Games
Abstract
The equilibrium concepts discussed in the previous chapters were eminently static, with traffic modeled as a steady state that results from the adaptive behavior of drivers. These models assume implicitly the existence of a hidden mechanism that leads to equilibrium, though they are stated directly in the form of equilibrium equations which are not tied to a specific adaptive dynamics. Furthermore, they consider a non-atomic framework that ignores individual drivers and uses continuous variables to represent aggregate flows. In this chapter we discuss a dynamical model for the adaptive behavior of finitely many drivers in a simple network and we study its convergence towards a steady state.
Roberto Cominetti, Francisco Facchinei, Jean B. Lasserre
Metadata
Title
Modern Optimization Modelling Techniques
Authors
Roberto Cominetti
Francisco Facchinei
Jean B. Lasserre
Copyright Year
2012
Publisher
Springer Basel
Electronic ISBN
978-3-0348-0291-8
Print ISBN
978-3-0348-0290-1
DOI
https://doi.org/10.1007/978-3-0348-0291-8