-
作者：Liu, Minghui; Pataki, Gabor
作者单位：SAS Institute Inc; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：In conic linear programming-in contrast to linear programming-the Lagrange dual is not an exact dual: it may not attain its optimal value, or there may be a positive duality gap. The corresponding Farkas' lemma is also not exact (it does not always prove infeasibility). We describe exact duals, and certificates of infeasibility and weak infeasibility for conic LPs which are nearly as simple as the Lagrange dual, but do not rely on any constraint qualification. Some of our exact duals generaliz...
-
作者：Soledad Aronna, M.; Bonnans, J. Frederic; Kroner, Axel
作者单位：Getulio Vargas Foundation; Institut Polytechnique de Paris; Ecole Polytechnique; ENSTA Paris; Universite Paris Saclay
-
作者：Combettes, Patrick L.
作者单位：North Carolina State University
摘要：Several aspects of the interplay between monotone operator theory and convex optimization are presented. The crucial role played by monotone operators in the analysis and the numerical solution of convex minimization problems is emphasized. We review the properties of subdifferentials as maximally monotone operators and, in tandem, investigate those of proximity operators as resolvents. In particular, we study new transformations which map proximity operators to proximity operators, and establ...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
