-
作者：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...
-
作者：Sur, Arnab; Birge, John R.
作者单位：University of Chicago
摘要：In this article we study the consistency of optimal and stationary (KKT) points of a stochastic non-linear optimization problem involving expectation functionals, when the underlying probability distribution associated with the random variable is weakly approximated by a sequence of random probability measures. The optimization model includes constraints with expectation functionals those are not captured in direct application of the previous results on optimality conditions exist in the liter...
-
作者：Abdi, Ahmad; Cornuejols, Gerard; Huynh, Tony; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; Monash University; Institute for Basic Science - Korea (IBS)
-
作者：Mueller, Benjamin; Munoz, Gonzalo; Gasse, Maxime; Gleixner, Ambros; Lodi, Andrea; Serrano, Felipe
作者单位：Zuse Institute Berlin; Universidad de O'Higgins; Universite de Montreal; Polytechnique Montreal
摘要：Themost important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In th...
-
作者：Shi, Bin; Du, Simon S.; Jordan, Michael, I; Su, Weijie J.
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; University of Washington; University of Washington Seattle; University of California System; University of California Berkeley; University of Pennsylvania
摘要：Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODES do not distinguish between two fundamentally different algorithms-Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) and Polyak's heavy-ball method-we study an alternative limiting process that yields high-resolution ODEs. We show that these ODES permit a general Lyapunov function framework for the ana...
-
作者：Rujeerapaiboon, Napat; Schindler, Kilian; Kuhn, Daniel; Wiesemann, Wolfram
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
摘要：The goal of scenario reduction is to approximate a given discrete distribution with another discrete distribution that has fewer atoms. We distinguish continuous scenario reduction, where the new atoms may be chosen freely, and discrete scenario reduction, where the new atoms must be chosen from among the existing ones. Using the Wasserstein distance as measure of proximity between distributions, we identify those n-point distributions on the unit ball that are least susceptible to scenario re...
