2026

最新文章

• Complexity of trust-region methods with potentially unbounded Hessian approximations for smooth and nonsmooth optimization AI翻译
  作者：Leconte, Geoffroy; Orban, Dominique
  作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal
  摘要：We develop a worst-case evaluation complexity bound for trust-region methods in the presence of unbounded Hessian approximations. We use the algorithm of Aravkin et al. (SIAM J Optim 32(2):900-929, 2022) as a model, which is designed for nonsmooth regularized problems, but applies to unconstrained smooth problems as a special case. Our analysis assumes that the growth of the Hessian approximation is controlled by the number of successful iterations. We show that the best known complexity bound...
• A novel catalyst scheme for stochastic minimax optimization AI翻译
  作者：Lan, Guanghui; Li, Yan
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：This paper presents a proximal-point-based catalyst scheme for simple first-order methods applied to convex minimization and convex-concave minimax problems. In particular, for smooth and (strongly)-convex minimization problems, the proposed catalyst scheme, instantiated with a simple variant of stochastic gradient method, attains the optimal rate of convergence in terms of both deterministic and stochastic errors. For smooth and strongly-convex-strongly-concave minimax problems, the catalyst ...
• Composite optimization with indicator functions: stationary duality and a semismooth newton method AI翻译
  作者：Zhang, Penghe; Xiu, Naihua; Qi, Houduo
  作者单位：Hong Kong Polytechnic University; Beijing Jiaotong University; Hong Kong Polytechnic University; Hong Kong Polytechnic University
  摘要：Indicator functions of taking values of zero or one are essential to numerous applications in machine learning and statistics. The corresponding primal optimization model has been researched in several recent works. However, its dual problem is a more challenging topic that has not been well addressed. One possible reason is that the Fenchel conjugate of any indicator function is finite only at the origin. This work aims to explore the dual optimization for the sum of a strongly convex functio...
• Bounding the optimal number of policies for robust K-Adaptability AI翻译
  作者：Kurtz, Jannis
  作者单位：University of Amsterdam
  摘要：In the realm of robust optimization the k-adaptability approach is one promising method to derive approximate solutions for two-stage robust optimization problems. Instead of allowing all possible second-stage decisions, the k-adaptability approach aims at calculating a limited set of k such decisions already in the first-stage before the uncertainty is revealed. The parameter k can be adjusted to control the quality of the approximation. However, not much is known on how many solutions k are ...
• Exact approaches for convex adjustable robust optimization AI翻译
  作者：Lefebvre, Henri; Malaguti, Enrico; Monaci, Michele
  作者单位：Universitat Trier; University of Bologna
  摘要：Adjustable Robust Optimization (ARO) is a paradigm for facing uncertainty in a decision problem, in case some recourse actions are allowed after the actual value of all input parameters is revealed. While several approaches have been introduced for the linear case, little is known regarding exact methods for the convex case. In this work, we introduce a new general framework for attacking a wide class of ARO problems involving convex functions in the recourse problem. We first recall a semi-in...
• The two-stripe symmetric circulant TSP is in P AI翻译
  作者：Gutekunst, Samuel C.; Jin, Billy; Williamson, David P.
  作者单位：Bucknell University; Cornell University; Purdue University System; Purdue University
  摘要：The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of the input, remarkably little is known about the symmetric circulant TSP, and the complexity of the problem has been an often-cited open question. Considerable effort has been made to understand the case in which only edges of two lengths are allowed to have finite cost: the two-stripe symmetric circulant TSP. In this ...
• Projection onto hyperbolicity cones and beyond: a dual Frank-Wolfe approach AI翻译
  作者：Nagano, Takayuki; Lourenco, Bruno F.; Takeda, Akiko
  作者单位：University of Tokyo; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; RIKEN
  摘要：We discuss the problem of projecting a point onto an arbitrary hyperbolicity cone from both theoretical and numerical perspectives. While hyperbolicity cones are furnished with a generalization of the notion of eigenvalues, obtaining closed form expressions for the projection operator as in the case of semidefinite matrices is an elusive endeavour. To address that we propose a Frank-Wolfe method to handle this task and, more generally, strongly convex optimization over closed convex cones. One...
• Accelerated first-order optimization under nonlinear constraints AI翻译
  作者：Muehlebach, Michael; Jordan, Michael I.
  作者单位：Max Planck Society; University of California System; University of California Berkeley
  摘要：We exploit analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems to design a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected gradients, these algorithms avoid optimization over the entire feasible set at each iteration. We prove convergence to stationary points even in a nonconvex setting and we derive accelerated rates for the convex setting both in continuous time, as well as in dis...
• Minimax-optimal Halpern iterations for Lipschitz maps AI翻译
  作者：Bravo, Mario; Cominetti, Roberto; Lee, Jongmin
  作者单位：Universidad de Santiago de Chile; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile; Seoul National University (SNU)
  摘要：This paper investigates the minimax-optimality of Halpern fixed-point iterations for Lipschitz maps in general normed spaces. Starting from an a priori bound on the orbit of iterates, we derive non-asymptotic estimates for the fixed-point residuals. These bounds are tight, meaning that they are attained by a suitable Lipschitz map and an associated Halpern sequence. By minimizing these tight bounds we identify the minimax-optimal Halpern scheme. For contractions, the optimal iteration exhibits...
• On integer programs with irrational data AI翻译
  作者：Hosseinian, Seyedmohammadhossein; Schaefer, Andrew J.
  作者单位：North Carolina State University; Rice University
  摘要：An integer program (IP) with a finite number of feasible solutions may have an unbounded continuous relaxation if it contains irrational parameters, due to implicit constraints induced by those irrational numbers. For IPs with polynomial constraints, we show that these implicit constraints can be derived explicitly when the irrational parameters belong to an extension field of the rational numbers by roots of integers, leading to a rational reformulation. We also present a weaker result for IP...