2011

最新文章

• Orbital branching AI翻译
  作者：Ostrowski, James; Linderoth, Jeff; Rossi, Fabrizio; Smriglio, Stefano
  作者单位：University of Wisconsin System; University of Wisconsin Madison; Lehigh University; University of L'Aquila
  摘要：We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry that is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry while stil...
• New results on Hermitian matrix rank-one decomposition AI翻译
  作者：Ai, Wenbao; Huang, Yongwei; Zhang, Shuzhong
  作者单位：Beijing University of Posts & Telecommunications; Chinese University of Hong Kong
  摘要：In this paper, we present several new rank-one decomposition theorems for Hermitian positive semidefinite matrices, which generalize our previous results in Huang and Zhang (Math Oper Res 32(3):758-768, 2007), Ai and Zhang (SIAM J Optim 19(4):1735-1756, 2009). The new matrix rank-one decomposition theorems appear to have wide applications in theory as well as in practice. On the theoretical side, for example, we show how to further extend some of the classical results including a lemma due to ...
• Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results AI翻译
  作者：Cartis, Coralia; Gould, Nicholas I. M.; Toint, Philippe L.
  作者单位：University of Edinburgh; UK Research & Innovation (UKRI); Science & Technology Facilities Council (STFC); STFC Rutherford Appleton Laboratory; University of Oxford; University of Namur
  摘要：An Adaptive Regularisation algorithm using Cubics (ARC) is proposed for unconstrained optimization, generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser et al. (Optim Methods Softw 22(3):413-431, 2007). At each iteration of our approach, an approximate global minimizer of a local cubic regularisation of the objective fun...
• Primal and dual linear decision rules in stochastic and robust optimization AI翻译
  作者：Kuhn, Daniel; Wiesemann, Wolfram; Georghiou, Angelos
  作者单位：Imperial College London
  摘要：Linear stochastic programming provides a flexible toolbox for analyzing real-life decision situations, but it can become computationally cumbersome when recourse decisions are involved. The latter are usually modeled as decision rules, i.e., functions of the uncertain problem data. It has recently been argued that stochastic programs can quite generally be made tractable by restricting the space of decision rules to those that exhibit a linear data dependence. In this paper, we propose an effi...
• Smoothed analysis of condition numbers and complexity implications for linear programming AI翻译
  作者：Dunagan, John; Spielman, Daniel A.; Teng, Shang-Hua
  作者单位：Yale University; Microsoft; Boston University
  摘要：nn We perform a smoothed analysis of Renegar's condition number for linear programming by analyzing the distribution of the distance to ill-posedness of a linear program subject to a slight Gaussian perturbation. In particular, we show that for every n-by-d matrix (A) over bar, n-vector (b) over bar, and d-vector (c) over bar satisfying parallel to(A) over bar, (b) over bar, (c) over bar parallel to(F) <= 1and every sigma <= 1, E-A,E-b,E-c[log C(A,b,c)] = O(log(nd/sigma)), where A, b and c are...
• Pegasos: primal estimated sub-gradient solver for SVM AI翻译
  作者：Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan; Cotter, Andrew
  作者单位：Toyota Technological Institute - Chicago; Hebrew University of Jerusalem; Alphabet Inc.; Google Incorporated
  摘要：We describe and analyze a simple and effective stochastic sub-gradient descent algorithm for solving the optimization problem cast by Support Vector Machines (SVM). We prove that the number of iterations required to obtain a solution of accuracy epsilon is (O) over tilde (1/epsilon), where each iteration operates on a single training example. In contrast, previous analyses of stochastic gradient descent methods for SVMs require Omega(1/epsilon(2)) iterations. As in previously devised SVM solve...
• Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion AI翻译
  作者：Kim, Sunyoung; Kojima, Masakazu; Mevissen, Martin; Yamashita, Makoto
  作者单位：Ewha Womans University; Institute of Science Tokyo; Tokyo Institute of Technology
  摘要：A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two types, the domain-space sparsity (d-space sparsity) for the symmetric matrix variable in the objective and/or constraint...
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT AI翻译
  作者：Ibaraki, Toshihide; Imamichi, Takashi; Koga, Yuichi; Nagamochi, Hiroshi; Nonobe, Koji; Yagiura, Mutsunori
  作者单位：Nagoya University; Kwansei Gakuin University; Kyoto University; Hosei University
  摘要：MAX-2-SAT is one of the representative combinatorial problems and is known to be NP-hard. Given a set of m clauses on n propositional variables, where each clause contains at most two literals and is weighted by a positive real, MAX-2-SAT asks to find a truth assignment that maximizes the total weight of satisfied clauses. In this paper, we propose branch-and-bound exact algorithms for MAX-2-SAT utilizing three kinds of lower bounds. All lower bounds are based on a directed graph that represen...
• An interactive weight space reduction procedure for nonlinear multiple objective mathematical programming AI翻译
  作者：Mackin, Patrick D.; Roy, Asim; Wallenius, Jyrki
  作者单位：Aalto University; Black Hills State University; Arizona State University; Arizona State University-Tempe
  摘要：To make a decision that is defined by multiple, conflicting objectives it is necessary to know the relative importance of the different objectives. In this paper we present an interactive method and the underlying theory for solving multiple objective mathematical programming problems defined by a convex feasible region and concave, continuously differentiable objective functions. The relative importance of the different objectives for a decision maker is elicited by using binary comparisons o...
• An FPTAS for minimizing the product of two non-negative linear cost functions AI翻译
  作者：Goyal, Vineet; Genc-Kaya, Latife; Ravi, R.
  作者单位：Carnegie Mellon University; Massachusetts Institute of Technology (MIT)
  摘要：We consider a quadratic programming (QP) problem (Pi) of the form min x(T) Cx subject to Ax >= b, x >= 0 where C is an element of R-+(nxn), rank(C) = 1 and A is an element of R-mxn, b is an element of R-m. We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Pi) as a parameterized LP and rounding the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0-1 p...