-
作者：Bertsimas, Dimitris; Van Parys, Bart
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We address the problem of prescribing an optimal decision in a framework where the cost function depends on uncertain problem parameters that need to be learned from data. Earlier work proposed prescriptive formulations based on supervised machine learning methods. These prescriptive methods can factor in contextual information on a potentially large number of covariates to take context specific actions which are superior to any static decision. When working with noisy or corrupt data, however...
-
作者：Ye, Ke; Wong, Ken Sze-Wai; Lim, Lek-Heng
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; University of Chicago; University of Chicago
摘要：A flag is a sequence of nested subspaces. Flags are ubiquitous in numerical analysis, arising in finite elements, multigrid, spectral, and pseudospectral methods for numerical pde; they arise in the form of Krylov subspaces in matrix computations, and as multiresolution analysis in wavelets constructions. They are common in statistics too-principal component, canonical correlation, and correspondence analyses may all be viewed as methods for extracting flags from a data set. The main goal of t...
-
作者：Zhang, Junyu; Hong, Mingyi; Zhang, Shuzhong
作者单位：Princeton University; National University of Singapore; University of Minnesota System; University of Minnesota Twin Cities; University of Minnesota System; University of Minnesota Twin Cities
摘要：In this paper, we study the lower iteration complexity bounds for finding the saddle point of a strongly convex and strongly concave saddle point problem: min(x) max(y) F(x, y). We restrict the classes of algorithms in our investigation to be either pure first-order methods or methods using proximal mappings. For problems with gradient Lipschitz constants (L-x, L-y and L-xy) and strong convexity/concavity constants (mu(x) and mu(y)), the class of pure first-order algorithms with the linear spa...
-
作者：Luo, Fengqiao; Mehrotra, Sanjay
作者单位：Northwestern University
摘要：We develop a decomposition algorithm for distributionally-robust two-stage stochastic mixed-integer convex conic programs, and its important special case of distributionally-robust two-stage stochastic mixed-integer second order conic programs. This generalizes the algorithm proposed by Sen and Sherali [Mathematical Programming 106(2): 203-223, 2006]. We show that the proposed algorithm is finitely convergent if the second-stage problems are solved to optimality at incumbent first stage soluti...
-
作者：Song, Yingkai; Khan, Kamil A.
作者单位：McMaster University
摘要：Novel convex and concave relaxations are proposed for the solutions of parametric ordinary differential equations (ODEs), to aid in furnishing bounding information for deterministic global dynamic optimizationmethods. These relaxations are constructed as the solutions of auxiliary ODE systems with embedded convex optimization problems, whose objective functions employ convex and concave relaxations of the original ODE right-hand side. Unlike established relaxation methods, any valid convex and...
-
作者：Berahas, Albert S.; Curtis, Frank E.; Zhou, Baoyu
作者单位：Lehigh University
摘要：A displacement aggregation strategy is proposed for the curvature pairs stored in a limited-memory BFGS (a.k.a. L-BFGS) method such that the resulting (inverse) Hessian approximations are equal to those that would be derived from a full-memory BFGS method. This means that, if a sufficiently large number of pairs are stored, then an optimization algorithm employing the limited-memory method can achieve the same theoretical convergence properties as when full-memory (inverse) Hessian approximati...
-
作者：Yuan, Chenyang; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We study the convex relaxation of a polynomial optimization problem, maximizing a product of linear forms over the complex sphere. We show that this convex program is also a relaxation of the permanent of Hermitian positive semidefinite (HPSD) matrices. By analyzing a constructive randomized rounding algorithm, we obtain an improved multiplicative approximation factor to the permanent of HPSD matrices, as well as computationally efficient certificates for this approximation. We also propose an...
-
作者：Correa, Jose R.; Munoz, Felipe T.
作者单位：Universidad de Chile; Universidad del Bio-Bio
摘要：We study the worst-case performance guarantee of locally optimal solutions for the problem of minimizing the total weighted and unweighted completion time on parallel machine environments. Our method makes use of a mapping that maps a schedule into an inner product space so that the norm of the mapping is closely related to the cost of the schedule. We apply the method to study the most basic local search heuristics for scheduling, namely jump and swap, and establish their worst-case performan...
-
作者：Candogan, Utkan Onur; Chandrasekaran, Venkat
作者单位：California Institute of Technology; California Institute of Technology
摘要：The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex...
-
作者：Grimm, Veronika; Nowak, Daniel; Schewe, Lars; Schmidt, Martin; Schwartz, Alexandra; Zoettl, Gregor
作者单位：University of Erlangen Nuremberg; Technical University of Darmstadt; University of Edinburgh; Universitat Trier; Technische Universitat Dresden; Technical University of Darmstadt
摘要：While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas ...
