-
作者：Harchaoui, Zaid; Juditsky, Anatoli; Nemirovski, Arkadi
作者单位：Inria; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University System of Georgia; Georgia Institute of Technology
摘要：Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone , a norm and a smooth convex function , we want either (1) to minimize the norm over the intersection of the cone and a level set of , or (2) to minimize over the cone the sum of and a multiple of the norm. We focus on the case where (a) the dimension of the problem is too large to allow for interior point algorithms, (b) is too complicated to allow for com...
-
作者：Bonami, Pierre; Lodi, Andrea; Tramontani, Andrea; Wiese, Sven
作者单位：University of Bologna
摘要：In this paper we review the relevant literature on mathematical optimization with logical implications, i.e., where constraints can be either active or disabled depending on logical conditions to hold. In the case of convex functions, the theory of disjunctive programming allows one to formulate these logical implications as convex nonlinear programming problems in a space of variables lifted with respect to its original dimension. We concentrate on the attempt of avoiding the issue of dealing...
-
作者：Vegh, Laszlo A.; von Stengel, Bernhard
作者单位：University of London; London School Economics & Political Science; University of London; London School Economics & Political Science
摘要：This paper presents oriented pivoting systems as an abstract framework for complementary pivoting. It gives a unified simple proof that the endpoints of complementary pivoting paths have opposite sign. A special case are the Nash equilibria of a bimatrix game at the ends of Lemke-Howson paths, which have opposite index. For Euler complexes or oiks, an orientation is defined which extends the known concept of oriented abstract simplicial manifolds. Ordered room partitions for a family of orient...
-
作者：Avis, David; Tiwary, Hans Raj
作者单位：McGill University; Universite de Montreal; McGill University; Kyoto University; Universite Libre de Bruxelles
摘要：In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut po...
-
作者：Curtis, Frank E.; Jiang, Hao; Robinson, Daniel P.
作者单位：Lehigh University; Johns Hopkins University
摘要：We propose an augmented Lagrangian algorithm for solving large-scale constrained optimization problems. The novel feature of the algorithm is an adaptive update for the penalty parameter motivated by recently proposed techniques for exact penalty methods. This adaptive updating scheme greatly improves the overall performance of the algorithm without sacrificing the strengths of the core augmented Lagrangian framework, such as its ability to be implemented matrix-free. This is important as this...
-
作者：Grapiglia, Geovani N.; Yuan, Jinyun; Yuan, Ya-xiang
作者单位：Universidade Federal do Parana; Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior (CAPES); Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：A nonlinear stepsize control framework for unconstrained optimization was recently proposed by Toint (Optim Methods Softw 28:82-95, 2013), providing a unified setting in which the global convergence can be proved for trust-region algorithms and regularization schemes. The original analysis assumes that the Hessians of the models are uniformly bounded. In this paper, the global convergence of the nonlinear stepsize control algorithm is proved under the assumption that the norm of the Hessians c...
-
作者：de laat, David; Vallentin, Frank
作者单位：Delft University of Technology; University of Cologne
摘要：Packing problems in discrete geometry can be modeled as finding independent sets in infinite graphs where one is interested in independent sets which are as large as possible. For finite graphs one popular way to compute upper bounds for the maximal size of an independent set is to use Lasserre's semidefinite programming hierarchy. We generalize this approach to infinite graphs. For this we introduce topological packing graphs as an abstraction for infinite graphs coming from packing problems ...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco
作者单位：Johns Hopkins University; University of Padua
摘要：The cutting-plane approach to integer programming was initiated more than 40 years ago: Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau form and Balas introduced intersection cuts for the corner polyhedron. This line of research was left dormant for several decades until relatively recently, when a paper of Andersen, Louveaux, Weismantel and Wolsey generated renewed interest in the corner polyhedron and intersection cuts. Recent developments rely on to...
-
作者：Couetoux, Basile; Davis, James M.; Williamson, David P.
作者单位：Aix-Marseille Universite; Cornell University
摘要：We consider a class of graph problems introduced in a paper of Goemans and Williamson that involve finding forests of minimum edge cost. This class includes a number of location/routing problems; it also includes a problem in which we are given as input a parameter , and want to find a forest such that each component has at least vertices. Goemans and Williamson gave a 2-approximation algorithm for this class of problems. We give an improved 3/2-approximation algorithm.
-
作者：Gouveia, Joo; Robinson, Richard Z.; Thomas, Rekha R.
作者单位：Universidade de Coimbra; University of Washington; University of Washington Seattle
摘要：We present various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes. We prove that the psd rank of a generic -dimensional polytope with vertices is at least improving on previous lower bounds. For polygons with vertices, we show that psd rank cannot exceed which in turn shows that the psd rank of a matrix of rank three is at most . In general, a nonnegative matrix of rank has psd rank at least and we pose the problem of d...
