Mathematical Programming

最新文章

• An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization AI翻译
  作者：Yang, Heng; Liang, Ling; Carlone, Luca; Toh, Kim-Chuan
  作者单位：National University of Singapore; Massachusetts Institute of Technology (MIT); National University of Singapore; National University of Singapore
  摘要：We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone...
• Error bounds, facial residual functions and applications to the exponential cone AI翻译
  作者：Lindstrom, Scott B.; Lourenco, Bruno F.; Pong, Ting Kei
  作者单位：Curtin University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; Hong Kong Polytechnic University
  摘要：We construct a general framework for deriving error bounds for conic feasibility problems. In particular, our approach allows one to work with cones that fail to be amenable or even to have computable projections, two previously challenging barriers. For the purpose, we first show how error bounds may be constructed using objects called one-step facial residual functions. Then, we develop several tools to compute these facial residual functions even in the absence of closed form expressions fo...
• An optimal gradient method for smooth strongly convex minimization AI翻译
  作者：Taylor, Adrien; Drori, Yoel
  作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS)
  摘要：We present an optimal gradient method for smooth strongly convex optimization. The method is optimal in the sense that its worst-case bound on the distance to an optimal point exactly matches the lower bound on the oracle complexity for the class of problems, meaning that no black-box first-order method can have a better worst-case guarantee without further assumptions on the class of problems at hand. In addition, we provide a constructive recipe for obtaining the algorithmic parameters of th...
• On the implementation and strengthening of intersection cuts for QCQPs AI翻译
  作者：Chmiela, Antonia; Munoz, Gonzalo; Serrano, Felipe
  作者单位：Zuse Institute Berlin; Universidad de O'Higgins
  摘要：The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm-a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations b...
• A finite time combinatorial algorithm for instantaneous dynamic equilibrium flows AI翻译
  作者：Graf, Lukas; Harks, Tobias
  摘要：Instantaneous dynamic equilibrium (IDE) is a standard game-theoretic concept in dynamic traffic assignment in which individual flow particles myopically select en route currently shortest paths towards their destination. We analyze IDE within the Vickrey bottleneck model, where current travel times along a path consist of the physical travel times plus the sum of waiting times in all the queues along a path. Although IDE have been studied for decades, several fundamental questions regarding eq...
• Lyapunov stability of the subgradient method with constant step size AI翻译
  作者：Josz, Cedric; Lai, Lexiao
  作者单位：Columbia University
  摘要：We consider the subgradient method with constant step size for minimizing locally Lipschitz semi-algebraic functions. In order to analyze the behavior of its iterates in the vicinity of a local minimum, we introduce a notion of discrete Lyapunov stability and propose necessary and sufficient conditions for stability.
• Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems AI翻译
  作者：Doron, Lior; Shtern, Shimrit
  作者单位：Technion Israel Institute of Technology
  摘要：Simple bilevel problems are optimization problems in which we want to find an optimal solution to an inner problem that minimizes an outer objective function. Such problems appear in many machine learning and signal processing applications as a way to eliminate undesirable solutions. In our work, we suggest a new approach that is designed for bilevel problems with simple outer functions, such as the l1 norm, which are not required to be either smooth or strongly convex. In our new ITerative Ap...
• Trace ratio optimization with an application to multi-view learning AI翻译
  作者：Wang, Li; Zhang, Lei-Hong; Li, Ren-Cang
  作者单位：University of Texas System; University of Texas Arlington; University of Texas System; University of Texas Arlington; Soochow University - China; Hong Kong Baptist University
  摘要：A trace ratio optimization problem over the Stiefel manifold is investigated from the perspectives of both theory and numerical computations. Necessary conditions in the form of nonlinear eigenvalue problem with eigenvector dependency (NEPv) are established and a numerical method based on the self-consistent field (SCF) iteration with a postprocessing step is designed to solve the NEPv and the method is proved to be always convergent. As an application to multi-view subspace learning, a new fr...
• Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations AI翻译
  作者：Hu, Shenglong; Ye, Ke
  作者单位：Hangzhou Dianzi University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
  摘要：Low rank orthogonal tensor approximation (LROTA) is an important problem in tensor computations and their applications. A classical and widely used algorithm is the alternating polar decomposition method (APD). In this paper, an improved version iAPD of the classical APD is proposed. For the first time, all of the following four fundamental properties are established for iAPD: (i) the algorithm converges globally and the whole sequence converges to a KKT point without any assumption; (ii) it e...
• An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangians AI翻译
  作者：Na, Sen; Anitescu, Mihai; Kolar, Mladen
  作者单位：University of California System; University of California Berkeley; United States Department of Energy (DOE); Argonne National Laboratory; University of Chicago
  摘要：We consider solving nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We assume for the objective that its evaluation, gradient, and Hessian are inaccessible, while one can compute their stochastic estimates by, for example, subsampling. We propose a stochastic algorithm based on sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. To motivate our algorithm design, we first revisit ...