-
作者：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...
-
作者：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...
-
作者：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 ...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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 ...
-
作者：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...
-
作者：Gerstbrein, Matthew; Sanita, Laura; Verberk, Lucy
作者单位：University of Waterloo; Bocconi University; Eindhoven University of Technology
摘要：An edge-weighted, vertex-capacitated graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is called stable if the value of a maximum-weight capacity-matching equals the value of a maximum-weight fractional capacity-matching. Stable graphs play a key role in characterizing the existence of stable...
-
作者：Zamani, Moslem; Abbaszadehpeivasti, Hadi; de Klerk, Etienne
作者单位：Tilburg University; Universite Catholique Louvain
摘要：Recently, semidefinite programming performance estimation has been employed as a strong tool for the worst-case performance analysis of first order methods. In this paper, we derive new non-ergodic convergence rates for the alternating direction method of multipliers (ADMM) by using performance estimation. We give some examples which show the exactness of the given bounds. We also study the linear and R-linear convergence of ADMM in terms of dual objective. We establish that ADMM enjoys a glob...
