Mathematical Programming

最新文章

• Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient AI翻译
  作者：Latafat, Puya; Themelis, Andreas; Stella, Lorenzo; Patrinos, Panagiotis
  作者单位：KU Leuven; Kyushu University
  摘要：Backtracking linesearch is the de facto approach for minimizing continuously differentiable functions with locally Lipschitz gradient. In recent years, it has been shown that in the convex setting it is possible to avoid linesearch altogether, and to allow the stepsize to adapt based on a local smoothness estimate without any backtracks or evaluations of the function value. In this work we propose an adaptive proximal gradient method, adaPGM, that uses novel estimates of the local smoothness m...
• Convexification techniques for fractional programs AI翻译
  作者：He, Taotao; Liu, Siyue; Tawarmalani, Mohit
  作者单位：Shanghai Jiao Tong University; Carnegie Mellon University; Purdue University System; Purdue University
  摘要：This paper develops a correspondence relating convex hulls of fractional functions with those of polynomial functions over the same domain. Using this result, we develop a number of new reformulations and relaxations for fractional programming problems. First, we relate 0-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{docum...
• Sample complexity analysis for adaptive optimization algorithms with stochastic oracles AI翻译
  作者：Jin, Billy; Scheinberg, Katya; Xie, Miaolan
  作者单位：Cornell University
  摘要：Several classical adaptive optimization algorithms, such as line search and trust-region methods, have been recently extended to stochastic settings where function values, gradients, and Hessians in some cases, are estimated via stochastic oracles. Unlike the majority of stochastic methods, these methods do not use a pre-specified sequence of step size parameters, but adapt the step size parameter according to the estimated progress of the algorithm and use it to dictate the accuracy required ...
• A cutting-plane and benders' decomposition algorithm for two-stage distributionally robust convex programs AI翻译
  作者：Luo, Fengqiao; Dey, Shibshankar; Mehrotra, Sanjay
  作者单位：Northwestern University
  摘要：We present a finitely convergent cutting-plane algorithm for solving a general mixed-integer convex program given an oracle for solving a general convex program. This method is extended to solve a family of two-stage mixed-integer convex programs using cutting planes, with applications to solving distributionally-robust two-stage stochastic mixed-integer convex programs. Analysis is also given for the case where convex programming oracle provides an is an element of-optimal solution. We combin...
• On the complexity of a simple primal-dual coordinate method AI翻译
  作者：Alacaoglu, Ahmet; Cevher, Volkan; Wright, Stephen J.
  作者单位：University of British Columbia; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Wisconsin System; University of Wisconsin Madison
  摘要：We prove new complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain promising practical performance for solving convex-concave min-max problems with bilinear coupling and dual separability. Such problems arise in many machine learning contexts, including empirical risk minimization, matrix games, and image processing. Our results either match or improve the best-known complexities of first-order algorithms for ...
• A simple uniformly optimal method without line search for convex optimization AI翻译
  作者：Li, Tianjiao; Lan, Guanghui
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：Line search (or backtracking) procedures have been widely employed into first-order methods for solving convex optimization problems, especially those with unknown problem parameters (e.g., Lipschitz constant). In this paper, we show that line search is superfluous in attaining the optimal rate of convergence for solving a convex optimization problem whose parameters are not given a priori. In particular, we present a novel accelerated gradient descent type algorithm called auto-conditioned fa...
• Lower bounds on the complexity of mixed-integer programs for stable set and knapsack AI翻译
  作者：Schade, Jamico; Sinha, Makrand; Weltge, Stefan
  作者单位：Technical University of Munich; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomial-size MIP formulation requires Omega(n/log(2) n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack problems. In both cases, this improves the previously known bounds of Omega(root n/log n) by Cevallos et al. (in Proceedings of the twe...
• V-polyhedral disjunctive cuts AI翻译
  作者：Balas, Egon; Kazachkov, Aleksandr M.
  作者单位：Carnegie Mellon University; State University System of Florida; University of Florida
  摘要：We introduce V-polyhedral disjunctive cuts (VPCs) to generate valid inequalities from general disjunctions for a mixed-integer linear program. While optimization solvers critically rely on cuts, they only deploy limited families derivable from weak disjunctions, as the typical cut-generating linear program needs a costly higher-dimensional representation. The VPC framework mitigates this through a polar perspective to more efficiently use deeper, multiterm disjunctions, which partition the fea...
• Mean-semideviation-based distributionally robust learning with weakly convex losses: convergence rates and finite-sample guarantees AI翻译
  作者：Zhu, Landi; Gurbuzbalaban, Mert; Ruszczynski, Andrzej
  作者单位：Rutgers University System; Rutgers University New Brunswick
  摘要：We consider a distributionally robust stochastic optimization problem where the ambiguity sets are implicitly defined by the dual representation of the mean-semideviation risk measure. Utilizing the specific form of this risk measure, we reformulate the problem as a stochastic two-level composition optimization problem. In this setting, we consider a single time-scale algorithm, involving two versions of the inner function value tracking: linearized tracking of a continuously differentiable lo...
• Primal methods for variational inequality problems with functional constraints AI翻译
  作者：Zhang, Liang; He, Niao; Muehlebach, Michael
  作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Max Planck Society
  摘要：Variational inequality problems are recognized for their broad applications across various fields including machine learning and operations research. First-order methods have emerged as the standard approach for solving these problems due to their simplicity and scalability. However, they typically rely on projection or linear minimization oracles to navigate the feasible set, which becomes computationally expensive in practical scenarios featuring multiple functional constraints. Existing eff...