-
作者：Anthony, Martin; Boros, Endre; Crama, Yves; Gruber, Aritanan
作者单位：University of London; London School Economics & Political Science; Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick; University of Liege; Universidade de Sao Paulo
摘要：Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recent...
-
作者：Chen, Liang; Sun, Defeng; Toh, Kim-Chuan
作者单位：Hunan University; National University of Singapore; National University of Singapore
摘要：In this paper, we propose an inexact multi-block ADMM-type first-order method for solving a class of high-dimensional convex composite conic optimization problems to moderate accuracy. The design of this method combines an inexact 2-block majorized semi-proximal ADMM and the recent advances in the inexact symmetric Gauss-Seidel (sGS) technique for solving a multi-block convex composite quadratic programming whose objective contains a nonsmooth term involving only the first block-variable. One ...
-
作者：Qi, Yunwei; Sen, Suvrajeet
作者单位：University System of Ohio; Ohio State University; University of Southern California
摘要：This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first-stage approximation is solved by a branch-and-bound algorithm with its nodes inheriting Benders' cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second-stage mixe...
-
作者：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...
