Workshop on Robust
Optimization and Control

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:
    • June 16, 2003
  • 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:10-11:00 Stephen Boyd (Stanford)
      • Fastest Mixing Markov Chain on a Graph
    • 11:10-12:00 Tetsuya Iwasaki (U. Virginia)
      • The Generalized KYP Lemma and its Engineering
        Applications
    • 12:00-14:00 Lunch
    • 14:00-14:50 Reha Tutuncu (CMU)
      • Robust Optimization Approach to Asset Allocation
    • 15:00-15:50 Yasuaki Oishi (U. Tokyo)
      • A Randomized Algorithm for Reducing Conservatism
        in Robust Control
    • 15:50-16:10 break
    • 16:10-17:00 Robert Weismantel (U. Magdeburg)
      • The Integral Basis Method : An Algorithm for Mixed
        Integer Programming
    • 17:10-18: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 7-3-1, Tokyo 113-8656
      tel: +81-3-5841-6891, fax: +81-3-5841-6886
      tsumura@crux.t.u-tokyo.ac.jp


Titles and Abstracts

10:10-11: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:10-12:00 Tetsuya Iwasaki (U. Virginia)

  • Title: The Generalized KYP Lemma and its Engineering Applications
  • Abstract:
    • The celebrated Kalman-Yakubovich-Popov (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:00-14:00 Lunch

14:00-14: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 mean-variance 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 worst-case 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:00-15: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 parameter-dependent 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:50-16:10 break

16:10-17: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:10-18:00 Kazuo Murota (U. Tokyo)

  • Title: Recent Results in Discrete Convex Analysis
  • Abstract:
    • The concepts of M-convexity and L-convexity, introduced by Murota for functions in integer vectors, extract combinatorial structures in well-solved nonlinear combinatorial optimization problems. These concepts are extended for convex functions in real vectors by Murota--Shioura. This talk describes fundamental properties of M-convex and L-convex functions in discrete and continuous variables with emphasis on their conjugacy relationship with respect to the Legendre-Fenchel transform.