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

    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

    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

    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. CitationTechnical Report … 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

    Second-order necessary conditions in Pontryagin form for optimal control problems

  • Joseph Frédéric Bonnans
  • Xavier Dupuis
  • Laurent Pfeiffer
    • Categories Constrained Nonlinear Optimization, Systems governed by Differential Equations Optimization

    In this report, we state and prove first- and second-order necessary conditions in Pontryagin form for optimal control problems with pure state and mixed control-state constraints. We say that a Lagrange multiplier of an optimal control problem is a Pontryagin multiplier if it is such that Pontryagin’s minimum principle holds, and we call optimality conditions … Read more

    Second-order sufficient conditions for strong solutions to optimal control problems

  • Joseph Frédéric Bonnans
  • Xavier Dupuis
  • Laurent Pfeiffer
    • Categories Constrained Nonlinear Optimization, Systems governed by Differential Equations Optimization

    In this report, given a reference feasible trajectory of an optimal control problem, we say that the quadratic growth property for bounded strong solutions holds if the cost function of the problem has a quadratic growth over the set of feasible trajectories with a bounded control and with a state variable sufficiently close to the … Read more

    Level Bundle Methods for Constrained Convex Optimization with Various Oracles

  • Welington de Oliveira
  • Wim van Ackooij
    • Categories Nonsmooth Optimization

    We propose restricted memory level bundle methods for minimizing constrained convex nonsmooth optimization problems whose objective and constraint functions are known through oracles (black-boxes) that might provide inexact information. Our approach is general and covers many instances of inexact oracles, such as upper, lower and on-demand oracles. We show that the proposed level bundle methods … Read more