-
作者：Nesterov, Yu
摘要：We consider a new class of huge-scale problems, the problems with sparse subgradients. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends logarithmically in the dimension. This technique is based on a recursive update of the results of matrix/vector products and the values of symmetric functions. It works...
-
作者：Fischer, Frank; Helmberg, Christoph
作者单位：Technische Universitat Chemnitz
摘要：In discrete optimization problems the progress of objects over time is frequently modeled by shortest path problems in time expanded networks, but longer time spans or finer time discretizations quickly lead to problem sizes that are intractable in practice. In convex relaxations the arising shortest paths often lie in a narrow corridor inside these networks. Motivated by this observation, we develop a general dynamic graph generation framework in order to control the networks' sizes even for ...
-
作者：Davi, Thomas; Jarre, Florian
作者单位：Heinrich Heine University Dusseldorf
摘要：The recent approach of solving large scale semidefinite programs with a first order method by minimizing an augmented primal-dual function is extended to doubly nonnegative programs. A key point governing the convergence of this approach are regularity properties of the underlying problem. Regularity of the augmented primal-dual function is established under the condition of uniqueness and strict complementarity. The application to the doubly nonnegative cone is motivated by the fact that the ...
-
作者：Dadush, Daniel; Dey, Santanu S.; Vielma, Juan Pablo
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：In this paper, we show that the Chvatal-Gomory closure of any compact convex set is a rational polytope. This resolves an open question of Schrijver (Ann Discret Math 9:291-296, 1980) for irrational polytopes, and generalizes the same result for the case of rational polytopes (Schrijver in Ann Discret Math 9:291-296, 1980), rational ellipsoids (Dey and Vielma in IPCO XIV, Lecture Notes in Computer Science, vol 6080. Springer, Berlin, pp 327-340, 2010) and strictly convex bodies (Dadush et al. ...
-
作者：Laurent, Monique; Varvitsiotis, Antonios
作者单位：Tilburg University
摘要：The Gram dimension of a graph is the smallest integer such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of , can be completed to a positive semidefinite matrix of rank at most (assuming a positive semidefinite completion exists). For any fixed the class of graphs satisfying is minor closed, hence it can be characterized by a finite list of forbidden minors. We show that the only minimal forbidden mi...
-
作者：Jofre, A.; Rockafellar, R. T.; Wets, R. J. -B.
作者单位：Universidad de Chile; Universidad de Chile; University of Washington; University of Washington Seattle; University of California System; University of California Davis
摘要：Convexity has long had an important role in economic theory, but some recent developments have featured it all the more in problems of equilibrium. Here the tools of convex analysis are applied to a basic model of incomplete financial markets in which assets are traded and money can be lent or borrowed between the present and future. The existence of an equilibrium is established with techniques that include bounds derived from the duals to problems of utility maximization. Composite variation...
-
作者：Lu, Zhaosong
作者单位：Simon Fraser University
摘要：In this paper we study general regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of the first- and second-order stationary points and hence also of local minimizers of the minimization problems. We extend some existing iterative reweighted () and () minimization methods to solve these problems and propose new variants for them in which each subproblem has a closed-form solution. Also, we provide a unified convergence analysis for these m...
-
作者：Durea, Marius; Strugariu, Radu
作者单位：Alexandru Ioan Cuza University; GH Asachi Technical University
摘要：In this work we present a general theorem concerning chain rules for linear openness of set-valued mappings acting between metric spaces. As particular cases, we obtain classical and also some new results in this field of research, including the celebrated Lyusternik-Graves Theorem. The applications deal with the study of the well-posedness of the solution mappings associated to parametric systems. Sharp estimates for the involved regularity moduli are given.
-
作者：Rockafellar, R. T.; Royset, J. O.
作者单位：University of Washington; University of Washington Seattle; United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Random variables can be described by their cumulative distribution functions, a class of nondecreasing functions on the real line. Those functions can in turn be identified, after the possible vertical gaps in their graphs are filled in, with maximal monotone relations. Such relations are known to be the subdifferentials of convex functions. Analysis of these connections yields new insights. The generalized inversion operation between distribution functions and quantile functions corresponds t...
-
作者：Beck, Amir; Sabach, Shoham
作者单位：Technion Israel Institute of Technology; Tel Aviv University
摘要：We consider a general class of convex optimization problems in which one seeks to minimize a strongly convex function over a closed and convex set which is by itself an optimal set of another convex problem. We introduce a gradient-based method, called the minimal norm gradient method, for solving this class of problems, and establish the convergence of the sequence generated by the algorithm as well as a rate of convergence of the sequence of function values. The paper ends with several illus...
