2016 INFORMS Annual Meeting Program

432 / 561

INFORMS Nashville – 2016
432
2 - Covariance Thresholding And Sparse Pca
Yash Deshpande, Stanford University,
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,
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,
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,
Co-Chair: Cong Shi, University of Michigan, 1205 Beal Avenue, Ann
Arbor, MI, 48109, United States,
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, , 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, ,
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
Yuchen Jiang, University of Michigan, Ann Arbor, MI,
United States, 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
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,
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.
WC17
105B-MCC
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,
Co-Chair: Frank Edward Curtis, Lehigh University, 200 West Packer
Avenue, Bethlehem, PA, 18015, United States,
Co-Chair: Andreas Waechter, Northwestern University, 2145 Sheridan
Road, Evanston, IL, 60208, United States,
1 - An Active-set Algorithm For Chance-constrained
Nonlinear Optimization
Andreas Waechter, Northwestern University,
, 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,
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, , 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.
WC16