Informs 2015

212 / 552

INFORMS Philadelphia – 2015
210
MC14
14-Franklin 4, Marriott
Optimization Award Session
Sponsor: Optimization
Sponsored Session
Chair: Suvrajeet Sen, Professor, University of Southern California,
University Park Campus, Los Angeles, CA, 90089,
United States of America,
1 -Optimization Society Awards
The Optimization Society sponsors four awards annually. They
are a) the Khachiyan Prize for lifetime contributions in
optimization, b) the Farkas Prize for exceptional mid-career
accomplishments, c) the Young Optimization Researcher award,
and finally, d) the student paper prize competition. The award
winners will present brief overviews of their contributions in this
session. The speakers will be Dr. J-B Lasserre (Khachiyan Prize),
Professor Robert Weismantel (Farkas Prize), Fatma Kilinc-Karzan,
Javad Lavaei, and Somayeh Sojoudi (all for the Young
Optimization Researcher award), and Paul Grigas for the best
student paper. These awards are highly competitive and coveted,
and this session is dedicated to congratulating the winners, and
their lasting contributions to optimization.
MC15
15-Franklin 5, Marriott
Theory and Applications of Convex Optimization
Sponsor: Optimization/Nonlinear Programming
Sponsored Session
Chair: Amir Ali Ahmadi, Princeton University, Department of ORFE,
Sherrerd Hall, Charlton Street, Princeton, NJ, 08544,
United States of America,
1 - Finding Stable Periodic Solutions to the N-body Problem via
Robust Optimization
Robert Vanderbei, Princeton University, ORFE, Sherrerd Hall,
Princeton, NJ, 08544, United States of America,
It is rather easy to use nonconvex nonlinear optimization techniques to find
periodic solutions to the n-body problem in celestial mechanics. But, the vast
majority of the solutions found are dynamically unstable. In this talk, I will
discuss how one can adapt ideas from robust optimization to coerce the
optimization toward local solutions that are in fact stable. Some preliminary
results will be shown.
2 - Efficiency of Supply Function Equilibrium in Networked Markets
Ermin Wei, Assistant Professor, Northwestern University, 2145
Sheridan Rd, Tech L310, Evanston, Il, 60208, United States of
America, , Chaitanya Bandi,
Yuanzhang Xiao
We study the efficiency loss of the supply function equilibrium (SFE). Specifically,
we consider a market where the demand is inelastic, the suppliers submit their
supply functions, and a uniform price is set to clear the market. Literature is
limited to the markets with no network structure, and suggest that SFE is
asymptotically efficient. Motivated by power grid, we study how network
topology affects the efficiency of SFE. We identify the structure where the
intuition from literature holds.
3 - DC Decomposition of Nonconvex Polynomials with
Algebraic Techniques
Georgina Hall, Princeton University, ORFE Department, Sherrerd
Hall, Charlton Street, Princeton, NJ, 08540, United States of
America, , Amir Ali Ahmadi
The concave-convex procedure is a majorization-minimization algorithm for
difference of convex (DC) optimization, where the constraints and the objective
are given as the difference of two convex functions. In this talk, we focus on
polynomial optimization: we introduce LP, SOCP, and SDP based algorithms for
finding optimal DC decompositions by appealing to the algebraic concepts of
“DSOS-Convex, SDSOS-Convex, and SOS-Convex” polynomials.
MC16
16-Franklin 6, Marriott
Advances in Infinite-Dimensional
Linear Programming
Sponsor: Optimization/Linear and Conic Optimization
Sponsored Session
Chair: Marina Epelman, University of Michigan, Industrial and
Operations Engineering, 1205 Beal Ave, Ann Arbor, MI, 48109, United
States of America,
1 - Analysis of Algorithms for Non-stationary Markov
Decision Processes
Ilbin Lee, Postdoctoral Researcher, Georgia Tech,
755 Ferst Dr., NW, Atlanta, GA, 30332, United States of America,
, Marina Epelman, H. Edwin Romeijn,
Robert L. Smith
We consider infinite-horizon discounted Markov decision processes (MDPs) with
finite state space and non-stationary problem data. Existing solution methods for
such MDPs are receding horizon approach and simplex algorithm. For each
method, we establish an upper bound on number of iterations to find a near-
optimal solution and compare the theoretical guarantees. We also provide
experimental results comparing their empirical performances.
2 - Policy Iteration for Robust Nonstationary Markov
Decision Processes
Archis Ghate, University of Washington, Industrial & Systems
Engineering, Box 352650, Seattle, WA, United States of America,
Saumya Sinha
In this talk, we will present an implementable policy iteration algorithm for
solving robust nonstationary Markov decision processes. Its convergence analysis
will be discussed.
3 - Dual Pricing in Semi-infinite Linear Programming
Christopher Ryan, University of Chicago,
Booth School of Business, Chicago, IL, United States of America,
Kipp Martin, Amitabh Basu
LPs satisfy strong duality (SD) and the dual pricing (DP) property, which means
that given a small perturbation of the right-hand side, there exists a dual solution
that computes the exact change in optimal value. SD and DP fail in general for
semi-infinite LPs. For a restricted constraint space SD and DP hold. We give
conditions for when DP holds in general. Dual solutions may exist that guarantee
DP but have awkward structure. “Nice” solutions can be seen as integrals that
price constraints.
4 - The Slater Conundrum: Duality and Pricing in Infinite
Dimensional Optimization
Matthew Stern, University of Chicago - Booth School of Business,
5807 S Woodlawn Ave, Chicago, IL, 60637, United States of
America, , Kipp Martin,
Christopher Ryan
For a general class of infinite dimensional vector spaces, we show that the
existence of interior points required by common constraint qualifications for zero
duality gap (such as Slater’s condition) implies the existence of singular dual
solutions that are difficult to find and interpret. We then provide sufficient
conditions that guarantee the existence an optimal dual solution that is not
singular.
MC17
17-Franklin 7, Marriott
Network Flows and Combinatorial Optimization
Sponsor: Optimization/Network Optimization
Sponsored Session
Chair: Baski Balasundaram, Associate Professor, Oklahoma State
University, 322 Engineering North, Stillwater, OK, 74078,
United States of America,
1 - A Branch Decomposition Algorithm for Better P-median Solutions
Caleb Fast, Rice University, 6100 Main St., Houston, TX, 77005,
United States of America, Illya Hicks
This talk presents a branch decomposition algorithm for improving approximate
solutions to the p-Median problem. Since the p-Median problem is NP-hard,
heuristics are commonly used to generate approximate solutions. We use a
branch decomposition algorithm on the support graph generated from multiple
heuristic runs to find an approximate solution of higher quality than that
provided by the heuristic. We report numerical results for some common
heuristics.
MC14