Informs Annual Meeting 2017

TE75

INFORMS Houston – 2017

3 - Boosting Performance via Communication in Concurrent Algorithms Oleg Shylo, University of Tennessee, 523 John D. Tickle Engineering Building, 851 Neyland Drive, Knoxville, TN, 37996, United States, oshylo@utk.edu, Andrii Berdnikov We discuss a theoretical framework that captures communication in concurrent optimization algorithms, and use the proposed model to streamline parallel communication. In particular, the focus is on communicative algorithm portfolios, where a group of optimization algorithms works in parallel and shares information about the search process to boost performance. Discussion of the structure and content of scalable communication for a class of scheduling algorithms is provided. 4 - Asynchronous Parallel Stochastic Global Optimization using Radial Basis Functions David Eriksson, Cornell University, 136 Hoy Road, Rhodes Hall 657, Ithaca, NY, 14853, United States, dme65@cornell.edu We propose an asynchronous parallel surrogate optimization algorithm for global optimization of computationally expensive black-box objective functions. Our algorithm uses a radial basis function surrogate and doesn’t require gradient information. We compare our algorithm to a synchronous implementation on several test problems and analyze how the performance depends on the distribution of the objective function evaluation times. Based on our experimental results we propose an empirical method to predict when asynchronous parallel is expected to outperform synchronous parallel. 372D Recent Advances in First and Second Order Methods Sponsored: Optimization, Nonlinear Programming Sponsored Session Chair: Mingyi Hong, University of Virginia, Ames, IA, 50011, Zhaoran Wang, Princeton University, Apt 302, 13 Lawrence Drive, Princeton, NJ, 08540, United States, zhaoran@princeton.edu In this talk, I will illustrate how statistical thinking enables us to harness the power of nonconvex optimization. In specific, I will present an algorithmic framework for exploiting the latent geometry induced by the randomness of data. By integrating three new global exploration meta-algorithms — namely, homotopy continuation, tightening after relaxation, and noise regularization — with local search heuristics — such as the variants of gradient descent — this unified framework leads to new nonconvex optimization algorithms for a broad variety of challenging learning problems. 2 - SARAH: Stochastic Recursive Gradient Algorithm Lam Minh Nguyen, Lehigh University, 200 West Packer Avenue, Room 362, Bethlehem, PA, 18015, United States, lmn214@lehigh.edu, Jie Liu, Katya Scheinberg, Martin Takac We propose a StochAstic Recursive grAdient algoritHm (SARAH), as well as its practical variant SARAH+, as a novel approach to the finite-sum minimization problems. Different from the vanilla SGD and other modern stochastic methods such as SVRG, S2GD, SAG and SAGA, SARAH admits a simple recursive framework for updating stochastic gradient estimates; when comparing to SAG/SAGA, SARAH does not require a storage of past gradients. The linear convergence rate of SARAH is proven under strong convexity assumption. We also prove a linear convergence rate in the strongly convex case for an inner loop of SARAH, the property that SVRG does not possess. Numerical experiments show the efficiency of our algorithm. 3 - Optimal Generalizability in Parametric Learning Meisam Razaviyayn, University of Southern California, Los Angeles, CA, United States, razaviya@usc.edu, Ahmad Beirami Cross-validation is the most popular approach for measuring the predictive performance of a statistical model. This procedure requires solving multiple optimization problems which is computationally expensive in practice. In this work, we first propose a computationally efficient surrogate for the cross- validation and provide theoretical guarantees for its performance. Then we use the proposed surrogate to provide an optimization algorithm for finding the optimal regularizer in the empirical risk minimization framework. In our numerical experiments, we illustrate the accuracy and efficiency of of our proposed surrogate as well as our proposed framework for the optimal regularizer. United States, mingyi@iastate.edu 1 - Taming Nonconvexity with Data TE75

4 - Iteration-complexity of Linearized Proximal Multiblock ADMMs for Solving Linearly Constrained Nonconvex Optimization Problems Renato Monteiro, School of ISyE, Georgia Tech, Atlanta, GA, 30332, United States, monteiro@isye.gatech.edu This talk discusses iteration-complexity of linearized proximal multiblock alternating direction methods of multipliers (ADMM) for solving linearly constrained nonconvex optimization problems. The subproblems are obtained by partially or fully linearizing the augmented Lagrangian with respect to the corresponding minimizing block variables. Complexity bounds are obtained for any choice of a relaxation parameter in the interval (0, 2). 372E Polynomial Optimization and Integer Programming Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Sercan Yildiz, University of North Carolina at Chapel Hill, Statistical and Applied Mathematical Sciences Institute, 19 T.W. Alexander Drive, Research Triangle Park, NC, 27703, United States, syildiz@email.unc.edu 1 - Stronger Polyhedral Relaxations for Polynomial Optimization Problems Aida Khajavirad, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA, 15232, Pittsburgh, PA, 15213, United States, aida@cmu.edu, Alberto Del Pia We consider the Multilinear set defined by a collection of multilinear terms over the unit hypercube. Such sets appear in factorable reformulations of many types of mixed-integer nonlinear programs including polynomial optimization problems. Utilizing an equivalent hypergraph representation for the Multilinear set, we derive various types of facet defining inequalities for its polyhedral convex hull and present a number of tightness results based on the acyclicity degree of the underlying hypergraph. Subsequently, we detail on the implementation of the proposed cutting planes in the branch-and-cut based global solver BARON. Extensive computational results will be presented. 2 - Global Optimization of Power Systems Problems Burak Kocuk, Sabanci University, Istanbul, Turkey, burakkocuk@sabanciuniv.edu, Santanu Subhas Dey, Andy Sun In this talk, we consider polynomial optimization problems form power systems. Due to nonlinearity induced by alternating current power flow equations, these two optimization problems are nonconvex and require efficient global optimization methods. We make effective use of several different strategies to handle nonconvexity, including conic relaxations, envelopes, disjunctive extended formulations, cutting planes, variable bound tightening techniques and feasibility heuristics. Our approaches scale well to large power systems problems and provide provably good solutions in time compatible with the needs of the system operators. 3 - Deriving the Convex Hull Form of a Symmetric Multilinear Polynomial Yibo Xu, Clemson University, 110 Martin Hall, Box 340975, Clemson, SC, 29634, United States, yibox@clemson.edu We generate all the facets of the convex hull of a symmetric multilinear polynomial (SMP) that is constrained over a symmetric box. Our approach exploits the problem symmetry to: define a “core” family of facets that motivates all remaining facets, develop necessary and sufficient conditions for establishing that a valid inequality is a facet, and use our conditions to derive all “core” facets. We propose algorithms that generate all the facets, and also provide a facet- certification algorithm. Our algorithms run successfully in MATLAB, one of which employs PORTA. The computational results provide insight into the complexity of the convex hull generation of a SMP. 4 - Disjunctive Cuts for Bilinear Programming TE76 Consider the problem of optimizing a bilinear function x’Qy + cx + dy over the feasible set given by x \in X, y \in Y, where X and Y are two polyhedral sets. This problem is NP-hard in general, and appears either as is in applications or can be extracted as a relaxation of another problem. We borrow the disjunctive programming paradigm from integer programming to derive strong cutting planes for bilinear optimization. We discuss when the proposed valid inequalities generate the underlying convex hull and how many rounds of these cuts are required to achieve this. Computational results on test instances will be presented. Akshay Gupte, Clemson University, Dept. of Mathematical Sciences, O-321 Martin Hall, Clemson, SC, 29634-0975, United States, agupte@clemson.edu, Michael Glen Eldredge

438