Month: May 2013

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 and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Global Optimization Tags , , , , ,

    The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest … Read more

    Nonmonotone line search methods with variable sample size

  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Global Optimization Tags , , ,

    Nonmonotone line search methods for unconstrained minimization with the objective functions in the form of mathematical expectation are considered. The objective function is approximated by the sample average approximation (SAA) with a large sample of fixed size. The nonmonotone line search framework is embedded with a variable sample size strategy such that different sample size … Read more

    Efficient tridiagonal preconditioner for the matrix-free truncated Newton method

  • Ladislav Lukšan
  • Jan Vlček
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this report, we study an efficient tridiagonal preconditioner, based on numerical differentiation, applied to the matrix-free truncated Newton method for unconstrained optimization. It is proved that this preconditioner is positive definite for many practical problems. The efficiency of the resulting matrix-free truncated Newton method is demonstrated by results of extensive numerical experiments. Citation Technical … Read more

    Using diversification, communication and parallelism to solve mixed-integer linear programs

  • Shabbir Ahmed
  • Rodolfo Carvajal
  • Kevin C Furman
  • George L. Nemhauser
  • Vikas Goel
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems, Parallel Algorithms Tags , , , , ,

    Performance variability of modern mixed-integer programming solvers and possible ways of exploiting this phenomenon present an interesting opportunity in the development of algorithms to solve mixed-integer linear programs (MILPs). We propose a framework using multiple branch-and-bound trees to solve MILPs while allowing them to share information in a parallel execution. We present computational results on … Read more

    Handelman’s hierarchy for the maximum stable set problem

  • Monique Laurent
  • Zhao Sun
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming

    The maximum stable set problem is a well-known NP-hard problem in combinatorial optimization, which can be formulated as the maximization of a quadratic square-free polynomial over the (Boolean) hypercube. We investigate a hierarchy of linear programming relaxations for this problem, based on a result of Handelman showing that a positive polynomial over a polytope can … Read more

    Updating LU Factors of LP Simplex Bases

  • Sande Gordon
    • Categories Linear Programming Tags , , ,

    Methods for updating the LU factors of simplex basis matrices are reviewed. An alternative derivation of the Fletcher and Matthews method is given. This leads to generalizations of their method which avoids problems with both the Bartels and Golub method and the Fletcher and Matthews method. The improvements are to both numerical stability and data … Read more

    On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming

  • Bingsheng He
  • Xiao-Ming Yuan
  • Liusheng Hou
    • Categories Convex Optimization Tags , , , , , ,

    The augmented Lagrangian method (ALM) is a benchmark for solving the convex minimization problem with linear constraints. We consider the special case where the objective is in form of the sum of m functions without coupled variables. For solving this separable convex programming model, it is usually required to decompose the ALM subproblem at each … Read more

    An inexact and nonmonotone proximal method for smooth unconstrained minimization

  • Sandra Augusta Santos
  • R. C. M. Silva
    • Categories Unconstrained Optimization

    An implementable proximal point algorithm is established for the smooth nonconvex unconstrained minimization problem. At each iteration, the algorithm minimizes approximately a general quadratic by a truncated strategy with step length control. The main contributions are: (i) a framework for updating the proximal parameter; (ii) inexact criteria for approximately solving the subproblems; (iii) a nonmonotone … Read more

    Nonsmooth Optimization Using Uncontrolled Inexact Information

  • Welington de Oliveira
  • Jérôme Malick
  • Sofia Zaourar
    • Categories Nonsmooth Optimization Tags , , , ,

    We consider convex nonsmooth optimization problems whose objective function is known through a (fine) oracle together with some additional (cheap but poor) information – formalized as a second coarse oracle with uncontrolled inexactness. It is the case when the objective function is itself the output of an optimization solver, using a branch-and-bound procedure, or decomposing … Read more