main-content

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.

### 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

### 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

### 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