-
作者：Ryan, Christopher Thomas; Smith, Robert L.
作者单位：University of British Columbia; University of Michigan System; University of Michigan
摘要：We develop novel dual-ascent and primal-dual methods to solve infinite-horizon nonstationary deterministic dynamic programs. These methods are finitely implementable and converge in value to optimality. Moreover, the dual-ascent method produces a sequence of improving dual solutions that pointwise converge to an optimal dual solution, while the primal-dual algorithm provides a sequence of primal basic feasible solutions with value error bounds from optimality that converge to zero. Our dual-ba...
-
作者：Liberti, Leo; Sager, Sebastian; Wiegele, Angelika
作者单位：Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole Polytechnique; Otto von Guericke University; University of Klagenfurt
-
作者：Correa, R.; Hantoute, A.; Lopez, M. A.
作者单位：Universidad de O'Higgins; Universidad de Chile; Universidad de Chile; Universitat d'Alacant; Federation University Australia
摘要：In this paper we establish general formulas for the subdifferential of the pointwise supremum of convex functions, which cover and unify both the compact continuous and the non-compact non-continuous settings. From the non-continuous to the continuous setting, we proceed by a compactification-based approach which leads us to problems having compact index sets and upper semi-continuously indexed mappings, giving rise to new characterizations of the subdifferential of the supremum by means of up...
-
作者：Pena, Javier; Vera, Juan C.; Zuluaga, Luis F.
作者单位：Carnegie Mellon University; Tilburg University; Lehigh University
摘要：We give a characterization of the Hoffman constant of a system of linear constraints in Rn relative to a reference polyhedron R. Rn. The reference polyhedron R represents constraints that are easy to satisfy such as box constraints. In the special case R = Rn, we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose R. Rn is a reference polyhedron, A. Rmxn, and A( R) := {Ax : x. R}. We characterize the sharpest constant H( A| R) such that for all b. A( R) +...
-
作者：Bartz, Sedi; Bauschke, Heinz H.; Phan, Hung M.; Wang, Xianfu
作者单位：University of Massachusetts System; University of Massachusetts Lowell; University of British Columbia
摘要：Monotonicity and convex analysis arise naturally in the framework of multi-marginal optimal transport theory. However, a comprehensive multi-marginal monotonicity and convex analysis theory is still missing. To this end we study extensions of classical monotone operator theory and convex analysis into the multi-marginal setting. We characterize multi-marginal c-monotonicity in terms of classical monotonicity and firmly nonexpansive mappings. We provide Minty type, continuity and conjugacy crit...
-
作者：van der Laan, Niels; Romeijnders, Ward
作者单位：University of Groningen
摘要：We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total...
-
作者：Letchford, Adam N.; Ni, Qiang; Zhong, Zhaoyu
作者单位：Lancaster University; Lancaster University
摘要：Perspective functions have long been used to convert fractional programs into convex programs. More recently, they have been used to form tight relaxations of mixed-integer nonlinear programs with so-called indicator variables. Motivated by a practical application (maximising energy efficiency in an OFDMA system), we consider problems that have a fractional objective and indicator variables simultaneously. To obtain a tight relaxation of such problems, one must consider what we call a bi-persp...
-
作者：Berczi, Kristof; Schwarcz, Tamas
作者单位：Eotvos Lorand University; Eotvos Lorand University
摘要：One of the most intriguing unsolved questions of matroid optimization is the characterization of the existence of k disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list of conjectures that can be formulated as special cases, such as Woodall's conjecture on packing disjoint dijoins in a directed graph, or Rota's beautiful conjecture on rearrangements of bases. In the present paper we prove that the problem is difficult under the rank oracle...
-
作者：Goettlich, Simone; Hante, Falk M.; Potschka, Andreas; Schewe, Lars
作者单位：University of Mannheim; Humboldt University of Berlin; TU Clausthal; University of Edinburgh
摘要：We consider mixed-integer optimal control problems with combinatorial constraints that couple over time such as minimum dwell times. We analyze a lifting and decomposition approach into a mixed-integer optimal control problem without combinatorial constraints and a mixed-integer problem for the combinatorial constraints in the control space. Both problems can be solved very efficiently with existing methods such as outer convexification with sum-up-rounding strategies and mixed-integer linear ...
-
作者：Chen, Zhongzhu; Fampa, Marcia; Lambert, Amelie; Lee, Jon
作者单位：University of Michigan System; University of Michigan; Universidade Federal do Rio de Janeiro; heSam Universite; Conservatoire National Arts & Metiers (CNAM)
摘要：The maximum-entropy sampling problem is a fundamental and challenging combinatorial-optimization problem, with application in spatial statistics. It asks to find a maximum-determinant order-s principal submatrix of an order-n covariance matrix. Exact solution methods for this NP-hard problem are based on a branch-and-bound framework. Many of the known upper bounds for the optimal value are based on convex optimization. We present a methodology for mixing these bounds to achieve better bounds.
