2016 INFORMS Annual Meeting Program

WC16

INFORMS Nashville – 2016

2 - Covariance Thresholding And Sparse Pca Yash Deshpande, Stanford University, yashd@stanford.edu In sparse principal components analysis (PCA), we wish to infer a sparse, low- rank matrix from noisy data. Johnstone and Lu proposed the popular “spiked covariance” model, where the data is $n$ samples with population covariance $I + vv^t$. Assuming that the spike $v$ is sparse, they proposed the diagonal thresholding scheme to estimate its support. Despite considerable work, there was no computationally efficient procedure that provably improved over this scheme. We analyze a simple “covariance thresholding” algorithm and show that it outperforms the diagonal thresholding scheme. In fact, assuming hardness of the hidden clique problem, it is impossible to significantly improve this guarantee. 3 - Vanishing Duality Gap In Nonconvex Optimization Mengdi Wang, Princeton University, mengdiw@princeton.edu Consider the optimization problem that involves multiple participants driven by self interests and common goods. We focus on the nonconvex problem which is often NP-hard. We analyze the nonconvex duality and show that it often vanishes to zero as the number of participants goes to infinity. Moreover, we show that there exists an approximate optimum by solving the dual problem and provide a coordinative dual algorithm to achieve the optimum in polynomial time. We demonstrate the application of the proposed method in estimating large spatial graphical model with sparsity constraints, and show that the dual solution is statistically optimal for large graphs. 4 - Nestt: A Nonconvex Primal Dual Splitting Method For Distributed And Stochastic Optimization Davood Hajinezhad, Iowa State University, dhaji@iastate.edu, Mingyi Hong, Zhaoran Wang, Tuo Zhao We study a stochastic and distributed algorithm for a nonconvex problem, whose objective consists a sum of $N$ nonconvex $L_i$-smooth functions $g_i$, plus a nonsmooth regularizer. The proposed algorithm splits the nonconvex problem into $N$ subproblems, and utilizes an augmented Lagrangian based primal-dual scheme to solve it in a distributed and stochastic manner. Further, we reveal a fundamental connection between the proposed {\it primal-dual splitting} methods and a few {\it primal only} methods such as IAG/SAG/SAGA. WC16 105A-MCC Optimization and Learning in Supply Chain Systems Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Huanan Zhang, University of Michigan, 1205 Beal Avenue, Ann Arbor, MI, 48109, United States, zhanghn@umich.edu Co-Chair: Cong Shi, University of Michigan, 1205 Beal Avenue, Ann Arbor, MI, 48109, United States, shicong@umich.edu 1 - Closing The Gaps: A Learning-while-doing Algorithm For Lost-sales Inventory System With Lead Times Huanan Zhang, University of Michigan, Ann Arbor, MI, 48108- 1094, United States, zhanghn@umich.edu, Xiuli Chao, Cong Shi We develop an improved nonparametric learning algorithm for periodic-review lost sales inventory systems with positive lead time, where the firm does not know the demand distribution a priori but makes the replenishment decision in each period based only on the past sales (censored demand) data. It is known that the optimal policy is hard to compute even with full information, hence in this paper we focus on finding the best base-stock policy. We establish a square-root convergence rate of the proposed learning algorithm, which is the best possible rate for this class of problems. 2 - Nonparametric Data-driven Algorithms For Capacitated Inventory Systems Weidong Chen, University of Michigan, aschenwd@umich.edu, Cong Shi, Izak Duenyas We propose data-driven algorithms for the management of stochastic inventory systems with fixed ordering capacity and random ordering capacity. We consider a single-product, periodic-review inventory system with backlogging. We assume that the manager has no prior information on the demand distribution nor the capacity distribution and only has access to past demand and supply data . In our model, we propose cyclic gradient-descent type of algorithms whose running average holding and backlogging cost asymptotically converges to the cost of the optimal. We prove the rate of convergence guarantee of our algorithm is O(1/sqrt(T )) for both cases. 3 - Primal-dual Algorithm For Online Transportation Problem

information of subsequent customers. We design a Primal-dual Algorithm for the retailer to maximize the total revenue under the uncertainty of those customers who have not yet arrived. We also compare our online policy with the offline optimal policy and obtain a competitive ratio which guarantees the performance of our Primal-Dual Algorithm. 4 - Preservation Of Additive Convexity And Its Applications In Stochastic Optimization Problems Xiting Gong, The Chinese University of Hong Kong, xtgong@se.cuhk.edu.hk, Tong Wang In this paper, we establish a new preservation result of additive convexity for a class of multi-dimensional optimization problems. We demonstrate the applications of this result and and its variant to several important stochastic optimization problems, including stochastic inventory control problems with remanufacturing, dynamic inventory rationing with multiple demand classes, and dynamic capacity management with general upgrading. Nonlinear Optimization Algorithms I Sponsored: Optimization, Nonlinear Programming Sponsored Session Chair: Daniel Robinson, Johns Hopkins University, 3400 N. Charles Street, Baltimore, MD, 21218, United States, daniel.p.robinson@gmail.com Co-Chair: Frank Edward Curtis, Lehigh University, 200 West Packer Avenue, Bethlehem, PA, 18015, United States, frank.e.curtis@gmail.com Co-Chair: Andreas Waechter, Northwestern University, 2145 Sheridan Road, Evanston, IL, 60208, United States, waechter@iems.northwestern.edu 1 - An Active-set Algorithm For Chance-constrained Nonlinear Optimization Andreas Waechter, Northwestern University, waechter@iems.northwestern.edu, Frank Edward Curtis, Victor M Zavala A new algorithmic framework for the solution of nonlinear chance-constrained optimization problems is proposed. Similar to Fletcher’s Sl1QP algorithm, the method computes trial points from the minimization of a piece-wise quadratic model subject to a trust region. Theoretical convergence results and numerical experiments will be presented. 2 - Logical Benders Decomposition For Binary-constrained Quadratic Programs With Complementarity Constraints Francisco Jara-Moroni, Northwestern University, Evanston, IL, United States, franciscojaramoroni2013@u.northwestern.edu, Andreas Waechter, Jong-Shi Pang, John E Mitchell We study a Benders decomposition approach to solving Binary Constrained Quadratic Programs with Linear Complementarity Constraints. It formulates a satisfiability master problem with feasibility cuts are added by solving primal and dual subproblems for chosen complementarity pieces and binary variables. Our method strengthens the feasibility cuts by solving L0-norm or L1-norm problems, and guides the satisfiability problem solution by means of a convex piecewise linear approximation of the objective function. 3 - Trust Region Methods With Optimal Complexity For Nonconvex Functions Mohammadreza Samadi, Lehigh University, Bethelehem, PA, United States, mos213@lehigh.edu, Frank E. Curtis, Daniel Robinson We present a trust region method for unconstrained nonconvex optimization that, in the worst-case, is able to drive the norm of the gradient of the objective below a prescribed threshold eps > 0 after at most O(eps^(-3/2)) iterations. This complexity bound has been shown to be optimal with respect to a wide class of methods. Our algorithm (called TRACE) is modeled after a traditional trust region algorithm, but employs modified step acceptance criteria and a novel trust region updating mechanism that allows it to achieve this desirable property. As an extension, we discuss the implications of our new algorithm on equality constrained problems. Numerical results are presented. WC17 105B-MCC

Yuchen Jiang, University of Michigan, Ann Arbor, MI, United States, ycjiang@umich.edu, Cong Shi, Siqian Shen

In this paper, we study a transportation problem in which customers come one by one in an online manner. The retailer chooses a particular warehouse from which a shipment is made to meet the current customer’s demand without knowing the

432