-
作者：Aissi, Hassene; Mahjoub, A. Ridha; McCormick, S. Thomas; Queyranne, Maurice
作者单位：Universite PSL; Universite Paris-Dauphine; University of British Columbia; Universite Catholique Louvain
摘要：We consider multiobjective and parametric versions of the global minimum cut problem in undirected graphs and bounded-rank hypergraphs with multiple edge cost functions. For a fixed number of edge cost functions, we show that the total number of supported non-dominated (SND) cuts is bounded by a polynomial in the numbers of nodes and edges, i.e., is strongly polynomial. This bound also applies to the combinatorial facet complexity of the problem, i.e., the maximum number of facets (linear piec...
-
作者：Lee, Jon; Vygen, Jens
作者单位：University of Michigan System; University of Michigan; University of Bonn
-
作者：Lehrer, Ehud; Teper, Roee
作者单位：Tel Aviv University; INSEAD Business School; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：The extension of set functions (or capacities) in a concave fashion, namely a concavification, is an important issue in decision theory and combinatorics. It turns out that some set-functions cannot be properly extended if the domain is restricted to be bounded. This paper examines the structure of those capacities that can be extended over a bounded domain in a concave manner. We present a property termed the sandwich property that is necessary and sufficient for a capacity to be concavifiabl...
-
作者：Ben-Tal, Aharon; den Hertog, Dick; Vial, Jean-Philippe
作者单位：Technion Israel Institute of Technology; Tilburg University; Tilburg University
摘要：In this paper we provide a systematic way to construct the robust counterpart of a nonlinear uncertain inequality that is concave in the uncertain parameters. We use convex analysis (support functions, conjugate functions, Fenchel duality) and conic duality in order to convert the robust counterpart into an explicit and computationally tractable set of constraints. It turns out that to do so one has to calculate the support function of the uncertainty set and the concave conjugate of the nonli...
-
作者：Bian, Wei; Chen, Xiaojun; Ye, Yinyu
作者单位：Harbin Institute of Technology; Hong Kong Polytechnic University; Stanford University
摘要：We propose a first order interior point algorithm for a class of non-Lipschitz and nonconvex minimization problems with box constraints, which arise from applications in variable selection and regularized optimization. The objective functions of these problems are continuously differentiable typically at interior points of the feasible set. Our first order algorithm is easy to implement and the objective function value is reduced monotonically along the iteration points. We show that the worst...
-
作者：Iiduka, Hideaki
作者单位：Meiji University
摘要：The existing algorithms for solving the convex minimization problem over the fixed point set of a nonexpansive mapping on a Hilbert space are based on algorithmic methods, such as the steepest descent method and conjugate gradient methods, for finding a minimizer of the objective function over the whole space, and attach importance to minimizing the objective function as quickly as possible. Meanwhile, it is of practical importance to devise algorithms which converge in the fixed point set qui...
-
作者：Kalaitzis, Christos; Madry, Aleksander; Newman, Alantha; Polacek, Lukas; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Royal Institute of Technology; Massachusetts Institute of Technology (MIT); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
摘要：We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integrality gap of , which matches the best known approximation algorithms, our main focus is to improve our understanding of the stronger configuration LP relaxation. In this direction, we prove that the integrality gap of the configuration LP is st...
-
作者：Diouane, Y.; Gratton, S.; Vicente, L. N.
作者单位：CERFACS; Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Universidade de Coimbra
摘要：In this paper we show how to modify a large class of evolution strategies (ES's) for unconstrained optimization to rigorously achieve a form of global convergence, meaning convergence to stationary points independently of the starting point. The type of ES under consideration recombines the parent points by means of a weighted sum, around which the offspring points are computed by random generation. One relevant instance of such an ES is covariance matrix adaptation ES (CMA-ES). The modificati...
-
作者：Averkov, Gennadiy; Basu, Amitabh
作者单位：Otto von Guericke University; Johns Hopkins University
摘要：We study the uniqueness of minimal liftings of cut-generating functions obtained from maximal lattice-free polyhedra. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polyhedra. This generalizes a previous result by Basu et al. (Math Oper Res 37(2):346-355, 2012) for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting for maximal lattice-free polyhedra. We further give a very general iterati...
-
作者：Burer, Samuel; Yang, Boshi
作者单位：University of Iowa; University of Iowa
摘要：This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with linear inequality constraints. When , or and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial time. However, it is also known that, when and at least two of the linear constraints intersect within the ball, i.e., some feasible point of the eTRS satisfies both ...
