Optimization Online


User manual of NewtBracket: “A Newton-Bracketing method for a simple conic optimization problem” with applications to QOPs in binary variables

Sunyoung Kim(skim***at***ewha.ac.kr)
Masakazu Kojima(kojima***at***is.titech.ac.jp)
Kim-Chuan Toh(mattohkc***at***nus.edu.sg)

Abstract: We describe the Matlab package NewtBracket for solving a simple conic optimization problem that minimizes a linear objective function subject to a single linear equality constraint and a convex cone constraint. The problem is converted into the problem of finding the largest zero $y^*$ of a continuously differentiable (except at $y^*$) convex function $g : \Real \rightarrow \Real$ such that $g(y) = 0$ if $y \leq y^*$ and $g(y) > 0$ otherwise. The Newton-Bracketing method [10] generates a sequence of lower and upper bounds of $y^*$ both converging to $y^*$. For applications, we present the Lagrangian doubly nonnegative relaxation of binary quadratic optimization problems, quadratic multiple knapsack problems, quadratic assignment problems and maximum stable set problems. The MATLAB package NewtBracket can be obtained at https://sites.google.com/site/masakazukojima1/softwares-developed/newtbracket.

Keywords: Nonconvex optimization problems, conic relaxations, robust numerical algorithms, Newton-bracketing method, secant-bracketing method for generating valid bounds.

Category 1: Linear, Cone and Semidefinite Programming (Other )


Download: [PDF]

Entry Submitted: 11/28/2020
Entry Accepted: 12/01/2020
Entry Last Modified: 11/28/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society