-
作者：Wang, Alex L.; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University; Purdue University System; Purdue University
摘要：This paper introduces a new storage-optimal first-order method, CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the exact QMP-like SDPs, is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. Crucially, we show how to use a certificate of strict complementarity to construct a low-dimensiona...
-
作者：Del Pia, Alberto; Kaibel, Volker
作者单位：University of Wisconsin System; University of Wisconsin Madison
-
作者：Lu, Zhaosong; Mei, Sanyou
作者单位：University of Minnesota System; University of Minnesota Twin Cities
摘要：In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method developed in this paper. Under some suitable assumptions, an operation complexity of O(epsilon-4log epsilon-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} ...
-
作者：Hoppenot, Pierre; Martin, Mathis; Szigeti, Zoltan
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：The seminal papers of Edmonds (Combinatorial algorithms, Academic Press, New York, 1973), Nash-Williams (J Lond Math Soc 36:445-450, 1961) and Tutte (J Lond Math Soc 36:221-230, 1961) have laid the foundations of the theories of packing arborescences and packing trees. The directed version has been extensively investigated, resulting in a great number of generalizations. In contrast, the undirected version has been marginally considered. The aim of this paper is to further develop the theories...
-
作者：Lu, Haihao; Yang, Jinwen
作者单位：Massachusetts Institute of Technology (MIT); University of Chicago
摘要：We study the convergence behaviors of primal-dual hybrid gradient (PDHG) for solving linear programming (LP). PDHG is the base algorithm of a new general-purpose first-order method LP solver, PDLP, which aims to scale up LP by taking advantage of modern computing architectures. Despite its numerical success, the theoretical understanding of PDHG for LP is still very limited; the previous complexity result relies on the global Hoffman constant of the KKT system, which is known to be very loose ...
-
作者：Belotti, Pietro
作者单位：Polytechnic University of Milan
摘要：We consider an n-variate monomial function that is restricted both in value by lower and upper bounds and in domain by two homogeneous linear inequalities. Monomial functions are building blocks for the class of Mixed Integer Nonlinear Optimization problems, which has many practical applications. We show that the upper envelope of the function in the given domain, for n >= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepa...
-
作者：Hu, Jian; Zhang, Dali; Xu, Huifu; Zhang, Sainan
作者单位：University of Michigan System; University of Michigan Dearborn; Shanghai Jiao Tong University; Chinese University of Hong Kong
摘要：Utility preference robust optimization (PRO) has recently been proposed to deal with optimal decision-making problems where the decision maker's (DM's) preference over gains and losses is ambiguous. In this paper, we take a step further to investigate the case that the DM's preference is random. We propose to use a random utility function to describe the DM's preference and develop distributional utility preference robust optimization (DUPRO) models when the distribution of the random utility ...
-
作者：Sudakov, Benny; Tomon, Istvan
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Umea University
摘要：Given an mxn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\times n$$\end{document} binary matrix M with |M|=pmn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargi...
-
作者：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...
