
The application of semidefinite programming (SDP) to control problems is recognized as a successful collaboration between optimization and control theory. Robust optimization, one of recent hot research topics in the field of optimization, has been stimulated by the progress of robust control theory, where we assume that models we use contain uncertainties as often appeared in practical situations. In this workshop, we invite celebrated researchers on the both fields, and the aim is to seek further collaborations for developing new frameworks and algorithms for robust optimization and control.
 Title:
 Workshop on Robust Optimization and Control
 Dates:
 Place:
 University of Tokyo (Seminar Room A, Build.#6,
Faculty of Engineering, Hongo, Tokyo)
 Speakers:
 Stephen Boyd (Stanford)
Tetsuya Iwasaki (U. Virginia)
Kazuo Murota (U. Tokyo)
Yasuaki Oishi (U. Tokyo)
Reha Tutuncu (CMU)
Robert Weismantel (U. Magdeburg)
 Schedule:
 June 16 (Mon):
 10:1011:00 Stephen Boyd (Stanford)
 Fastest Mixing Markov Chain on a Graph
 11:1012:00 Tetsuya Iwasaki (U. Virginia)
 The Generalized KYP Lemma and its Engineering
Applications
 12:0014:00 Lunch
 14:0014:50 Reha Tutuncu (CMU)
 Robust Optimization Approach to Asset Allocation
 15:0015:50 Yasuaki Oishi (U. Tokyo)
 A Randomized Algorithm for Reducing Conservatism
in Robust Control
 15:5016:10 break
 16:1017:00 Robert Weismantel (U. Magdeburg)
 The Integral Basis Method : An Algorithm for Mixed
Integer Programming
 17:1018:00 Kazuo Murota (U. Tokyo)
 Recent Results in Discrete Convex Analysis
 Organizers:
 S. Hara (Chair), K. Tsumura (Secretary), K. Murota, S. Iwata, Y. Oishi
Optimization/Control Group
Superrobust Computation Project
Information Science and Technology Strategic Core
The 21st Century COE (Center of Excellence) Program
 Contact:
 K. Tsumura, Dept. Information Physics and Computing
University of Tokyo, Hongo 731, Tokyo 1138656
tel: +81358416891, fax: +81358416886
tsumura@crux.t.utokyo.ac.jp
Titles and Abstracts
10:1011:00 Stephen Boyd (Stanford)
 Title: Fastest Mixing Markov Chain on a Graph
 Joint work with Lin Xiao and Persi Diaconis
 Abstract:
 We consider an undirected graph, with edges labeled with the probability of a transition between the associated vertices. The associated Markov chain has a uniform equilibrium distribution; the rate of convergence to this distribution is determined by the second largest (in magnitude) eigenvalue of the transition matrix. We show that determining the fastest mixing Markov chain, with a fixed graph, is a convex problem that can be expressed as an SDP.
11:1012:00 Tetsuya Iwasaki (U. Virginia)
 Title: The Generalized KYP Lemma and its Engineering Applications
 Abstract:
 The celebrated KalmanYakubovichPopov (KYP) lemma converts frequency domain inequalities to linear matrix inequalities in the state space, suitable for development of systems theory and for numerical computations. This talk discusses our recent result that generalizes the KYP lemma to treat conditions on restricted frequency intervals expressed as curve(s) on the complex plane. We study implications of the generalized KYP lemma and develop a proper interface between the basic result and various engineering applications. In particular, it is shown that the result allows us to solve a certain class of engineering problems expressed in terms of multiple requirements of the followin type: The Nyquist plot of the system within a prescribed frequency interval must lie in a prescribed conic section on the complex plane. Specific applications include designs of digital filters, PID controllers, and flexible structures.
12:0014:00 Lunch
14:0014:50 Reha Tutuncu (CMU)
 Title: Robust Optimization Approach to Asset Allocation
 Abstract:
 We address the problem of finding an optimal allocation of funds among different asset classes in a robust manner when the estimates of the structure of asset returns are unreliable. Instead of point estimates used in classical meanvariance optimization, moments of returns are described using uncertainty sets that contain all, or most, of their possible realizations. The approach we present takes a conservative viewpoint and identifies asset mixes that have the best worstcase behavior. We discuss techniques for generating uncertainty sets from historical data and report numerical results that illustrate the stability of robust optimal asset mixes.
15:0015:50 Yasuaki Oishi (U. Tokyo)
 Title: A Randomized Algorithm for Reducing Conservatism in Robust Control
 Although robust stabilization is a classical problem in the field of control, it is still difficult to solve. Indeed, it is often the case in practical situations that the existing algorithms provide only conservative results, which are insufficient for practical purposes. In this talk, we consider an algorithm that uses randomization and parameterdependent Lyapunov functions in order to reduce conservatism. The proposed algorithm iteratively solves semidefinite programming problems and is guaranteed to terminate after a finite number of iterations and to give a controller that stabilizes the system almost robustly with high confidence.
15:5016:10 break
16:1017:00 Robert Weismantel (U. Magdeburg)
 Title: The Integral Basis Method : An Algorithm for Mixed Integer Programming
 Abstract:
 This talk deals with the design of a new integer programming algorithm that is based on the theory of irreducible sets of points. We will explain the concept of irreducibility in detail and demonstrate on computational results that this approach is promissing. The talk is based on joint work with Utz Uwe Haus and Matthias Koeppe.
17:1018:00 Kazuo Murota (U. Tokyo)
 Title: Recent Results in Discrete Convex Analysis
 Abstract:
 The concepts of Mconvexity and Lconvexity, introduced by Murota for functions in integer vectors, extract combinatorial structures in wellsolved nonlinear combinatorial optimization problems. These concepts are extended for convex functions in real vectors by MurotaShioura. This talk describes fundamental properties of Mconvex and Lconvex functions in discrete and continuous variables with emphasis on their conjugacy relationship with respect to the LegendreFenchel transform.


