INFORMS Lehigh Student Chapter Distinguished Speaker Seminar

Title:               The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Constant Discount Factor

Speaker:         Professor Yinyu Ye (Stanford University)

Date:               Friday, March 30

Time:              2:30 pm – 3:30 pm

Place:              Room 451 Mohler Lab, 200 W. Packer Avenue

Abstract: We prove that the classic policy-iteration method (Howard 1960), including the Simplex method (Dantzig 1947) with the most-negative-reduced-cost pivoting rule,
is a strongly polynomial-time algorithm for solving the Markov decision problem (MDP) with a constant discount factor. Furthermore, the computational complexity of the
policy-iteration method (including the Simplex method) is superior to that of the only known strongly polynomial-time interior-point algorithm for solving this problem.
The result is surprising since the Simplex method with the same pivoting rule was shown to be exponential for solving a general linear programming (LP) problem,
the Simplex (or simple policy-iteration) method with the smallest-index pivoting rule was shown to be exponential for solving an MDP regardless of discount rates,
and the policy-iteration method was recently shown to be exponential for solving a undiscounted MDP. We also extend the result to solving MDPs with sub-stochastic
and transient state transition probability matrices.

Bio: Yinyu Ye received the B.S. degree in System Engineering from the Huazhong University of Science and Technology, Wuhan, China, and the M.S. and Ph.D. degrees in
Management Science & Engineering from Stanford University, Stanford. Currently, he is a full Professor of Management Science and Engineering and Institute of
Computational and Mathematical Engineering and the Director of the MS&E Industrial Affiliates Program, Stanford University. His current research interests include
Continuous and Discrete Optimization, Mathematical Programming, Algorithm Design and Analysis, Computational Game/Market Equilibrium, Metric Distance
Geometry, Graph Realization, Dynamic Resource Allocation, and Stochastic and Robust Decision Making, etc. 

He was the recipient of John von Neumann Theory Prize by INFORMS (2009), and recipient of the 2009 IBM Faculty Award. He was elected vice chair of the SIAM
Activity Group on Optimization (SIAG/OPT) in 2008. He was elected to theINFORMS fellow in 2006, and awarded the Farkas prize by INFORMS Optimization Society
in the same year. He was the area editor of Math of Operation Research (2009-now), Operation Research (2006-2009), and the Co-Chief Editor of Pacific J. of Optimization (2005-2009).

ALL FULL-TIME ISE PHD STUDENTS ARE REQUIRED TO ATTEND AND

ALL ISE GRADUATE STUDENTS ARE ENCOURAGED TO ATTEND

NSF Award on Polynomial Optimization: Solution Methods and Applications

Recently, a NSF grant was award to Shuzhong Zhang on polynomial optimization. 

The research objective of this project is to develop numerical tools for solving polynomial and tensor optimization models arising from engineering applications such as design of radar waveforms in signal processing, information extraction in magnetic resonance imaging, and gene expression data analysis in bioinformatics. An integrated approach for polynomial and tensor optimization models will be studied and tested in this project. The key components of the integrated approach include relaxation techniques, approximations to optimal solutions, randomized sampling techniques utilizing known structure of the model, and disciplined local improvements of feasible solutions. Numerical tools to be developed under the framework of the integrated approach will be investigated experimentally and validated using the data obtained from practical engineering applications including signal processing and bioinformatics. Performance of the algorithms developed from the project will be measured and compared against currently existing benchmarks. 

If successful, the results of this research will enhance the effectiveness of methods for solving nonlinear optimization models where polynomial functions are found in the objective as well as in the constraints. In particular, such algorithms will lead to substantial practical improvements in radar waveform design, image processing, and data co-clustering analysis. As polynomial functions are known to be pervasive in the context of engineering design and decision making, success of the project will lead to broad societal benefits. Moreover, the proposed research addresses fundamental challenges in optimization theory, because most current research has not gone beyond polynomial models of degree 2; thus, results extending the theory beyond these models would constitute a major advance on the theory side, as well.

NSF Award : Practical Algorithms for Applied Submodular Optimization

Recently, a NSF grant was granted to Jon Lee on submodular optimization. 
This award provides funding for the development and analysis of practical exact and approximation algorithms for general submodular optimization problems, by generalizing and extending mathematical-optimization and approximation methods that have been successful in specific application areas. Important application areas include redesigning environmental monitoring networks and Boolean quadratic optimization. Thus far, general techniques for submodular optimization have been developed with the aim of providing provably good worst-case behavior. On the other hand, practical algorithms, not encumbered by theoretical requirements, have been developed and implemented for several special cases. This project is aimed at extending such success to the general case.

