-
作者：Del Pia, Alberto; Kaibel, Volker
作者单位：University of Wisconsin System; University of Wisconsin Madison
-
作者：Evens, Brecht; Pas, Pieter; Latafat, Puya; Patrinos, Panagiotis
作者单位：KU Leuven; IMT School for Advanced Studies Lucca
摘要：The proximal point algorithm (PPA) is the most widely recognized method for solving inclusion problems and serves as the foundation for many numerical algorithms. Despite this popularity, its convergence results have been largely limited to the monotone setting. In this work, we study the convergence of (relaxed) preconditioned PPA for a class of nonmonotone problems that satisfy an oblique weak Minty condition. Additionally, we study the (relaxed) Douglas-Rachford splitting (DRS) method in th...
-
作者：Gao, Bin; Peng, Renfeng; Yuan, Ya-xiang
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
摘要：In the realm of tensor optimization, the low-rank Tucker decomposition is crucial for reducing the number of parameters and for saving storage. We explore the geometry of Tucker tensor varieties-the set of tensors with bounded Tucker rank-which is notably more intricate than the well-explored matrix varieties. We give an explicit parametrization of the tangent cone of Tucker tensor varieties and leverage its geometry to develop provable gradient-related line-search methods for optimization on ...
-
作者：Chandrasekaran, Karthekeyan; Chekuri, Chandra; Fiorini, Samuel; Kulkarni, Shubhang; Weltge, Stefan
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Universite Libre de Bruxelles; Technical University of Munich
摘要：We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph G=(V,E) with non-negative vertex costs. The goal is to find a minimum cost subset of vertices S subset of V such that G-S is acyclic. FVS is a well-known NP-hard problem and does not admit a (2-& varepsilon;)-approximation for any fixed & varepsilon;>0 assuming the Unique Games Conjecture. There are combinatorial 2-approximation algorithms (Bafna et al., in: Algorithms and computatio...
-
作者：Sheriff, Mohammed Rayyan; Esfahani, Peyman Mohajerin
作者单位：Delft University of Technology
摘要：This article focuses on a class of distributionally robust optimization (DRO) problems where, unlike the growing body of the literature, the objective function is potentially nonlinear in the distribution. Existing methods to optimize nonlinear functions in probability space use the Frechet derivatives, which present both theoretical and computational challenges. Motivated by this, we propose an alternative notion for the derivative and corresponding smoothness based on Gateaux (G)-derivative ...
-
作者：Goyens, Florentin; Royer, Clement W.
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
摘要：The difficulty of minimizing a nonconvex function is in part explained by the presence of saddle points. This slows down optimization algorithms and impacts worst-case complexity guarantees. However, many nonconvex problems of interest possess a favorable structure for optimization, in the sense that saddle points can be escaped efficiently by appropriate algorithms. This strict saddle property has been extensively used in data science to derive good properties for first-order algorithms, such...
-
作者：Lewis, A. S.; Tian, Tonghua
作者单位：Cornell University
摘要：A central tool for understanding first-order optimization algorithms is the Kurdyka-& Lstrok;ojasiewicz inequality. Standard approaches to such methods rely crucially on this inequality to leverage sufficient decrease conditions involving gradients or subgradients. However, the KL property fundamentally concerns not subgradients but rather slope, a purely metric notion. By highlighting this view, and avoiding any use of subgradients, we present a simple and concise complexity analysis for firs...
-
作者：Munoz, Gonzalo; Paat, Joseph; Serrano, Felipe
作者单位：Universidad de Chile; University of British Columbia
摘要：The intersection cut framework was introduced by Balas in 1971 as a method for generating cutting planes in integer optimization. In this framework, one uses a full-dimensional convex S-free set, where S is the feasible region of the integer program, to derive a cut separating S from a non-integral vertex of a linear relaxation of S. Among all S-free sets, it is the inclusion-wise maximal ones that yield the strongest cuts. Recently, this framework has been extended beyond the integer case in ...
-
作者：Pennanen, Teemu; Perkkioe, Ari-Pekka
作者单位：University of London; King's College London; University of Munich
摘要：This paper studies duality and optimality conditions in general convex stochastic optimization problems introduced by Rockafellar and Wets in (Math Programm Stud 6:170-187, 1976). We derive an explicit dual problem in terms of two dual variables, one of which is the shadow price of information while the other one gives the marginal cost of a perturbation much like in classical Lagrangian duality. Existence of primal solutions and the absence of duality gap are obtained without compactness or b...
-
作者：Ponte, Gabriel; Fampa, Marcia; Lee, Jon
作者单位：Universidade Federal do Rio de Janeiro; University of Michigan System; University of Michigan
摘要：We develop a branch-and-bound algorithm for the integer D-optimality problem, a central problem in statistical design theory, based on two convex relaxations, employing variable-bound tightening and fast local-search procedures, testing our ideas on various test problems.
