Mathematical Programming

最新文章

• Small and strong formulations for unions of convex sets from the Cayley embedding AI翻译
  作者：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...
• On intersection of two mixing sets with applications to joint chance-constrained programs AI翻译
  作者：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...
• Scaling, proximity, and optimization of integrally convex functions AI翻译
  作者：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...
• Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging AI翻译
  作者：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...
• Improved local convergence results for augmented Lagrangian methods in C2-cone reducible constrained optimization AI翻译
  作者：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...
• Nearly linear-time packing and covering LP solvers: Achieving width-independence and -convergence AI翻译
  作者：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...
• Characterizations of mixed binary convex quadratic representable sets AI翻译
  作者：Del Pia, Alberto; Poskin, Jeffrey
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：Representability results play a fundamental role in optimization since they provide characterizations of the feasible sets that arise from optimization problems. In this paper we study the sets that appear in the feasibility version of mixed binary convex quadratic optimization problems. We provide a complete characterization of the sets that can be obtained as the projection of such feasible regions. In order to obtain this result, we first provide a complete characterization of these sets in...
• A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems AI翻译
  作者：Razaviyayn, Meisam; Hong, Mingyi; Reyhanian, Navid; Luo, Zhi-Quan
  作者单位：University of Southern California; University of Minnesota System; University of Minnesota Twin Cities; Shenzhen Research Institute of Big Data; The Chinese University of Hong Kong, Shenzhen
  摘要：Consider the classical problem of solving a general linear system of equations Ax=b. It is well known that the (successively over relaxed) Gauss-Seidel scheme and many of its variants may not converge when A is neither diagonally dominant nor symmetric positive definite. Can we have a linearly convergent G-S type algorithm that works for anyA? In this paper we answer this question affirmatively by proposing a doubly stochastic G-S algorithm that is provably linearly convergent (in the mean squ...
• Conditional gradient type methods for composite nonlinear and stochastic optimization AI翻译
  作者：Ghadimi, Saeed
  作者单位：Princeton University
  摘要：In this paper, we present a conditional gradient type (CGT) method for solving a class of composite optimization problems where the objective function consists of a (weakly) smooth term and a (strongly) convex regularization term. While including a strongly convex term in the subproblems of the classical conditional gradient method improves its rate of convergence, it does not cost per iteration as much as general proximal type algorithms. More specifically, we present a unified analysis for t...
• Identifying effective scenarios in distributionally robust stochastic programs with total variation distance AI翻译
  作者：Rahimian, Hamed; Bayraksan, Guzin; Homem-de-Mello, Tito
  作者单位：University System of Ohio; Ohio State University; Universidad Adolfo Ibanez
  摘要：Traditional stochastic programs assume that the probability distribution of uncertainty is known. However, in practice, the probability distribution oftentimes is not known or cannot be accurately approximated. One way to address such distributional ambiguity is to work with distributionally robust convex stochastic programs (DRSPs), which minimize the worst-case expected cost with respect to a set of probability distributions. In this paper we analyze the case where there is a finite number o...