Algorithms will be instantiated and distributed as open-source software thus providing practical, general-purpose tools for attacking this ubiquitous problem class. With particular special cases defined through a black box (i.e., a function-evaluation subroutine), such software will have broad applicability across a variety of application areas, such as economics, machine learning, biodiversity conservation and statics. Moreover, the project is within the broader area of nonlinear discrete optimization, and it is natural to expect to have a broader influence within this important current topic.

ISE seminar 3-16-12:The Central Curve of a Linear Program

INDUSTRIAL AND SYSTEMS ENGINEERING DEPARTMENT
SPRING 2012 SEMINAR SERIES


TITLE:                          The Central Curve of a Linear Program

SPEAKER:                   Cynthia Vinzantis, Department of Mathematics
                                    University of Michigan


DATE / TIME:             Friday, March 16, 2012
                                    2:30 pm –3:30 pm

LOCATION:                 Room 451 Mohler Lab, 200 W. Packer Avenue


ABSTRACT: The central curve of a linear program is an algebraic curve specified by a hyperplane arrangement and a cost vector. This curve is the union of the various central
paths for minimizing or maximizing the cost function over any region in this hyperplane arrangement. I will discuss the algebraic properties of this curve and its beautiful
global geometry, both of which are controlled by the corresponding matroid and hyperplane arrangement.

BIOGRAPHY: Cynthia Vinzant is an Assistant Professor in the department of Mathematics at the University of Michigan. Her research interests center around real algebraic
geometry and its interplay with convexity and optimization. She received her B.A. from Oberlin College and her Ph.D. in mathematics from University of California, Berkeley,
under the direction of Bernd Sturmfels.


ALL FULL-TIME ISE PHD STUDENTS ARE REQUIRED TO ATTEND AND
ALL ISE GRADUATE STUDENTS ARE ENCOURAGED TO ATTEND

Postdoc positions at Nanyang Technological University, Singapore

The Division of Systems and Engineering Management (SEM) at Nanyang Technological University (NTU) in Singapore invites applications for a post-doctoral position effective August/September 2011 or until the position is filled. The initial appointment will be for a period of one year. This can be extended depending on the candidate’s research performance and budget availability. The candidate is required to have a PhD in Operations Research. The successful candidate will have demonstrated experience in optimization, particularly global and stochastic optimization, with related engineering and management applications. Knowledge of conic/SDP optimization will be considered as well. Applicants should have a proven record of research publications in top-tier journals. Strong written and oral communication skills are expected and proposal writing experience is preferred. The position is expected to begin in Aug 2012. 
 
Nanyang Technological University, located in Singapore, is one of the world's leading research universities, and has been consistently ranked in the top 50 in global world engineering rankings. Additional information about the university is available at www.ntu.edu.sg. Singapore has a population of more than 5 million, and is one of the most cosmopolitan cities in the world. If you are interested in applying for this position, please send your CV and one sample publication to Dr. Jitamitra Desai(jdesai@ntu.edu.sg).

Job oportunities at IBM Research and Development, Melbourne, Australia

In 2011, IBM established the IBM Research and Development Lab in
Melbourne, Australia.  The lab focuses on applying data analytics and
optimization to real-world challenges in several domains, including
disaster management, health and natural resources. We are looking for
exceptional researchers in optimization to join our fast-growing
interdisciplinary team. We encourage expressions of interest from both
entry level and experienced candidates.

Required:
  Ph.D. in Operation Research, Engineering, Applied Mathematics or similar field

Expertise in one or more of the following:
     Mixed Integer Linear Programming
     Robust optimization
     Optimization under uncertainty
     Nonlinear optimization
     Supply chain optimization
    Constraint programming
     Local search / meta-heuristics

Preferred:
  Experience applying optimization techniques to industry problems
  Experience with the IBM ILOG optimization products (CPLEX Studio,
CPLEX Optimizer, or ODM Enterprise)
  Java and/or C++ experience

If interested, please send your Resume, the names of at least two
people who can provide references, and a brief cover letter/email
discussing your strengths and relevant experience to Dr. Irina
Dumitrescu at irina.dumitrescu@au.ibm.com . Irina will be happy to
answer any questions you may have about the lab and tell you about
Melbourne, which is currently ranked the most liveable city in the
world.

--
Irina Dumitrescu, Ph.D.
Research Scientist
IBM Research and Development Australia
ph: +61 3 99213805
e: irina.dumitrescu@au.ibm.com