Mathematical Programming

最新文章

• Spectral operators of matrices AI翻译
  作者：Ding, Chao; Sun, Defeng; Sun, Jie; Toh, Kim-Chuan
  作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; National University of Singapore; National University of Singapore; Curtin University; National University of Singapore
  摘要：The class of matrix optimization problems (MOPs) has been recognized in recent years to be a powerful tool to model many important applications involving structured low rank matrices within and beyond the optimization community. This trend can be credited to some extent to the exciting developments in emerging fields such as compressed sensing. The Lowner operator, which generates a matrix valued function via applying a single-variable function to each of the singular values of a matrix, has p...
• Binary decision rules for multistage adaptive mixed-integer optimization AI翻译
  作者：Bertsimas, Dimitris; Georghiou, Angelos
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); McGill University
  摘要：Decision rules provide a flexible toolbox for solving computationally demanding, multistage adaptive optimization problems. There is a plethora of real-valued decision rules that are highly scalable and achieve good quality solutions. On the other hand, existing binary decision rule structures tend to produce good quality solutions at the expense of limited scalability and are typically confined to worst-case optimization problems. To address these issues, we first propose a linearly parameter...
• Better s-t-tours by Gao trees AI翻译
  作者：Gottschalk, Corinna; Vygen, Jens
  作者单位：RWTH Aachen University; University of Bonn
  摘要：We consider the s-t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution x * as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of x * that has only one edge in each narrow...
• Complexity bounds for primal-dual methods minimizing the model of objective function AI翻译
  作者：Nesterov, Yu.
  摘要：We provide Frank-Wolfe (equivalent to Conditional Gradients) method with a convergence analysis allowing to approach a primal-dual solution of convex optimization problem with composite objective function. Additional properties of complementary part of the objective (strong convexity) significantly accelerate the scheme. We also justify a new variant of this method, which can be seen as a trust-region scheme applying to the linear model of objective function. For this variant, we prove also th...
• Strong formulations for quadratic optimization with M-matrices and indicator variables AI翻译
  作者：Atamturk, Alper; Gomez, Andres
  作者单位：University of California System; University of California Berkeley; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
  摘要：We study quadratic optimization with indicator variables and an M-matrix, i.e., a PSD matrix with non-positive off-diagonal entries, which arises directly in image segmentation and portfolio optimization with transaction costs, as well as a substructure of general quadratic optimization problems. We prove, under mild assumptions, that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular minimization problem. To strengthen the formulation, we decomp...
• Near-optimal stochastic approximation for online principal component estimation AI翻译
  作者：Li, Chris Junchi; Wang, Mengdi; Liu, Han; Zhang, Tong
  作者单位：Princeton University; Rutgers University System; Rutgers University New Brunswick
  摘要：Principal component analysis (PCA) has been a prominent tool for high-dimensional data analysis. Online algorithms that estimate the principal component by processing streaming data are of tremendous practical and theoretical interests. Despite its rich applications, theoretical convergence analysis remains largely open. In this paper, we cast online PCA into a stochastic nonconvex optimization problem, and we analyze the online PCA algorithm as a stochastic approximation iteration. The stocha...
• Interpreting latent variables in factor models via convex optimization AI翻译
  作者：Taeb, Armeen; Chandrasekaran, Venkat
  作者单位：California Institute of Technology; California Institute of Technology; California Institute of Technology
  摘要：Latent or unobserved phenomena pose a significant difficulty in data analysis as they induce complicated and confounding dependencies among a collection of observed variables. Factor analysis is a prominent multivariate statistical modeling approach that addresses this challenge by identifying the effects of (a small number of) latent variables on a set of observed variables. However, the latent variables in a factor model are purely mathematical objects that are derived from the observed phen...
• Submodular unsplittable flow on trees AI翻译
  作者：Adamaszek, Anna; Chalermsook, Parinya; Ene, Alina; Wiese, Andreas
  作者单位：University of Copenhagen; Aalto University; University of Warwick; Max Planck Society
  摘要：We study the Unsplittable Flow problem (UFP) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function. Our m...
• Approximations and solution estimates in optimization AI翻译
  作者：Royset, Johannes O.
  作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
  摘要：Approximation is central to many optimization problems and the supporting theory provides insight as well as foundation for algorithms. In this paper, we lay out a broad framework for quantifying approximations by viewing finite- and infinite-dimensional constrained minimization problems as instances of extended real-valued lower semicontinuous functions defined on a general metric space. Since the Attouch-Wets distance between such functions quantifies epi-convergence, we are able to obtain e...
• Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates AI翻译
  作者：Li, G.; Mordukhovich, B. S.; Nghia, T. T. A.; Pham, T. S.
  作者单位：University of New South Wales Sydney; Wayne State University; Oakland University
  摘要：The paper addresses parametric inequality systems described by polynomial functions in finite dimensions, where state-dependent infinite parameter sets are given by finitely many polynomial inequalities and equalities. Such systems can be viewed, in particular, as solution sets to problems of generalized semi-infinite programming with polynomial data. Exploiting the imposed polynomial structure together with powerful tools of variational analysis and semialgebraic geometry, we establish a far-...