Mathematical Programming

最新文章

• New approaches to multi-objective optimization AI翻译
  作者：Grandoni, Fabrizio; Ravi, R.; Singh, Mohit; Zenklusen, Rico
  作者单位：Universita della Svizzera Italiana; Carnegie Mellon University; McGill University; Swiss Federal Institutes of Technology Domain; ETH Zurich
  摘要：A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes ...
• Bundle methods for sum-functions with easy components: applications to multicommodity network design AI翻译
  作者：Frangioni, Antonio; Gorgone, Enrico
  作者单位：University of Pisa; University of Calabria
  摘要：We propose a version of the bundle scheme for convex nondifferentiable optimization suitable for the case of a sum-function where some of the components are easy, that is, they are Lagrangian functions of explicitly known compact convex programs. This corresponds to a stabilized partial Dantzig-Wolfe decomposition, where suitably modified representations of the easy convex subproblems are inserted in the master problem as an alternative to iteratively inner-approximating them by extreme points...
• Optimality conditions for maximizing a function over a polyhedron AI翻译
  作者：Hager, William W.; Hungerford, James T.
  作者单位：State University System of Florida; University of Florida
  摘要：We present new first and second-order optimality conditions for maximizing a function over a polyhedron. These conditions are expressed in terms of the first and second-order directional derivatives along the edges of the polyhedron, and an edge description of the polyhedron. If the objective function is quadratic and edge-convex, and the constraint polyhedron includes a box constraint, then local optimality can be checked in polynomial time. The theory is applied to continuous formulations of...
• An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions AI翻译
  作者：Facchinei, Francisco; Fischer, Andreas; Herrich, Markus
  作者单位：Sapienza University Rome; Technische Universitat Dresden
  摘要：We define a new Newton-type method for the solution of constrained systems of equations and analyze in detail its properties. Under suitable conditions, that do not include differentiability or local uniqueness of solutions, the method converges locally quadratically to a solution of the system, thus filling an important gap in the existing theory. The new algorithm improves on known methods and, when particularized to KKT systems derived from optimality conditions for constrained optimization...
• Passivity and complementarity AI翻译
  作者：Camlibel, M. K.; Iannelli, L.; Vasca, F.
  作者单位：University of Groningen; Dogus University; University of Sannio
  摘要：This paper studies the interaction between the notions of passivity of systems theory and complementarity of mathematical programming in the context of complementarity systems. These systems consist of a dynamical system (given in the form of state space representation) and complementarity relations. We study existence, uniqueness, and nature of solutions for this system class under a passivity assumption on the dynamical part. A complete characterization of the initial states and the inputs f...
• Monotonic stable solutions for minimum coloring games AI翻译
  作者：Hamers, H.; Miquel, S.; Norde, H.
  作者单位：Tilburg University; Tilburg University; Universitat de Lleida
  摘要：For the class of minimum coloring games (introduced by Deng et al. Math Oper Res, 24:751-766, 1999) we investigate the existence of population monotonic allocation schemes (introduced by Sprumont Games Econ Behav 2:378-394, 1990). We show that a minimum coloring game on a graph has a population monotonic allocation scheme if and only if is -free (or, equivalently, if its complement graph is quasi-threshold). Moreover, we provide a procedure that for these graphs always selects an integer popul...
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems AI翻译
  作者：Hemmecke, Raymond; Koeppe, Matthias; Weismantel, Robert
  作者单位：Technical University of Munich; University of California System; University of California Davis; Swiss Federal Institutes of Technology Domain; ETH Zurich
  摘要：We consider -fold -block decomposable integer programs, which simultaneously generalize -fold integer programs and two-stage stochastic integer programs with scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our...
• Bilevel programming and the separation problem AI翻译
  作者：Lodi, Andrea; Ralphs, Ted K.; Woeginger, Gerhard J.
  作者单位：University of Bologna; Lehigh University; Eindhoven University of Technology
  摘要：In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxa...
• A Frank-Wolfe type theorem for nondegenerate polynomial programs AI翻译
  作者：Si Tiep Dinh; Huy Vui Ha; Tien Son Pham
  作者单位：Vietnam Academy of Science & Technology (VAST)
  摘要：In this paper, we study the existence of optimal solutions to a constrained polynomial optimization problem. More precisely, let and be convenient polynomial functions, and let Under the assumption that the map is non-degenerate at infinity, we show that if is bounded from below on then attains its infimum on.
• Strong Abadie CQ, ACQ, calmness and linear regularity AI翻译
  作者：Wei, Zhou; Yao, Jen-Chih; Zheng, Xi Yin
  作者单位：Yunnan University; Kaohsiung Medical University; National Sun Yat Sen University
  摘要：The Abadie CQ (ACQ) for convex inequality systems is a fundamental notion in optimization and approximation theory. In terms of the contingent cone and tangent derivative, we extend the Abadie CQ to more general convex multifunction cases and introduce the strong ACQ for both multifunctions and inequality systems. Some seemly unrelated notions are unified by the new ACQ and strong ACQ. Relationships among ACQ, strong ACQ, basic constraint qualification (BCQ) and strong BCQ are discussed. Using...