Mathematical Programming

最新文章

• Finite convergence of the Moment-SOS hierarchy for polynomial matrix optimization AI翻译
  作者：Huang, Lei; Nie, Jiawang
  作者单位：University of California System; University of California San Diego
  摘要：This paper studies the matrix Moment-SOS hierarchy for solving polynomial matrix optimization. Our first result is to show the finite convergence of this hierarchy, if the nondegeneracy condition, strict complementarity condition and second order sufficient condition hold at every minimizer, under the Archimedean property. A useful criterion for detecting the finite convergence is the flat truncation. Our second result is to show that every minimizer of the moment relaxation must have a flat t...
• Totally Δ-modular IPs with two non-zeros in most rows AI翻译
  作者：Kober, Stefan
  作者单位：Universite Libre de Bruxelles
  摘要：Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial-time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge & Yuditsky (J. ACM 72(1), 1-50 (2025)) by allowing for additional, unifying constraints and variables. Further, we ...
• Exponential convergence rates for momentum stochastic gradient descent in the overparametrized setting AI翻译
  作者：Gess, Benjamin; Kassing, Sebastian
  作者单位：University of Wuppertal; Technical University of Berlin; Max Planck Society
  摘要：We prove explicit bounds on the exponential rate of convergence for the momentum stochastic gradient descent scheme (MSGD) for arbitrary, fixed hyperparameters (learning rate, friction parameter) and its continuous-in-time counterpart in the context of non-convex optimization. The results are shown for objective functions satisfying a local Polyak-& Lstrok;ojasiewicz inequality and under assumptions on the variance of MSGD that are satisfied in overparametrized settings. Moreover, we analyze t...
• Approximation algorithm for unrooted prize-collecting forest with multiple components and its application on prize-collecting sweep coverage AI翻译
  作者：Liang, Wei; Tang, Shaojie; Zhang, Zhao
  作者单位：Zhejiang Normal University
  摘要：In this paper, we introduce a polynomial-time 2-approximation algorithm for the Unrooted Prize-Collecting Forest with K Components (URPCFK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {URPCF}_K$$\end{document}) problem. Given a graph G and an integer K, URPCFK\documentclass[12pt]{minimal} \usepackage{amsmat...
• A minimal face constant rank constraint qualification for reducible conic programming AI翻译
  作者：Andreani, Roberto; Haeser, Gabriel; Mito, Leonardo M.; Ramirez, Hector
  作者单位：Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidad de Chile; Universidad de Chile
  摘要：In a previous paper [Andreani et al, Math. Prog. 202, p. 473-514, 2023] we introduced a constant rank constraint qualification for nonlinear semidefinite and second-order cone programming by considering all faces of the underlying cone. This condition is independent of Robinson's condition and it implies a strong second-order necessary optimality condition which depends on a single Lagrange multiplier instead of the full set of Lagrange multipliers. In this paper we expand on this result in se...
• A parametric approach for solving convex quadratic optimization with indicators over trees AI翻译
  作者：Bhathena, Aaresh; Fattahi, Salar; Gomez, Andres; Kucukyavuz, Simge
  作者单位：University of Michigan System; University of Michigan; University of Southern California; Northwestern University
  摘要：This paper investigates convex quadratic optimization problems involving n indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix Q defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this problem in time and memory complexity of O(n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepa...
• Augmented Lagrangian methods for infeasible convex optimization problems and diverging proximal-point algorithms AI翻译
  作者：Andrews, Roland; Carpentier, Justin; Taylor, Adrien
  作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); Communaute Universite Grenoble Alpes; Centre National de la Recherche Scientifique (CNRS); Universite Grenoble Alpes (UGA); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble
  摘要：This work investigates the convergence behavior of augmented Lagrangian methods (ALMs) when applied to convex optimization problems that may be infeasible. ALMs are a popular class of algorithms for solving constrained optimization problems. We demonstrate that, under mild assumptions, the sequences of iterates generated by ALMs converge to solutions of the closest feasible problem. We establish progressively stronger convergence results, ranging from basic sequence convergence to more precise...
• A single-loop stochastic feasible interior-point algorithm for nonlinear inequality-constrained optimization AI翻译
  作者：Curtis, Frank E.; Jiang, Xin; Wang, Qi
  作者单位：Lehigh University
  摘要：An interior-point algorithm framework is proposed, analyzed, and tested for solving nonlinearly constrained continuous optimization problems. The main setting of interest is when the objective and inequality constraint functions may be nonlinear and/or nonconvex, and when constraint values and derivatives are tractable to compute, but objective function values and derivatives can only be estimated. The algorithm is intended primarily for a setting that is similar for stochastic-gradient method...
• Characterizations of the Aubin property of the solution mapping for nonlinear semidefinite programming AI翻译
  作者：Chen, Liang; Chen, Ruoning; Sun, Defeng; Zhang, Liping
  作者单位：Hunan University; Tsinghua University; Hong Kong Polytechnic University
  摘要：In this paper, we study the Aubin property of the Karush-Kuhn-Tucker solution mapping for the nonlinear semidefinite programming (NLSDP) problem at a locally optimal solution. In the literature, it is known that the Aubin property implies the constraint nondegeneracy by Fusek (SIAM J. Optim. 23:1041-1061, 2013) and the second-order sufficient condition by Ding et al. (SIAM J. Optim. 27:67-90, 2017). Based on the Mordukhovich criterion, here we further prove that the strong second-order suffici...
• A Bayesian composite risk approach for stochastic optimal control and Markov decision processes AI翻译
  作者：Ma, Wentao; Chen, Zhiping; Xu, Huifu
  作者单位：Xi'an Jiaotong University; Chinese University of Hong Kong
  摘要：Inspired by Shapiro et al. [], we consider a stochastic optimal control (SOC) and Markov decision process (MDP) under simultaneous epistemic and aleatoric uncertainties using Bayesian composite risk (BCR) measures. The proposed BCR-SOC/MDP model evaluates the risk of stagewise cost via a two-layer framework: the inner risk measure tackles aleatoric uncertainty conditional on a latent environment parameter, while the outer risk measure deals with the epistemic uncertainty of the inner risk unde...