-
作者：Ahmed, Shabbir; Cabral, Filipe Goulart; Paulo da Costa, Bernardo Freitas
作者单位：University System of Georgia; Georgia Institute of Technology; Universidade Federal do Rio de Janeiro
摘要：We propose a new algorithm for solving multistage stochastic mixed integer linear programming (MILP) problems with complete continuous recourse. In a similar way to cutting plane methods, we construct nonlinear Lipschitz cuts to build lower approximations for the non-convex cost-to-go functions. An example of such a class of cuts are those derived using Augmented Lagrangian Duality for MILPs. The family of Lipschitz cuts we use is MILP representable, so that the introduction of these cuts does...
-
作者：Zhang, Shixuan; Sun, Xu Andy
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT)
摘要：In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with non-Lipschitzian value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based o...
-
作者：Banholzer, Dirk; Fliege, Jorg; Werner, Ralf
作者单位：University of Southampton; University of Augsburg
摘要：We study the rates at which optimal estimators in the sample average approximation approach converge to their deterministic counterparts in the almost sure sense and in mean. To be able to quantify these rates, we consider the law of the iterated logarithm in a Banach space setting and first establish under relatively mild assumptions almost sure convergence rates for the approximating objective functions, which can then be transferred to the estimators for optimal values and solutions of the ...
-
作者：Fujishige, Satoru; Tardella, Fabio
作者单位：Kyoto University; University of Florence
摘要：We focus on a new class of integrally convex functions which we call discrete 2-convex functions. Discrete 2-convexity generalizes known classes of integrally convex functions such as the well-established M-/M-(sic)-convex and L-/L-(sic)-convex functions by Murota et al., the recently investigated globally/locally discrete midpoint convex functions by Moriguchi, Murota, Tamura, and Tardella, the directed discrete midpoint convex functions by Tamura and Tsurumi, and BS*- convex and UJ-convex fu...
-
作者：Barmann, Andreas; Schneider, Oskar
作者单位：University of Erlangen Nuremberg; Fraunhofer Gesellschaft
摘要：In the present work, we consider Zuckerberg's method for geometric convex-hull proofs introduced in Zuckerberg (Oper Res Lett 44(5):625-629, 2016). It has only been scarcely adopted in the literature so far, despite the great flexibility in designing algorithmic proofs for the completeness of polyhedral descriptions that it offers. We suspect that this is partly due to the rather heavy algebraic framework its original statement entails. This is why we present a much more lightweight and access...
-
作者：Gupta, Swati; Khodabakhsh, Ali; Mortagy, Hassan; Nikolova, Evdokia
作者单位：University System of Georgia; Georgia Institute of Technology; University of Texas System; University of Texas Austin
摘要：The network reconfiguration problem seeks to find a rooted tree T such that the energy of the (unique) feasible electrical flow over T is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the...
-
作者：Ho-Nguyen, Nam; Kilinc-Karzan, Fatma; Kucukyavuz, Simge; Lee, Dabeen
作者单位：University of Sydney; Carnegie Mellon University; Northwestern University; Institute for Basic Science - Korea (IBS)
摘要：We consider exact deterministic mixed-integer programming (MIP) reformulations of distributionally robust chance-constrained programs (DR-CCP) with random right-hand sides over Wasserstein ambiguity sets. The existing MIP formulations are known to have weak continuous relaxation bounds, and, consequently, for hard instances with small radius, or with large problem sizes, the branch-and-bound based solution processes suffer from large optimality gaps even after hours of computation time. This s...
-
作者：Kiszka, Adriana; Wozabal, David
作者单位：Technical University of Munich
摘要：In this paper, we propose a semi-metric for Markov processes that allows to bound optimal values of linear Markovian stochastic optimization problems. Similar to existing notions of distance for general stochastic processes, our distance is based on transportation metrics. As opposed to the extant literature, the proposed distance is problem specific, i.e., dependent on the data of the problem whose objective value we want to bound. As a result, we are able to consider problems with randomness...
-
作者：Rontsis, Nikitas; Goulart, Paul J.; Nakatsukasa, Yuji
作者单位：University of Oxford; University of Oxford; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：We present an algorithm for the minimization of a nonconvex quadratic function subject to linear inequality constraints and a two-sided bound on the 2-norm of its solution. The algorithm minimizes the objective using an active-set method by solving a series of trust-region subproblems (TRS). Underpinning the efficiency of this approach is that the global solution of the TRS has been widely studied in the literature, resulting in remarkably efficient algorithms and software. We extend these res...
-
作者：Blekherman, Grigoriy; Dey, Santanu S.; Molinaro, Marco; Sun, Shengding
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k x k principal submatrices-we call this the sparse SDP relaxation. Surprisingly, it has been observed empirically that in some cases this approach appears to produce bounds that are close to the optimal objectiv...
