1-2期

最新文章

• Integrality gaps for strengthened linear relaxations of capacitated facility location AI翻译
  作者：Kolliopoulos, Stavros G.; Moysoglou, Yannis
  作者单位：National & Kapodistrian University of Athens
  摘要：Metric uncapacitated facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. Capacitated facility location (Cfl) is a generalization for which there are local-search-based constant-factor approximations, while there is no known compact relaxation with constant integrality gap. This paper produces, through a host of impossibility results, the first comprehensive investigation of the effectiveness of...
• Combining sampling-based and scenario-based nested Benders decomposition methods: application to stochastic dual dynamic programming AI翻译
  作者：Rebennack, Steffen
  作者单位：Colorado School of Mines
  摘要：Nested Benders decomposition is a widely used and accepted solution methodology for multi-stage stochastic linear programming problems. Motivated by large-scale applications in the context of hydro-thermal scheduling, in 1991, Pereira and Pinto introduced a sampling-based variant of the Benders decomposition method, known as stochastic dual dynamic programming (SDDP). In this paper, we embed the SDDP algorithm into the scenario tree framework, essentially combining the nested Benders decomposi...
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization AI翻译
  作者：Ghadimi, Saeed; Lan, Guanghui; Zhang, Hongchao
  作者单位：State University System of Florida; University of Florida; Louisiana State University System; Louisiana State University
  摘要：This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are taken at each iteration depending on the total budget of stochastic samples allowed. The RSPG...
• Stronger bounds and faster algorithms for packing in generalized kernel systems AI翻译
  作者：Leston-Rey, Mario; Lee, Orlando
  作者单位：Universidade Estadual de Campinas
  摘要：In this paper, we consider integral (and fractional) packing problems in generalized kernel systems with a mixed family (gksmf). This framework generalizes combinatorial packing problems of several structures as, for instance, st-flows, arborescences, kernel systems, branchings, convex branchings, and covers in bi-set systems. We provide an algorithm, which improves by a factor of 2 on the upperbound for the size of a packing in a gksmf, provided by Leston-Rey and Wakabayashi. This in turn imp...
• The continuous knapsack set AI翻译
  作者：Dash, Sanjeeb; Guenluek, Oktay; Wolsey, Laurence A.
  作者单位：International Business Machines (IBM); IBM USA; Universite Catholique Louvain
  摘要：We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with non-negative integer and non-negative bounded continuous variables. When , this set is a generalization of the single arc flow set studied by Magnanti et al. (Math Program 60:233-250, 1993). We first show that in any facet-defining inequality, the number of distinct non-zero coefficients of the continuous variables is bounded by . Our next result is to show that when , this upper bound...
• A proximal method for composite minimization AI翻译
  作者：Lewis, A. S.; Wright, S. J.
  作者单位：Cornell University; University of Wisconsin System; University of Wisconsin Madison
  摘要：We consider minimization of functions that are compositions of convex or prox-regular functions (possibly extended-valued) with smooth vector functions. A wide variety of important optimization problems fall into this framework. We describe an algorithmic framework based on a subproblem constructed from a linearized approximation to the objective and a regularization term. Properties of local solutions of this subproblem underlie both a global convergence result and an identification property ...
• A nonsmooth Robinson's inverse function theorem in Banach spaces AI翻译
  作者：Cibulka, R.; Dontchev, A. L.
  作者单位：University of West Bohemia Pilsen; University of West Bohemia Pilsen; University of Michigan System; University of Michigan; University of Michigan System; University of Michigan
  摘要：In a recent paper, Izmailov (Math Program Ser A 147:581-590, 2014) derived an extension of Robinson's implicit function theorem for nonsmooth generalized equations in finite dimensions, which reduces to Clarke's inverse function theorem when the generalized equation is just an equation. Pales (J Math Anal Appl 209:202-220, 1997) gave earlier a generalization of Clarke's inverse function theorem to Banach spaces by employing Ioffe's strict pre-derivative. In this paper we generalize both theore...
• On conic QPCCs, conic QCQPs and completely positive programs AI翻译
  作者：Bai, Lijie; Mitchell, John E.; Pang, Jong-Shi
  作者单位：MathWorks; Rensselaer Polytechnic Institute; University of Southern California
  摘要：This paper studies several classes of nonconvex optimization problems defined over convex cones, establishing connections between them and demonstrating that they can be equivalently formulated as convex completely positive programs. The problems being studied include: a conic quadratically constrained quadratic program (QCQP), a conic quadratic program with complementarity constraints (QPCC), and rank constrained semidefinite programs. Our results do not make any boundedness assumptions on th...
• A smoothing SQP framework for a class of composite minimization over polyhedron AI翻译
  作者：Liu, Ya-Feng; Ma, Shiqian; Dai, Yu-Hong; Zhang, Shuzhong
  作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese University of Hong Kong; University of Minnesota System; University of Minnesota Twin Cities
  摘要：The composite minimization problem over a general polyhedron has received various applications in machine learning, wireless communications, image restoration, signal reconstruction, etc. This paper aims to provide a theoretical study on this problem. First, we derive the Karush-Kuhn-Tucker (KKT) optimality conditions for local minimizers of the problem. Second, we propose a smoothing sequential quadratic programming framework for solving this problem. The framework requires a (approximate) so...
• A bundle-free implicit programming approach for a class of elliptic MPECs in function space AI翻译
  作者：Hintermueller, M.; Surowiec, T.
  作者单位：Humboldt University of Berlin; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
  摘要：Using a standard first-order optimality condition for nonsmooth optimization problems, a general framework for a descent method is developed. This setting is applied to a class of mathematical programs with equilibrium constraints in function space from which a new algorithm is derived. Global convergence of the algorithm is demonstrated in function space and the results are then illustrated by numerical experiments.