Optimization Software and Modeling Systems

Strange Behaviors of Interior-point Methods for Solving Semidefinite Programming Problems in Polynomial Optimization

  • Masakazu Muramatsu
  • Hayato Waki
  • Maho Nakata
    • Categories Optimization Software and Modeling Systems, Semi-definite Programming Tags , ,

    We observe that in a simple one-dimensional polynomial optimization problem (POP), the `optimal’ values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial … Read more

    A Comparison of Software Packages for Verified Linear Programming

  • Christian Keil
    • Categories Linear Programming, Optimization Software and Modeling Systems Tags , , , ,

    Linear programming is arguably one of the most basic forms of optimization. Its theory and algorithms can not only be applied to linear optimization problems but also to relaxations of nonlinear problems and branch-and-bound methods for mixed-integer and global optimization problems. Recent research shows that against intuition bad condition numbers frequently occur in linear programming. … Read more

    Parallel Space Decomposition of the Mesh Adaptive Direct Search algorithm

  • Charles Audet
  • John E. Dennis, Jr.
  • Sébastien Le Digabel
    • Categories Applications - OR and Management Sciences, Nonsmooth Optimization, Parallel Algorithms Tags , , , ,

    This paper describes a parallel space decomposition PSD technique for the mesh adaptive direct search MADS algorithm. MADS extends a generalized pattern search for constrained nonsmooth optimization problems. The objective of the present work is to obtain good solutions to larger problems than the ones typically solved by MADS. The new method PSD-MADS is an … Read more

    Benchmarking Derivative-Free Optimization Algorithms

  • Jorge Moré
  • Stefan M. Wild
    • Categories Optimization Software Benchmark, Unconstrained Optimization Tags , , , ,

    We propose data profiles as a tool for analyzing the performance of derivative-free optimization solvers when there are constraints on the computational budget. We use performance and data profiles, together with a convergence test that measures the decrease in function value, to analyze the performance of three solvers on sets of smooth, noisy, and piecewise-smooth … Read more

    LIBOPT – An environment for testing solvers on heterogeneous collections of problems – The manual, version 2.0

  • Jean Charles Gilbert
  • Xavier Jonsson
    • Categories Modeling Languages and Systems, Optimization Software Benchmark Tags

    The Libopt environment is both a methodology and a set of tools that can be used for testing, comparing, and profiling solvers on problems belonging to various collections. These collections can be heterogeneous in the sense that their problems can have common features that differ from one collection to the other. Libopt brings a unified … Read more

    LANCELOt_simple, a simple interface to LANCELOT B

  • Nicholas I. M. Gould
  • Dominique Orban
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization Software and Modeling Systems Tags , ,

    We describe LANCELOT_simple, an interface to the LANCELOT B nonlinear optimization package within the GALAHAD} library (Gould, Orban, Toint, 2003) which ignores problem structure. The result is an easy-to-use Fortran 90 subroutine, with a small number of intuitively interpretable arguments. However, since structure is ignored, the means of presenting problems to the solver limited and … Read more

    Two theoretical results for sequential semidefinite programming

  • Rodrigo Garcés
  • Walter Gómez
  • Florian Jarre
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    We examine the local convergence of a sequential semidefinite programming approach for solving nonlinear programs with nonlinear semidefiniteness constraints. Known convergence results are extended to slightly weaker second order sufficient conditions and the resulting subproblems are shown to have local convexity properties that imply a weak form of self-concordance of the barrier subproblems. Citation Preprint, … Read more

    Automated Tuning of Optimization Software Parameters

  • Mustafa Baz
  • J. Paul Brooks
  • Brady Hunsaker
  • Abhijit Gosavi
    • Categories Optimization Software and Modeling Systems Tags , , ,

    We present a method to tune software parameters using ideas from software testing and machine learning. The method is based on the key observation that for many classes of instances, the software shows improved performance if a few critical parameters have “good” values, although which parameters are critical depends on the class of instances. Our … Read more

    Graph Implementations for Nonsmooth Convex Programs

  • Stephen Boyd
  • Michael Grant
    • Categories Convex Optimization, Modeling Languages and Systems, Nonsmooth Optimization Tags , ,

    We describe graph implementations, a generic method for representing a convex function via its epigraph, described in a disciplined convex programming framework. This simple and natural idea allows a very wide variety of smooth and nonsmooth convex programs to be easily specified and efficiently solved, using interior-point methods for smooth or cone convex programs. Citation … Read more

    Computational Experience with a Software Framework for Parallel Integer Programming

  • Lazslo Ladanyi
  • Ted K. Ralphs
  • Matthew Saltzman
  • Yan Xu
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles, Parallel Algorithms

    In this paper, we discuss the challenges that arise in parallelizing algorithms for solving mixed integer linear programs and introduce a software framework that aims to address these challenges. The framework was designed specifically with support for implementation of relaxation-based branch-and-bound algorithms in mind. Achieving efficiency for such algorithms is particularly challenging and involves a … Read more