1-2期

最新文章

• On the polyhedrality of cross and quadrilateral closures AI翻译
  作者：Dash, Sanjeeb; Gunluk, Oktay; Moran R, Diego A.
  作者单位：International Business Machines (IBM); IBM USA; Virginia Polytechnic Institute & State University; Universidad Adolfo Ibanez
  摘要：Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook et al. (Math Program 47:155-174, 1990) showed that the split closure of a rational polyhedron P is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We then use this result to prove that cross cuts yield closures that are rational polyhedra. Cross cuts are a generalization of split cuts introduced b...
• On the worst case performance of the steepest descent algorithm for quadratic functions AI翻译
  作者：Gonzaga, Clovis C.
  作者单位：Universidade Federal de Santa Catarina (UFSC)
  摘要：The existing choices for the step lengths used by the classical steepest descent algorithm for minimizing a convex quadratic function require in the worst case iterations to achieve a precision , where C is the Hessian condition number. We show how to construct a sequence of step lengths with which the algorithm stops in iterations, with a bound almost exactly equal to that of the Conjugate Gradient method.
• A dynamic inequality generation scheme for polynomial programming AI翻译
  作者：Ghaddar, Bissan; Vera, Juan C.; Anjos, Miguel F.
  作者单位：Tilburg University; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
  摘要：Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the p...
• Distributionally robust chance constraints for non-linear uncertainties AI翻译
  作者：Yang, Wenzhuo; Xu, Huan
  作者单位：National University of Singapore
  摘要：This paper investigates the computational aspects of distributionally robust chance constrained optimization problems. In contrast to previous research that mainly focused on the linear case (with a few exceptions discussed in detail below), we consider the case where the constraints can be non-linear to the decision variable, and in particular to the uncertain parameters. This formulation is of great interest as it can model non-linear uncertainties that are ubiquitous in applications. Our ma...
• Some LCPs solvable in strongly polynomial time with Lemke's algorithm AI翻译
  作者：Adler, Ilan; Cottle, Richard W.; Pang, Jong-Shi
  作者单位：University of California System; University of California Berkeley; Stanford University; University of Southern California
  摘要：We identify a class of Linear Complementarity Problems (LCPs) that are solvable in strongly polynomial time by Lemke's Algorithm (Scheme 1) or by the Parametric Principal Pivoting Method (PPPM). This algorithmic feature for the class of problems under consideration here is attributable to the proper selection of the covering vector in Scheme 1 or the parametric direction vector in the PPPM which leads to solutions of limited and monotonically increasing support size; such solutions are sparse....
• Constraint qualifications and optimality conditions for optimization problems with cardinality constraints AI翻译
  作者：Cervinka, Michal; Kanzow, Christian; Schwartz, Alexandra
  作者单位：Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Charles University Prague; University of Wurzburg; Technical University of Darmstadt
  摘要：This paper considers optimization problems with cardinality constraints. Based on a recently introduced reformulation of this problem as a nonlinear program with continuous variables, we first define some problem-tailored constraint qualifications and then show how these constraint qualifications can be used to obtain suitable optimality conditions for cardinality constrained problems. Here, the (KKT-like) optimality conditions hold under much weaker assumptions than the corresponding result t...
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank AI翻译
  作者：Fawzi, Hamza; Parrilo, Pablo A.
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：The nonnegative rank of a matrix A is the smallest integer r such that A can be written as the sum of r rank-one nonnegative matrices. The nonnegative rank has received a lot of attention recently due to its application in optimization, probability and communication complexity. In this paper we study a class of atomic rank functions defined on a convex cone which generalize several notions of positive ranks such as nonnegative rank or cp-rank (for completely positive matrices). The main contri...
• Two pairs of families of polyhedral norms versus -norms: proximity and applications in optimization AI翻译
  作者：Gotoh, Jun-ya; Uryasev, Stan
  作者单位：Chuo University; State University System of Florida; University of Florida
  摘要：This paper studies four families of polyhedral norms parametrized by a single parameter. The first two families consist of the CVaR norm (which is equivalent to the D-norm, or the largest- norm) and its dual norm, while the second two families consist of the convex combination of the - and -norms, referred to as the deltoidal norm, and its dual norm. These families contain the - and -norms as special limiting cases. These norms can be represented using linear programming (LP) and the size of L...
• Conic version of Loewner-John ellipsoid theorem AI翻译
  作者：Seeger, Alberto; Torki, Mounir
  作者单位：Avignon Universite; Avignon Universite
  摘要：We extend John's inscribed ellipsoid theorem, as well as Loewner's circumscribed ellipsoid theorem, from convex bodies to proper cones. To be more precise, we prove that a proper cone in contains a unique ellipsoidal cone of maximal canonical volume and, on the other hand, it is enclosed by a unique ellipsoidal cone of minimal canonical volume. In addition, we explain how to construct the inscribed ellipsoidal cone . The circumscribed ellipsoidal cone is then obtained by duality arguments. The...
• A comment on computational complexity of stochastic programming problems AI翻译
  作者：Hanasusanto, Grani A.; Kuhn, Daniel; Wiesemann, Wolfram
  作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
  摘要：Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Math Program A 106(3):423-432, 2006). Amongst others, that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard even if the random problem data is governed by independent uniform distributions. We show that Dyer and Stougie's proof is not correct, and we ...