-
作者：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...
-
作者：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...
-
作者：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...
-
作者：Cartis, Coralia; Roberts, Lindon
作者单位：University of Oxford; Australian National University
摘要：We introduce a general framework for large-scale model-based derivative-free optimization based on iterative minimization within random subspaces. We present a probabilistic worst-case complexity analysis for our method, where in particular we prove high-probability bounds on the number of iterations before a given optimality is achieved. This framework is specialized to nonlinear least-squares problems, with a model-based framework based on the Gauss-Newton method. This method achieves scalab...
-
作者：Josz, Cedric; Lai, Lexiao
作者单位：Columbia University
