-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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.
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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 ...
-
作者：Lodi, Andrea; Tanneau, Mathieu; Vielma, Juan-Pablo
作者单位：Universite de Montreal; Polytechnique Montreal; Massachusetts Institute of Technology (MIT)
摘要：This paper studies disjunctive cutting planes in Mixed-Integer Conic Programming. Building on conic duality, we formulate a cut-generating conic program for separating disjunctive cuts, and investigate the impact of the normalization condition on its resolution. In particular, we show that a careful selection of normalization guarantees its solvability and conic strong duality. Then, we highlight the shortcomings of separating conic-infeasible points in an outer-approximation context, and prop...
