-
作者：Chandra, Ashish; Tawarmalani, Mohit
作者单位：Purdue University System; Purdue University
摘要：This paper develops various optimization techniques to estimate probability of events where the optimal value of a convex program, satisfying certain structural assumptions, exceeds a given threshold. First, we relate the search of affine/polynomial policies for the robust counterpart to existing relaxation hierarchies in MINLP (Lasserre in Proceedings of the international congress of mathematicians (ICM 2018), 2019; Sherali and Adams in A reformulation-linearization technique for solving disc...
-
作者：Wei, Linchuan; Gomez, Andres; Kucukyavuz, Simge
作者单位：Northwestern University; University of Southern California
摘要：Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give the convex hull description of the epigraph of the composition of a o...
-
作者：Klein, Kim-Manuel
作者单位：University of Kiel
摘要：We consider so called 2-stage stochastic integer programs (IPs) and their generalized form, so calledmulti-stage stochastic IPs. A2-stage stochastic IP is an integer program of the form max{c(T) x vertical bar Ax = b, l <= x <= u, x epsilon Z(s+nt)} where the constraint matrix A epsilon Z(rnxs+nt) consists roughly of n repetitions of a matrix A epsilon Z(rxs) on the vertical line and n repetitions of a matrix B epsilon Z(rxt) on the diagonal. In this paper we improve upon an algorithmic result...
-
作者：Attouch, Hedy; Chbani, Zaki; Fadili, Jalal; Riahi, Hassan
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Montpellier; Cadi Ayyad University of Marrakech; Universite de Caen Normandie; Centre National de la Recherche Scientifique (CNRS)
摘要：In a Hilbert space setting, for convex optimization, we analyze the convergence rate of a class of first-order algorithms involving inertial features. They can be interpreted as discrete time versions of inertial dynamics involving both viscous and Hessian-driven dampings. The geometrical damping driven by the Hessian intervenes in the dynamics in the form del(2) f (x(t)).x(t). By treating this term as the time derivative of del f (x(t)), this gives, in discretized form, first-order algorithms...
-
作者：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)
摘要：A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer k >= 4, every k-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it for k = 4 for the class of binary clutters. Two key ingredients for our proof are Jaeger's 8-flow theorem for graphs, and Seymour's characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture,...
-
作者：Noyan, Nilay; Merakli, Merve; Kucukyavuz, Simge
作者单位：Sabanci University; Northwestern University
摘要：In this study, we consider two classes of multicriteria two-stage stochastic programs in finite probability spaces with multivariate risk constraints. The first-stage problem features multivariate stochastic benchmarking constraints based on a vector-valued random variable representing multiple and possibly conflicting stochastic performance measures associated with the second-stage decisions. In particular, the aim is to ensure that the decision-based random outcome vector of interest is pref...
-
作者：Beer, G.; Canovas, M. J.; Lopez, M. A.; Parra, J.
作者单位：California State University System; California State University Los Angeles; Universidad Miguel Hernandez de Elche; Universitat d'Alacant; Federation University Australia
-
作者：Zhang, Haixiang; Milzarek, Andre; Wen, Zaiwen; Yin, Wotao
作者单位：University of California System; University of California Berkeley; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shenzhen Institute of Artificial Intelligence & Robotics for Society; Peking University; Peking University; University of California System; University of California Los Angeles
摘要：This paper considers the problem of solving a special quartic-quadratic optimization problem with a single sphere constraint, namely, finding a global and local minimizer of 1/2z*Az + beta/2 Sigma(n)(k=1) vertical bar z(k)vertical bar(4) such that parallel to z parallel to(2) = 1. This problem spans multiple domains including quantum mechanics and chemistry sciences and we investigate the geometric properties of this optimization problem. Fourth-order optimality conditions are derived for char...
-
作者：Doikov, Nikita; Nesterov, Yurii
摘要：In this paper, we study local convergence of high-order Tensor Methods for solving convex optimization problems with composite objective. We justify local superlinear convergence under the assumption of uniform convexity of the smooth component, having Lipschitz-continuous high-order derivative. The convergence both in function value and in the norm of minimal subgradient is established. Global complexity bounds for the Composite Tensor Method in convex and uniformly convex cases are also disc...
-
作者：Bruggmann, Simon; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the second step, where elements are dropped, is typically randomized. This leads to an additional source of randomization w...
