frank-wolfe

The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    This paper considers a general class of iterative optimization algorithms, referred to as linear-optimization-based convex programming (LCP) methods, for solving large-scale convex programming (CP) problems. The LCP methods, covering the classic conditional gradient (CG) method (a.k.a., Frank-Wolfe method) as a special case, can only solve a linear optimization subproblem at each iteration. In this paper, … Read more

    New concave penalty functions for improving the Feasibility Pump

  • Marianna De Santis
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories (Mixed) Integer Linear Programming, Nonlinear Optimization Tags , , ,

    Mixed-Integer optimization represents a powerful tool for modeling many optimization problems arising from real-world applications. The Feasibility pump is a heuristic for finding feasible solutions to mixed integer linear problems. In this work, we propose a new feasibility pump approach using concave non-differentiable penalty functions for measuring solution integrality. We present computational results on binary … Read more

    A concave optimization-based approach for sparse portfolio selection

  • David Di Lorenzo
  • Giampaolo Liuzzi
  • Francesco Rinaldi
  • Fabio Schoen
  • Marco Sciandrone
    • Categories Constrained Nonlinear Optimization, Finance and Economics, Stochastic Approaches Tags , , ,

    This paper considers a portfolio selection problem in which portfolios with minimum number of active assets are sought. This problem is motivated by the need of inducing sparsity on the selected portfolio to reduce transaction costs, complexity of portfolio management, and instability of the solution. The resulting problem is a difficult combinatorial problem. We propose … Read more

    A Modified Frank-Wolfe Algorithm for Computing Minimum-Area Enclosing Ellipsoidal Cylinders: Theory and Algorithms

  • Selin Damla Ahipasaoglu
  • Michael J. Todd
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    We study a first-order method to find the minimum cross-sectional area ellipsoidal cylinder containing a finite set of points. This problem arises in optimal design in statistics when one is interested in a subset of the parameters. We provide convex formulations of this problem and its dual, and analyze a method based on the Frank-Wolfe … Read more

    A Linearly Convergent Linear-Time First-Order Algorithm for Support Vector Classification with a Core Set Result

  • Piyush Kumar
  • E. Alper Yildirim
    • Categories Convex Optimization Tags , , , , ,

    We present a simple, first-order approximation algorithm for the support vector classification problem. Given a pair of linearly separable data sets and $\epsilon \in (0,1)$, the proposed algorithm computes a separating hyperplane whose margin is within a factor of $(1-\epsilon)$ of that of the maximum-margin separating hyperplane. We discuss how our algorithm can be extended … Read more

    Simultaneously solving seven optimization problems in relative scale

  • Peter Richtarik
    • Categories Linear Programming, Nonsmooth Optimization, Statistics Tags , , , , , , , , , , , , , ,

    In this paper we develop and analyze an efficient algorithm which solves seven related optimization problems simultaneously, in relative scale. Each iteration of our method is very cheap, with main work spent on matrix-vector multiplication. We prove that if a certain sequence generated by the algorithm remains bounded, then the method must terminate in $O(1/\delta)$ … Read more

    Concave programming for minimizing the zero-norm over polyhedral sets

  • Francesco Rinaldi
  • Fabio Schoen
  • Marco Sciandrone
    • Categories Constrained Nonlinear Optimization, Data-Mining Tags , ,

    Given a non empty polyhedral set, we consider the problem of finding a vector belonging to it and having the minimum number of nonzero components, i.e., a feasible vector with minimum zero-norm. This nonsmooth combinatorial optimization problem is NP-Hard and arises in various fields such as machine learning, pattern recognition, signal processing. We propose two … Read more

    Linear convergence of a modified Frank-Wolfe algorithm for computing minimum volume ellipsoids

  • Selin Damla Ahipasaoglu
  • Peng Sun
  • Michael J. Todd
    • Categories Convex Optimization Tags , , ,

    We show the linear convergence of a simple first-order algorithm for the minimum-volume enclosing ellipsoid problem and its dual, the D-optimal design problem of statistics. Computational tests confirm the attractive features of this method. Citation Optimization Methods and Software 23 (2008), 5–19. Article Download View Linear convergence of a modified Frank-Wolfe algorithm for computing minimum … Read more

    Set Intersection Theorems and Existence of Optimal Solutions

  • Dimitri Bertsekas
  • Paul Tseng
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , ,

    The question of nonemptiness of the intersection of a nested sequence of closed sets is fundamental in a number of important optimization topics, including the existence of optimal solutions, the validity of the minimax inequality in zero sum games, and the absence of a duality gap in constrained optimization. We introduce the new notion of … Read more