Category Archives: Fall 2013

Fall 2013 Calendar

October 8
Sameer Agarwal, Google.
Ceres Solver

October 15
James Pfeiffer, Department of Mathematics, University of Washington.
A Cri­te­rion for Sums of Squares on the Hypercube

October 28
Stephen Boyd, Department of Electrical Engineering, Stanford.
The Sci­ence of Bet­ter: Embed­ded Opti­miza­tion in Smart Systems

October 29
Stephen Boyd, Department of Electrical Engineering, Stanford.
Con­vex Opti­miza­tion: From Embed­ded Real-Time to Large-Scale Distributed

November 19
Daniel Dadush, Courant Institute of Mathematical Sciences, NYU.
On the exis­tence of 0/1 poly­topes with high semi­def­i­nite exten­sion complexity

November 26 (cancelled)
Sina Jafarpour, Bina Technologies.
Sta­tis­ti­cal Opti­miza­tion for Iden­ti­fy­ing Genomic Copy Num­ber Variations

December 2
Pablo Parrilo, Department of Electrical Engineering, MIT.
Flows and Decompositions of Games; Harmonic and Potential Games

See below for the abstracts.

Pablo A. Parrilo; Flows and Decompositions of Games: Harmonic and Potential Games

Monday, December 2, 2013, 4:00pm
EEB 125
Pablo A. Parrilo, Department of Electrical Engineering and Computer Science, MIT.
Flows and Decompositions of Games: Harmonic and Potential Games

Abstract: Game theory is a rich mathematical framework to model and analyze the interactions of multiple decision makers with possibly conflicting objectives. Finite games in strategic form (i.e., those with a finite number of players, each with finitely many possible actions, that simultaneously and independently choose their action) are particularly important and well-studied.

In this talk we discuss a novel flow representation for finite games in strategic form. Based on this representation, we develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. Besides its intrinsic interest, this decomposition facilitates the study of Nash and correlated equilibria as well as convergence properties of natural distributed game dynamics. We explain the background and basic ideas, and illustrate the implications of the decomposition for dynamic analysis, pricing schemes, efficiency loss, and network games.

Based on joint work with Ozan Candogan, Ishai Menache, and Asu Ozdaglar (MIT).

Biosketch: Pablo A. Parrilo is a Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. He is currently an Associate Director of the Laboratory for Information and Decision Systems (LIDS), and is also affiliated with the Operations Research Center (ORC). Past appointments include Assistant Professor at the Automatic Control Laboratory of the Swiss Federal Institute of Technology (ETH Zurich), Visiting Associate Professor at the California Institute of Technology, as well as short-term research visits at the University of California at Santa Barbara (Physics), Lund Institute of Technology (Automatic Control), and University of California at Berkeley (Mathematics). He received an Electronics Engineering undergraduate degree from the University of Buenos Aires, and a PhD in Control and Dynamical Systems from the California Institute of Technology.

His research interests include optimization methods for engineering applications, control and identification of uncertain complex systems, robustness analysis and synthesis, and the development and application of computational tools based on convex optimization and algorithmic algebra to practically relevant engineering problems.

Pablo Parrilo has received several distinctions, including a Finmeccanica Career Development Chair, the Donald P. Eckman Award of the American Automatic Control Council, the SIAM Activity Group on Control and Systems Theory (SIAG/CST) Prize, the IEEE Antonio Ruberti Young Researcher Prize, and the Farkas Prize of the INFORMS Optimization Society. He is currently on the Editorial Board of the MOS/SIAM Book Series on Optimization.

Sameer Agarwal; Ceres Solver

October 8, 2013, 4:00pm
Johnson 175
Sameer AgarwalGoogle. 
Ceres Solver

