-
作者：Nam Ho-Nguyen; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：In this paper, we consider two paradigms that are developed to account for uncertainty in optimization models: robust optimization (RO) and joint estimation-optimization (JEO). We examine recent developments on efficient and scalable iterative first-order methods for these problems, and show that these iterative methods can be viewed through the lens of online convex optimization (OCO). The standard OCO framework has seen much success for its ability to handle decision-making in dynamic, uncer...
-
作者：Zhang, Yu; Baldacci, Roberto; Sim, Melvyn; Tang, Jiafu
作者单位：Southwestern University of Finance & Economics - China; National University of Singapore; University of Bologna; National University of Singapore; Dongbei University of Finance & Economics
摘要：We study an a priori Traveling Salesman Problem with Time Windows (tsptw) in which the travel times along the arcs are uncertain and the goal is to determine within a budget constraint, a route for the service vehicle in order to arrive at the customers' locations within their stipulated time windows as well as possible. In particular, service at customer's location cannot commence before the beginning of the time window and any arrival after the end of the time window is considered late and c...
-
作者：Arjevani, Yossi; Shamir, Ohad; Shiff, Ron
作者单位：Weizmann Institute of Science
摘要：Second-order methods, which utilize gradients as well as Hessians to optimize a given function, are of major importance in mathematical optimization. In this work, we prove tight bounds on the oracle complexity of such methods for smooth convex functions, or equivalently, the worst-case number of iterations required to optimize such functions to a given accuracy. In particular, these bounds indicate when such methods can or cannot improve on gradient-based methods, whose oracle complexity is m...
-
作者：Liu, Yanli; Ryu, Ernest K.; Yin, Wotao
作者单位：University of California System; University of California Los Angeles
摘要：In this paper, we present a method for identifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting. When an optimization program is infeasible, unbounded, or pathological, the iterates of Douglas-Rachford splitting diverge. Somewhat surprisingly, such divergent iterates still provide useful information, which our method uses for identification. In addition, for strongly infeasible problems the method produces a separating hyperplane and informs the us...
-
作者：Vielma, Juan Pablo
作者单位：Massachusetts Institute of Technology (MIT)
摘要：There is often a significant trade-off between formulation strength and size in mixed integer programming. When modeling convex disjunctive constraints (e.g. unions of convex sets), adding auxiliary continuous variables can sometimes help resolve this trade-off. However, standard formulations that use such auxiliary continuous variables can have a worse-than-expected computational effectiveness, which is often attributed precisely to these auxiliary continuous variables. For this reason, there...
-
作者：Liu, Xiao; Kilinc-Karzan, Fatma; Kucukyavuz, Simge
作者单位：University System of Ohio; Ohio State University; Carnegie Mellon University; University of Washington; University of Washington Seattle
摘要：We study the polyhedral structure of a generalization of a mixing set described by the intersection of two mixing sets with two shared continuous variables, where one continuous variable has a positive coefficient in one mixing set, and a negative coefficient in the other. Our developments are motivated from a key substructure of linear joint chance-constrained programs (CCPs) with random right hand sides from a finite probability space. The CCPs of interest immediately admit a mixed-integer p...
-
作者：Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio
作者单位：Tokyo Metropolitan University; Keio University; Sapienza University Rome
摘要：In discrete convex analysis, the scaling and proximity properties for the class of L?-convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of n variables, we show here that the scaling property only holds when n2, while a proximity theorem can be established for any n, but only with a superexponential bound. This is, however, sufficient to extend the classical logarithmic com...
-
作者：Rockafellar, R. Tyrrell; Sun, Jie
作者单位：University of Washington; University of Washington Seattle; Curtin University
摘要：The concept of a stochastic variational inequality has recently been articulated in a new way that is able to cover, in particular, the optimality conditions for a multistage stochastic programming problem. One of the long-standing methods for solving such an optimization problem under convexity is the progressive hedging algorithm. That approach is demonstrated here to be applicable also to solving multistage stochastic variational inequality problems under monotonicity, thus increasing the r...
-
作者：Kanzow, Christian; Steck, Daniel
作者单位：University of Wurzburg
摘要：This paper deals with a class of cone-reducible constrained optimization problems which encompasses nonlinear programming, semidefinite programming, second-order cone programming, and any combination thereof. Using the second-order sufficient condition and a strict version of the Robinson constraint qualification, we provide a (semi-)local error bound which generalizes known results from the literature. Moreover, under the same assumptions, we prove that an augmented Lagrangian method is local...
-
作者：Allen-Zhu, Zeyuan; Orecchia, Lorenzo
作者单位：Boston University
摘要：Packing and covering linear programs (PC-LP s) form an important class of linear programs (LPs) across computer science, operations research, and optimization. Luby and Nisan(in: STOC, ACM Press, New York, 1993) constructed an iterative algorithm for approximately solving PC-LP s in nearly linear time, where the time complexity scales nearly linearly in N, the number of nonzero entries of the matrix, and polynomially in epsilon, the (multiplicative) approximation error. Unfortunately, existing...
