2015

最新文章

• Extreme point inequalities and geometry of the rank sparsity ball AI翻译
  作者：Drusvyatskiy, D.; Vavasis, S. A.; Wolkowicz, H.
  作者单位：University of Washington; University of Washington Seattle; University of Waterloo
  摘要：We investigate geometric features of the unit ball corresponding to the sum of the nuclear norm of a matrix and the norm of its entries-a common penalty function encouraging joint low rank and high sparsity. As a byproduct of this effort, we develop a calculus (or algebra) of faces for general convex functions, yielding a simple and unified approach for deriving inequalities balancing the various features of the optimization problem at hand, at the extreme points of the solution set.
• Recent advances in trust region algorithms AI翻译
  作者：Yuan, Ya-xiang
  作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
  摘要：Trust region methods are a class of numerical methods for optimization. Unlike line search type methods where a line search is carried out in each iteration, trust region methods compute a trial step by solving a trust region subproblem where a model function is minimized within a trust region. Due to the trust region constraint, nonconvex models can be used in trust region subproblems, and trust region algorithms can be applied to nonconvex and ill-conditioned problems. Normally it is easier ...
• Dual consistent systems of linear inequalities and cardinality constrained polytopes AI翻译
  作者：Fujishige, Satoru; Massberg, Jens
  作者单位：Kyoto University; Ulm University
  摘要：We introduce a concept of dual consistency of systems of linear inequalities with full generality. We show that a cardinality constrained polytope is represented by a certain system of linear inequalities if and only if the systems of linear inequalities associated with the cardinalities are dual consistent. Typical dual consistent systems of inequalities are those which describe polymatroids, generalized polymatroids, and dual greedy polyhedra with certain choice functions. We show that the s...
• Packing in generalized kernel systems: a framework that generalizes packing of branchings AI翻译
  作者：Leston-Rey, Mario; Wakabayashi, Yoshiko
  作者单位：Universidade de Sao Paulo
  摘要：We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems in this framework which, in particular, imply an improvement over the best known upper bounds on the size of the packing, one due to Gabow and Manu, for packing arborescences from a given root, and another, due to Schrijver, for packing branchings from given root-sets in a digraph.
• -Step cycle inequalities: facets for continuous multi-mixing set and strong cuts for multi-module capacitated lot-sizing problem AI翻译
  作者：Bansal, Manish; Kianfar, Kiavash
  作者单位：Texas A&M University System; Texas A&M University College Station
  摘要：In this paper, we introduce a generalization of the continuous mixing set, which we refer to as the continuous multi-mixing set. This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We present a family of valid inequalities for the continuous multi-mixing set and identify conditions under which they are facet-defining. The cycle inequalities, -step MIR inequalities, and mixed -step MIR inequalities are special cases of ...
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex AI翻译
  作者：de Klerk, Etienne; Laurent, Monique; Sun, Zhao
  作者单位：Tilburg University; Centrum Wiskunde & Informatica (CWI)
  摘要：The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems-it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties...
• Numerical optimization for symmetric tensor decomposition AI翻译
  作者：Kolda, Tamara G.
  作者单位：United States Department of Energy (DOE); Sandia National Laboratories
  摘要：We consider the problem of decomposing a real-valued symmetric tensor as the sum of outer products of real-valued vectors. Algebraic methods exist for computing complex-valued decompositions of symmetric tensors, but here we focus on real-valued decompositions, both unconstrained and nonnegative, for problems with low-rank structure. We discuss when solutions exist and how to formulate the mathematical program. Numerical results show the properties of the proposed formulations (including one t...
• Automatic Dantzig-Wolfe reformulation of mixed integer programs AI翻译
  作者：Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Luebbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano
  作者单位：RWTH Aachen University; University of Milan; Universite PSL; Universite Paris-Dauphine; University of Bologna; Universite Paris 13
  摘要：Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That is, we perform a rigorous experimental study, which results in identifying a score to estimate...
• A globally convergent incremental Newton method AI翻译
  作者：Guerbuzbalaban, M.; Ozdaglar, A.; Parrilo, P.
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：Motivated by machine learning problems over large data sets and distributed optimization over networks, we develop and analyze a new method called incremental Newton method for minimizing the sum of a large number of strongly convex functions. We show that our method is globally convergent for a variable stepsize rule. We further show that under a gradient growth condition, convergence rate is linear for both variable and constant stepsize rules. By means of an example, we show that without th...
• A Riemannian symmetric rank-one trust-region method AI翻译
  作者：Huang, Wen; Absil, P. -A.; Gallivan, K. A.
  作者单位：State University System of Florida; Florida State University; Universite Catholique Louvain
  摘要：The well-known symmetric rank-one trust-region method-where the Hessian approximation is generated by the symmetric rank-one update-is generalized to the problem of minimizing a real-valued function over a -dimensional Riemannian manifold. The generalization relies on basic differential-geometric concepts, such as tangent spaces, Riemannian metrics, and the Riemannian gradient, as well as on the more recent notions of (first-order) retraction and vector transport. The new method, called RTR-SR...