2025

最新文章

• On the tightness of an SDP relaxation for homogeneous QCQP with three real or four complex homogeneous constraints AI翻译
  作者：Ai, Wenbao; Liang, Wei; Yuan, Jianhua
  作者单位：Beijing University of Posts & Telecommunications
  摘要：In this paper, we consider the problem of minimizing a general homogeneous quadratic function, subject to three real or four complex homogeneous quadratic inequality or equality constraints. For this problem, we present a sufficient and necessary test condition to detect whether its standard semi-definite programming (SDP) relaxation is tight or not. This test condition is based on only an optimal solution pair of the SDP relaxation and its dual. When the tightness is confirmed, a global optim...
• A slope generalization of Attouch theorem AI翻译
  作者：Daniilidis, Aris; Salas, David; Tapia-Garcia, Sebastian
  作者单位：Technische Universitat Wien; Universidad de O'Higgins
  摘要：A classical result of variational analysis, known as Attouch theorem, establishes an equivalence between epigraphical convergence of a sequence of proper convex lower semicontinuous functions and graphical convergence of the corresponding subdifferential maps up to a normalization condition which fixes the integration constant. In this work, we show that in finite dimensions and under a mild boundedness assumption, we can replace subdifferentials (sets of vectors) by slopes (scalars, correspon...
• The effect of smooth parametrizations on nonconvex optimization landscapes AI翻译
  作者：Levin, Eitan; Kileel, Joe; Boumal, Nicolas
  作者单位：California Institute of Technology; University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
  摘要：We develop new tools to study landscapes in nonconvex optimization. Given one optimization problem, we pair it with another by smoothly parametrizing the domain. This is either for practical purposes (e.g., to use smooth optimization algorithms with good guarantees) or for theoretical purposes (e.g., to reveal that the landscape satisfies a strict saddle property). In both cases, the central question is: how do the landscapes of the two problems relate? More precisely: how do desirable points ...
• 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...
• The computational complexity of finding stationary points in non-convex optimization AI翻译
  作者：Hollender, Alexandros; Zampetakis, Manolis
  作者单位：University of Oxford; Yale University
  摘要：Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions f over unrestricted d-dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational and query complexity of this problem are still not well understood when the dimension d of the problem is independent of the approximation error. In this paper, we show the following computational and query ...
• Gaining or losing perspective for convex multivariate functions on box domains AI翻译
  作者：Xu, Luze; Lee, Jon
  作者单位：University of California System; University of California Davis; University of Michigan System; University of Michigan
  摘要：Mixed-integer nonlinear optimization formulations of the disjunction between the origin and a polytope via a binary indicator variable is broadly used in nonlinear combinatorial optimization for modeling a fixed cost associated with carrying out a group of activities and a convex cost function associated with the levels of the activities. The perspective relaxation of such models is often used to solve to global optimality in a branch-and-bound context, but it typically requires suitable conic...