Informs Annual Meeting 2017

TC83

INFORMS Houston – 2017

TC82

TC83

382B Recent Advances in Multistage Stochastic Programs Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Yongjia Song, Virginia Commonwealth University, Richmond, VA, 23284, United States, ysong3@vcu.edu 1 - Two-stage Linear Decision Rules for Multistage Stochastic Programming Merve Bodur, University of Toronto, 5 King’s College Road, Toronto, ON, M5S.3G8, Canada, bodur@mie.utoronto.ca, James Luedtke Multistage stochastic linear programs (MSLP) can be approximated by applying linear decision rules (LDR) on the recourse decisions. This reduces MSLP (its dual) into a static problem which provides an upper (lower) bound on the optimal value. We introduce two-stage LDR whose application reduces MSLP (or its dual) into a two-stage stochastic LP. In addition to yielding better policies and bounds, this approach requires many fewer assumptions than are required to get an explicit reformulation when using the static LDR approach. On a capacity expansion model, we find that the two-stage LDR policy has expected cost 20- 34% lower than the static LDR policy, and yields lower bounds that are 0.1-3.3% better. 2 - Regularized Decomposition Methods for Multistage Convex Optimization Problems We design regularized variants of the Dual Dynamic Programming (DDP) and Stochastic Dual Dynamic Programming (SDDP) algorithms to solve dynamic convex programming problems. We show the convergence of the proposed algorithms and study their computational performance. The algorithms are used on portfolio optimization problems with direct and indirect transaction costs. In particular, we propose a risk-neutral portfolio selection model included market impact costs and cast as a multistage stochastic second-order cone programming problem. 3 - Speeding-up a Modified SDDP Method for Risk-averse Energy Storage Optimization using Importance Sampling Juliana Nascimento, Princeton University, Sherrerd Hall, Operations Research and Fincl. Engineering, Princeton, NJ, 08544, United States, jnascime@princeton.edu, Joe Durante, Daniel Jiang, Warren B.Powell Stochastic dual decomposition procedure (SDDP) has been widely used for stochastic linear programs. We study SDDP in the context of optimizing grid-level storage, using a new hidden semi-Markov model (HSMM) for modeling the behavior of wind. Our HSMM has been shown to accurately reproduce the crossing-time behavior of the wind, which captures the amount of time that actual wind sample paths are above or below forecasts. The HSMM requires that we capture complex temporal interdependencies, but provides more robust solutions. We use an additive utility function and demonstrate a novel importance sampling technique to speed-up the backward pass of SDDP. 4 - Regularized Decomposition Methods for Multistage Stochastic Linear Programs Yongjia Song, Virginia Commonwealth University, 1015 Floyd Avenue, P.O. Box 843083, Richmond, VA, 23284, United States, ysong3@vcu.edu, Wim van Ackooij, Welington de Oliveira We consider well-known decomposition techniques for multistage stochastic programming and a new scheme based on normal solutions for stabilizing calculations as the iteration process progresses. The given algorithms combine ideas from finite perturbation of convex programs and level bundle methods to regularize the so-called forward step of these decomposition methods. We also improve the backward step (that generates cuts, approximating the cost-to-go functions) by employing an adaptive partition-based approach to reduce the computational burden. Numerical experiment results on a hydrothermal scheduling problem will be shown. Miguel Lejeune, Professor, George Washington University, Washington, DC, 20052, United States, mljne@yahoo.com, Vincent Guigues, Walid Tekaya

382C Optimization, Robust Contributed Session Chair: Yang Zhan, City University of Hong Kong, Kowloon, Hong Kong, yangzhan3-c@my.cityu.edu.hk 1 - Optimizing Black Box Functions with Xpress Majid Bazrafshan, Lead Consultant, FICO, 3957 Rue Berri, Montreal, QC, H2L.4H2, Canada, majidbazrafshan@fico.com, Zsolt Csizmadia Optimization of black box functions are challenging due to the lack of information that defines them. The best method depends on the application; and while there may be no free lunch one property seems common: the expensive part is often the evaluations. A tempting solution is to use a solver that uses multiple evaluations per iteration organized into parallel calls. Doing so faces the same black box challenge; while the modeler knows the assumptions of the black- box, the solver is unlikely to offer just the right facilities to accommodate those. We show how FICO Xpress comes around these problems by providing automatic generation of parallel versions for user functions that remain fully customize-able. 2 - Solving L0-constrained Sparse Inverse Covariance Estimation Dzung Phan, IBM.Research, 1101 Kitchawan Road, P.O. Box 218, Yorktown Heights, NY, 10598, United States, phandu@us.ibm.com, Matt Menickelly Sparse inverse covariance matrices are utilized to model conditional dependences between variables in a network. Sparsity is often used for either interpretability of model or to avoid overfitting. We directly constrain sparsity by specifying a maximally allowable number of nonzeros. We present an efficient proximal projected Newton algorithm with warm starts for solving the l0-constrained GGM learning problem. 3 - A Second Order Method for Non-convex Optimization with Logarithmic Complexity Santiago Paternain, University of Pennsylvania, Philadelphia, PA, United States, spater@seas.upenn.edu, Aryan Mokhtari, Alejandro Ribeiro The problem of minimizing non-convex functions is central to many applications such as neural networks and matrix factorization. The main issue in solving these problems origins in the proliferation of saddle points. In this work, we present a modified Newton’s method by replacing the negative eigenvalues of the Hessian by their absolute values to correct the curvature of the descent direction. This modification leads to a novel method that escapes the saddles exponentially fast. Moreover, we show that with probability 1-p the proposed algorithm outputs a solution within the epsilon radius of a local minimum of the objective function after running for O(log(1/p)+ log(eps)) iterations. 4 - Robust Operational Decisions for Multi Period Industrial Gas Pipeline Networks under Uncertainty Pelin Cay, PhD Candidate, Lehigh University, Harold S. Mohler Laboratory, 200 W. Packer Ave, Bethlehem, PA, 18015, United States, caypelin@gmail.com, Camilo Mancilla, Robert H. Storer, Luis F. Zuluaga Industrial gas companies plan daily gas production levels to minimize total production cost per day. While meeting the customer demand and physical constraints in a gas pipeline network leads to a challenging optimization problem, daily planning requires multi-period formulation with ramping limitation of the plants. In this study, we apply a heuristic approach to find a feasible solution for industry-sized problems. Moreover, we provide a lower bound solution to produce global optimality gap of the heuristic solution by the convex reformulation of the standard problem. Numerical experiments show advantages of using the developed heuristic compared to solving the standard formulation. 5 - A Smooth Path Following Algorithm for Market Equilibrium under a Class of Piecewise Smooth Concave Utilities Yang Zhan, City University of Hong Kong, Kowloon, Hong Kong, yangzhan3-c@my.cityu.edu.hk, Chuangyin Dang This paper presents a smooth path-following algorithm for computing market equilibrium in a pure exchange economy under a class of piecewise-smooth concave utilities, which can be expressed as u(x)=minl{fl(x)} with fl(x) being a smooth concave function for all l. As a result of a smooth technique for minimax problems, a smooth homotopy mapping is derived from the introduction of logarithmic barrier terms and an extra variable. With this mapping, it is proved that there always exists a smooth path leading to a market equilibrium as the extra variable approaches zero. Numerical results are given to further demonstrate the effectiveness and efficiency of the algorithm.

367