2015 Informs Annual Meeting

MC14

INFORMS Philadelphia – 2015

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, s.sen@usc.edu 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, a_a_a@princeton.edu 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, rvdb@princeton.edu 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, ermin.wei@northwestern.edu, 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, gh4@princeton.edu, 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, mepelman@umich.edu 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, ilbinlee@umich.edu, 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 Archis Ghate, University of Washington, Industrial & Systems Engineering, Box 352650, Seattle, WA, United States of America, archis@uw.edu, 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, chris.ryan@chicagobooth.edu, 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, stern@chicagobooth.edu, 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, baski@okstate.edu 1 - A Branch Decomposition Algorithm for Better P-median Solutions Caleb Fast, Rice University, 6100 Main St., Houston, TX, 77005, United States of America, ccf5@rice.edu, 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. experimental results comparing their empirical performances. 2 - Policy Iteration for Robust Nonstationary Markov Decision Processes

210