-
作者：Wang, Mengdi; Fang, Ethan X.; Liu, Han
作者单位：Princeton University; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., the problem In order to solve this stochastic composition problem, we propose a class of stochastic compositional gradient descent (SCGD) algorithms that can be viewed as stochastic versions of quasi-gradient method. SCGD update the solutio...
-
作者：Chen, Yunmei; Lan, Guanghui; Ouyang, Yuyuan
作者单位：State University System of Florida; University of Florida; University System of Georgia; Georgia Institute of Technology; Clemson University
摘要：We propose a novel stochastic method, namely the stochastic accelerated mirror-prox (SAMP) method, for solving a class of monotone stochastic variational inequalities (SVI). The main idea of the proposed algorithm is to incorporate a multi-step acceleration scheme into the stochastic mirror-prox method. The developed SAMP method computes weak solutions with the optimal iteration complexity for SVIs. In particular, if the operator in SVI consists of the stochastic gradient of a smooth function,...
-
作者：Greenbaum, Anne; Lewis, Adrian S.; Overton, Michael L.
作者单位：University of Washington; University of Washington Seattle; Cornell University; New York University
摘要：Let W(A) denote the field of values (numerical range) of a matrix A. For any polynomial p and matrix A, define the Crouzeix ratio to have numerator and denominator . Crouzeix's 2004 conjecture postulates that the globally minimal value of the Crouzeix ratio is 1 / 2, over all polynomials p of any degree and matrices A of any order. We derive the subdifferential of this ratio at pairs (p, A) for which the largest singular value of p(A) is simple. In particular, we show that at certain candidate...
-
作者：Carvalho, Margarida; Lodi, Andrea; Pedroso, Joao Pedro; Viana, Ana
作者单位：INESC TEC; Universidade do Porto; Universidade do Porto; University of Bologna; Universite de Montreal; Polytechnique Montreal; INESC TEC; Instituto Politecnico do Porto
摘要：Kidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of kidney patients being transplanted. For the case of hospital programs, it has been claimed that hospitals would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different hospitals. This claim led to the study of multi-hospital exchange markets. We propose a novel direction in this s...
-
作者：Curtis, Frank E.; Gould, Nicholas I. M.; Robinson, Daniel P.; Toint, Philippe L.
作者单位：Lehigh University; UK Research & Innovation (UKRI); Science & Technology Facilities Council (STFC); STFC Rutherford Appleton Laboratory; Johns Hopkins University; University of Namur; University of Namur
摘要：We present an interior-point trust-funnel algorithm for solving large-scale nonlinear optimization problems. The method is based on an approach proposed by Gould and Toint (Math Prog 122(1):155-196, 2010) that focused on solving equality constrained problems. Our method is similar in that it achieves global convergence guarantees by combining a trust-region methodology with a funnel mechanism, but has the additional capability of being able to solve problems with both equality and inequality c...
-
作者：Zhao, Ming; Huang, Kai; Zeng, Bo
作者单位：University of Houston System; University of Houston; McMaster University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：The essential structure of the mixed-integer programming formulation for chance-constrained program (CCP) is the intersection of multiple mixing sets with a 0-1 knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a 0-1 knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with stochastic right-hand side under a finite discrete distribution. We first present a family of strong inequalities th...
-
作者：Ravat, Uma; Shanbhag, Uday V.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：Variational inequality problems allow for capturing an expansive class of problems, including convex optimization problems, convex Nash games and economic equilibrium problems, amongst others. Yet in most practical settings, such problems are complicated by uncertainty, motivating the examination of a stochastic generalization of the variational inequality problem and its extensions in which the components of the mapping contain expectations. When the associated sets are unbounded, ascertainin...
-
作者：Burer, Samuel; Kilinc-Karzan, Fatma
作者单位：University of Iowa; Carnegie Mellon University
摘要：A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown-by several authors using different techniques-that the convex hull of the intersection of an ellipsoid, , and a split disjunction, with , equals the intersection of with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form and , where is a SOCr cone, is a nonc...
-
作者：Basu, Amitabh; Martin, Kipp; Ryan, Christopher Thomas
作者单位：Johns Hopkins University; University of Chicago
摘要：Finite-dimensional linear programs satisfy strong duality (SD) and have the dual pricing (DP) property. The DP property ensures that, given a sufficiently small perturbation of the right-hand-side vector, there exists a dual solution that correctly prices the perturbation by computing the exact change in the optimal objective function value. These properties may fail in semi-infinite linear programming where the constraint vector space is infinite dimensional. Unlike the finite-dimensional cas...
-
作者：Charitha, C.; Dutta, Joydeep; Luke, D. Russell
作者单位：University of Gottingen; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Kanpur; University of Gottingen
摘要：We examine two central regularization strategies for monotone variational inequalities, the first a direct regularization of the operative monotone mapping, and the second via regularization of the associated dual gap function. A key link in the relationship between the solution sets to these various regularized problems is the idea of exact regularization, which, in turn, is fundamentally associated with the existence of Lagrange multipliers for the regularized variational inequality. A regul...
