Mathematical Programming

最新文章

• Adjustable robust nonlinear network design without controllable elements under load scenario uncertainties AI翻译
  作者：Thuerauf, Johannes; Gruebel, Julia; Schmidt, Martin
  作者单位：Universitat Trier
  摘要：We study network design problems for nonlinear and nonconvex flow models without controllable elements under load scenario uncertainties, i.e., under uncertain injections and withdrawals. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, load scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we sh...
• Sensor network localization has a benign landscape after low-dimensional relaxation AI翻译
  作者：Criscitiello, Christopher; McRae, Andrew D.; Rebjock, Quentin; Boumal, Nicolas
  作者单位：University of Pennsylvania; Institut Polytechnique de Paris; Centre National de la Recherche Scientifique (CNRS); Ecole Nationale des Ponts et Chaussees; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
  摘要：We consider the sensor network localization problem, which is closely related to multidimensional scaling and Euclidean distance matrix completion. Given a ground truth configuration of n points in R-& ell;, we observe a subset of the pairwise distances and aim to recover the underlying configuration (up to rigid transformations). We show with a simple counterexample that the associated optimization problem is nonconvex and may admit spurious local minimizers, even when all distances are known...
• Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions AI翻译
  作者：Rotaru, Teodor; Glineur, Francois; Patrinos, Panagiotis
  作者单位：KU Leuven; Universite Catholique Louvain
  摘要：We consider gradient descent with constant stepsizes and derive exact worst-case convergence rates on the minimum gradient norm of the iterates. Our analysis covers all possible stepsizes and arbitrary upper/lower bounds on the curvature of the objective function, thus including convex, strongly convex and weakly convex (hypoconvex) objective functions. Among the challenging parts of the analysis, we note the necessity to exploit dependencies between non-consecutive iterates. While this compli...
• An exact penalty approach for equality constrained optimization over a convex set AI翻译
  作者：Xiao, Nachuan; Tang, Tianyun; Wang, Shiwei; Toh, Kim-Chuan
  作者单位：The Chinese University of Hong Kong, Shenzhen; University of Chicago; Chinese Academy of Sciences; National University of Singapore; National University of Singapore
  摘要：In this paper, we consider the nonlinear constrained optimization problem (NCP) with a constraint set 1C := {x is an element of X : c(x) = 0}, where X is a closed convex subset of Rn. We propose an exact penalty approach, named constraint dissolving approach, that transforms (NCP) into its corresponding constraint dissolving problem (CDP). The transformed problem (CDP) admits X as its feasible region with a locally Lipschitz smooth objective function. We prove that (NCP) and (CDP) share the sa...
• A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron AI翻译
  作者：Garber, Dan
  作者单位：Technion Israel Institute of Technology
  摘要：We consider the problem of minimizing a smooth and convex function over the n-dimensional spectrahedron - the set of real symmetric n & times;n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n imes n$$\end{document} positive semidefinite matrices with unit trace, which underlies numerous applications in statistics,...
• A fixed-point algorithm for matrix projections with applications in quantum information AI翻译
  作者：Brahmachari, Shrigyan; Rubboli, Roberto; Tomamichel, Marco
  作者单位：National University of Singapore; Duke University; National University of Singapore
  摘要：We develop a fixed-point iterative algorithm that computes the matrix projection with respect to the Bures distance on the set of positive definite matrices that are invariant under some symmetry. We prove that the fixed-point iteration algorithm converges exponentially fast to the optimal solution in the number of iterations. Moreover, it numerically shows fast convergence compared to the off-the-shelf semidefinite program solvers. Our algorithm, for the specific case of Bures-Wasserstein bar...
• Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth AI翻译
  作者：Davis, Damek; Drusvyatskiy, Dmitriy; Jiang, Liwei
  作者单位：University of Pennsylvania; University of Washington; University of Washington Seattle; Purdue University System; Purdue University
  摘要：A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers. In this work, we argue that this belief is inaccurate. We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function that merely exhibits fourth-order growth away from its minimizer. The adaptive stepsize we propose arises from an intriguing decomposition theorem:...
• Factorized binary polynomial optimization AI翻译
  作者：Del Pia, Alberto
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general optimization problem, which we call factorized binary polynomial optimization. In this formulation, we assume that the variables are partitioned into a fixed number of sets, and that the objective function is written as a sum of r products of linear functions, each one involving only variables in one set of the partition...
• A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem AI翻译
  作者：Proenca, Nathan Benedetto; Silva, Marcel K. de Carli; Sato, Cristiane M.; Tuncel, Levent
  作者单位：University of Waterloo; Universidade de Sao Paulo; Universidade Federal do ABC (UFABC)
  摘要：We study a weighted generalization of the fractional cut-covering problem, which we relate to the maximum cut problem via antiblocker and gauge duality. This relationship allows us to introduce a semidefinite programming (SDP) relaxation whose solutions may be rounded into fractional cut covers by sampling via the random hyperplane technique. We then provide a 1/alpha GW\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackag...
• Quantum computing inspired iterative refinement for semidefinite optimization AI翻译
  作者：Mohammadisiahroudi, Mohammadhossein; Augustino, Brandon; Sampourmahani, Pouya; Terlaky, Tamas
  作者单位：Lehigh University
  摘要：Iterative Refinement (IR) is a classical computing technique for obtaining highly precise solutions to linear systems of equations, as well as linear optimization problems. In this paper, motivated by the limited precision of quantum solvers, we develop the first IR scheme for solving semidefinite optimization (SDO) problems and explore two major impacts of the proposed IR scheme. First, we prove that the proposed IR scheme exhibits quadratic convergence of the optimality gap without any assum...