-
作者：Coniglio, Stefano; Furini, Fabio; Ljubic, Ivana
作者单位：University of Southampton; University of Bergamo; Sapienza University Rome; ESSEC Business School
摘要：We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of met...
-
作者：Malaguti, Enrico; Monaci, Michele; Pruente, Jonas
作者单位：University of Bologna; Dortmund University of Technology
摘要：We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for a given problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realized scenario. We analyze the complexity of the resulting problem from a theoretical viewpoint, showing that, even in case the deterministic problem can be solved in polynomia...
-
作者：Bolte, Jerome; Pauwels, Edouard
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：Counterexamples to some old-standing optimization problems in the smooth convex coercive setting are provided. We show that block-coordinate, steepest descent with exact search or Bregman descent methods do not generally converge. Other failures of various desirable features are established: directional convergence of Cauchy's gradient curves, convergence of Newton's flow, finite length of Tikhonov path, convergence of central paths, or smooth Kurdyka-Lojasiewicz inequality. All examples are p...
-
作者：Castro, Margarita P.; Cire, Andre A.; Beck, J. Christopher
作者单位：Pontificia Universidad Catolica de Chile; University of Toronto; University Toronto Scarborough; University of Toronto
摘要：Cut generation and lifting are key components for the performance of state-of-the-art mathematical programming solvers. This work proposes a new general cut-and-lift procedure that exploits the combinatorial structure of 0-1 problems via a binary decision diagram (BDD) encoding of their constraints. We present a general framework that can be applied to a wide range of binary optimization problems and show its applicability for second-order conic inequalities. We identify conditions for which o...
-
作者：Kilinc-Karzan, Fatma; Kucukyavuz, Simge; Lee, Dabeen
作者单位：Carnegie Mellon University; Northwestern University; Institute for Basic Science - Korea (IBS)
摘要：A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this paper, we first revisit basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities assoc...
-
作者：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...