Abstract: Nonlinear least squares problems comes up in a broad range of areas across science and engineering – from fitting curves in statistics, to constructing 3D models from photographs in computer vision. Ceres Solver (http://code.google.com/p/ceres-solver) is a portable C++ library that allows for modeling and solving large complicated nonlinear least squares problems.

Ceres Solver is used at Google to estimate the pose of Street View cars, aircrafts, and satellites; to build 3D models for PhotoTours; stitch panoramic images on your cellphone and more. Outside Google, it is used for robot navigation, semi-conductor physics and financial calculations.

In this talk I will describe Ceres Solver’s architecture, pontificate on what is so awesome about it and some lessons learned in developing and open sourcing it. Small fragments of C++ will make an appearance too.

James Pfeiffer; A Criterion for Sums of Squares on the Hypercube

October 15, 2013, 4:00pm
Johnson 175
James Pfeif­fer, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Washington
A Criterion for Sums of Squares on the Hypercube

Abstract: Functions on the hypercube $\{0,1\}^n$ have a natural notion of polynomial divisibility and degree. We use the action of the symmetric group to show that a function vanishing to odd degree on a slice of the hypercube given by $\sum_i x_i = t$, for $t \le n/2$, cannot be a sum of squares of degree $d \le t$. As a corollary, we reprove a result of Laurent that the Lasserre rank of optimizing over the cut polytope is at least $n/2$. We also find a nonnegative degree-4 polynomial on $\RR^n$ which requires degree-$n/2$ sum of squares multipliers to be written as a sum of squares.

Stephen Boyd; The Science of Better: Embedded Optimization in Smart Systems

October 28, 2013, 3:30pm
The Paul G. Allen Center – Microsoft Atrium
Stephen P. BoydDepartment of Electrical Engineering, Stanford
The Science of Better: Embedded Optimization in Smart Systems

Abstract: Many current products and systems employ sophisticated mathematical algorithms to automatically make complex decisions, or take action, in real-time. Examples include recommendation engines, search engines, spam filters, on-line advertising systems, fraud detection systems, automated trading engines, revenue management systems, supply chain systems, electricity generator scheduling, flight management systems, and advanced engine controls. I’ll cover the basic ideas behind these and other applications, emphasizing the central role of mathematical optimization and the associated areas of machine learning and automatic control. The talk will be nontechnical, but the focus will be on understanding the central issues that come up across many applications, such as the development or learning of mathematical models, the role of uncertainty, the idea of feedback or recourse, and computational complexity.

Part of The Dean Lytle Electrical Engineering Endowed Lecture Series, for general audience.

Stephen Boyd; Convex Optimization: From Embedded Real-Time to Large-Scale Distributed

October 29, 2013, 3:30pm
EEB 105
Stephen P. Boyd, Department of Electrical Engineering, Stanford
Convex Optimization: From Embedded Real-Time to Large-Scale Distributed

Abstract: Convex optimization has emerged as a useful tool for applications that include data analysis and model fitting, resource allocation, engineering design, network design and optimization, finance, and control and signal processing. After an overview, the talk will focus on two extremes: real-time embedded convex optimization, and distributed convex optimization. Code generation can be used to generate extremely efficient and reliable solvers for small problems, that can execute in milliseconds or microseconds, and are ideal for embedding in real-time systems. At the other extreme, we describe methods for large-scale distributed optimization, which coordinate many solvers to solve enormous problems.

Part of The Dean Lytle Electrical Engineering Endowed Lecture Series, Technical Colloquium.

Daniel Dadush; On the existence of 0/1 polytopes with high semidefinite extension complexity

November 19, 2013, 4:00pm
John­son 175
Daniel Dadush, Courant Insti­tute of Math­e­mat­i­cal Sci­ences, NYU.
On the existence of 0/1 polytopes with high semidefinite extension complexity

Abstract: In linear programming, the technique of linear extended formulations attempts to translate exponential sized linear programs into polynomial sized ones. To do this, one finds a higher dimensional polytope with relatively few facets that projects to the original feasible polytope. The technique has limitations, however. In 2011, Rothvoss showed that there exists a 0/1 poly­tope such that any higher-dimensional poly­tope pro­ject­ing to it must have an expo­nen­tial num­ber of facets, i.e., there does not exist a polynomial sized linear extended formulation. The technique of linear extended formulations can be generalized to PSD extended formulations by working with PSD cones instead of nonnegative orthants. Using new techniques to rescale semidefinite factorizations, we show that there exists a 0/1 polytope such that every PSD extended formulation for this polytope must have exponential size.

Joint work with Jop Briet and Sebastian Pokutta.