-
作者：Sun, Hailin; Su, Che-Lin; Chen, Xiaojun
作者单位：Nanjing University of Science & Technology; University of Chicago; Hong Kong Polytechnic University
摘要：Utility-based choice models are often used to determine a consumer's purchase decision among a list of available products; to provide an estimate of product demands; and, when data on purchase decisions or market shares are available, to infer consumers' preferences over observed product characteristics. These models also serve as a building block in modeling firms' pricing and assortment optimization problems. We consider a firm's multiproduct pricing problem, in which product demands are det...
-
作者：Yousefian, Farzad; Nedic, Angelia; Shanbhag, Uday V.
作者单位：Oklahoma State University System; Oklahoma State University - Stillwater; Arizona State University; Arizona State University-Tempe; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：Traditionally, most stochastic approximation (SA) schemes for stochastic variational inequality (SVI) problems have required the underlying mapping to be either strongly monotone or monotone and Lipschitz continuous. In contrast, we consider SVIs with merely monotone and non-Lipschitzian maps. We develop a regularized smoothed SA (RSSA) scheme wherein the stepsize, smoothing, and regularization parameters are reduced after every iteration at a prescribed rate. Under suitable assumptions on the...
-
作者：Rudloff, Birgit; Ulus, Firdevs; Vanderbei, Robert
作者单位：Vienna University of Economics & Business; Ihsan Dogramaci Bilkent University; Princeton University
摘要：In this paper, a parametric simplex algorithm for solving linear vector optimization problems (LVOPs) is presented. This algorithm can be seen as a variant of the multi-objective simplex (the Evans-Steuer) algorithm (Math Program 5(1):54-72, 1973). Different from it, the proposed algorithm works in the parameter space and does not aim to find the set of all efficient solutions. Instead, it finds a solution in the sense of Lohne (Vector optimization with infimum and supremum. Springer, Berlin, ...
-
作者：de Carli Silva, Marcel K.; Tuncel, Levent
作者单位：Universidade de Sao Paulo; University of Waterloo
摘要：Lovasz theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are generalized, including the main equivalent characterizations of the theta function, the theta body of graphs, and the...
-
作者：Yu, Jiajin; Ahmed, Shabbir
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Motivated by stochastic 0-1 integer programming problems with an expected utility objective, we study the mixed-integer nonlinear set: where N is a positive integer, is a concave function, are nonnegative vectors, d is a real number and B is a positive real number. We propose a family of inequalities for the convex hull of P by exploiting submodularity of the function over and the knapsack constraint . Computational effectiveness of the proposed inequalities within a branch-and-cut framework i...
-
作者：Natarajan, Karthik; Teo, Chung-Piaw
作者单位：Singapore University of Technology & Design; National University of Singapore
摘要：We show that the complexity of computing the second order moment bound on the expected optimal value of a mixed integer linear program with a random objective coefficient vector is closely related to the complexity of characterizing the convex hull of the points where is the feasible region. In fact, we can replace the completely positive programming formulation for the moment bound on , with an associated semidefinite program, provided we have a linear or a semidefinite representation of this...
-
作者：Facchinei, Francisco; Lampariello, Lorenzo; Scutari, Gesualdo
作者单位：Sapienza University Rome; Roma Tre University; Purdue University System; Purdue University
摘要：We propose a general feasible method for nonsmooth, nonconvex constrained optimization problems. The algorithm is based on the (inexact) solution of a sequence of strongly convex optimization subproblems, followed by a step-size procedure. Key features of the scheme are: (i) it preserves feasibility of the iterates for nonconvex problems with nonconvex constraints, (ii) it can handle nonsmooth problems, and (iii) it naturally leads to parallel/distributed implementations. We illustrate the app...
-
作者：Schmidt, Mark; Le Roux, Nicolas; Bach, Francis
作者单位：University of British Columbia
摘要：We analyze the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method's iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from to O(1 / k) in general, and when the sum is strongly-convex the convergen...
-
作者：Jegelka, Stefanie; Bilmes, Jeff A.
作者单位：Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle
摘要：We study an extension of the classical graph cut problem, wherein we replace the modular (sum of edge weights) cost function by a submodular set function defined over graph edges. Special cases of this problem have appeared in different applications in signal processing, machine learning, and computer vision. In this paper, we connect these applications via the generic formulation of cooperative graph cuts, for which we study complexity, algorithms, and connections to polymatroidal network flo...
-
作者：Bolte, Jerome; Trong Phong Nguyen; Peypouquet, Juan; Suter, Bruce W.
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universidad Tecnica Federico Santa Maria; Universidad Tecnica Federico Santa Maria; United States Department of Defense; United States Air Force; US Air Force Research Laboratory; Yamaguchi University
摘要：This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-Aojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with Holderian growth). A counterexample shows that the...
