-
作者：Borwein, Jonathan M.; Giladi, Ohad
作者单位：University of Newcastle
摘要：We define convexity canonically in the setting of monoids. We show that many classical results from convex analysis hold for functions defined on such groups and semigroups, rather than only vector spaces. Some examples and counter-examples are also discussed.
-
作者：Kruger, Alexander Y.; Luke, D. Russell; Thao, Nguyen H.
作者单位：Federation University Australia; University of Gottingen; Can Tho University
摘要：We synthesize and unify notions of regularity, both of individual sets and of collections of sets, as they appear in the convergence theory of projection methods for consistent feasibility problems. Several new characterizations of regularities are presented which shed light on the relations between seemingly different ideas and point to possible necessary conditions for local linear convergence of fundamental algorithms.
-
作者：Royset, Johannes O.; Wets, Roger J. -B.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School; University of California System; University of California Davis
摘要：Applications in the areas of data fitting, forecasting, and estimation naturally lead to a rich class of constrained infinite-dimensional optimization problems over extended real-valued semicontinuous functions. We discuss a framework for dealing with such applications, even in the presence of nearly arbitrary constraints on the functions. We formulate computationally tractable approximating problems relying on piecewise polynomial semicontinuous approximations of the actual functions. The app...
-
作者：Soma, Tasuku; Yoshida, Yuichi
作者单位：University of Tokyo; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a nonnegative monotone submodular function f : Zn +. R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Giv...
-
作者：Bertsimas, Dimitris; Gupta, Vishal; Kallus, Nathan
作者单位：Massachusetts Institute of Technology (MIT); University of Southern California; Cornell University; Cornell University
摘要：Sample average approximation (SAA) is a widely popular approach to data-driven decision-making under uncertainty. Under mild assumptions, SAA is both tractable and enjoys strong asymptotic performance guarantees. Similar guarantees, however, do not typically hold in finite samples. In this paper, we propose a modification of SAA, which we term Robust SAA, which retains SAA's tractability and asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees. The key to...
-
作者：Bodur, Merve; Del Pia, Alberto; Dey, Santanu S.; Molinaro, Marco; Pokutta, Sebastian
作者单位：University of Toronto; University of Wisconsin System; University of Wisconsin Madison; University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined by this single inequality with variable bounds, and finally use the inequalities describing the integer hull as cutting-planes. Our first ma...
-
作者：Ahmed, Shabbir; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology; Virginia Polytechnic Institute & State University
摘要：Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulat...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Hildebrand, Robert
作者单位：International Business Machines (IBM); IBM USA; Virginia Polytechnic Institute & State University
摘要：We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call unimodular extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature...
-
作者：Carrizosa, Emilio; Guerrero, Vanesa; Morales, Dolores Romero
作者单位：University of Sevilla; Copenhagen Business School
摘要：In this paper we address the problem of visualizing in a bounded region a set of individuals, which has attached a dissimilarity measure and a statistical value, as convex objects. This problem, which extends the standard Multidimensional Scaling Analysis, is written as a global optimization problem whose objective is the difference of two convex functions (DC). Suitable DC decompositions allow us to use the Difference of Convex Algorithm (DCA) in a very efficient way. Our algorithmic approach...
-
作者：Maehara, Takanori; Marumo, Naoki; Murota, Kazuo
作者单位：Shizuoka University; RIKEN; University of Tokyo; Tokyo Metropolitan University
摘要：Discrete DC programming with convex extensible functions is studied. A natural approach for this problem is a continuous relaxation that extends the problem to a continuous domain and applies the algorithm in continuous DC programming. By employing a special form of continuous relaxation, which is named lin-vex extension, the produced optimal solution of the extended continuous relaxation coincides with the solution of the original discrete problem. The proposed method is demonstrated for the ...
