Text

A Generalized Method for Binary Optimization : Convergence Analysis and Applications

Binary optimization problems (BOPs) arise naturally in many fields, such as information retrieval, computer vision, and machine learning. Most existing binary optimization methods either use continuous relaxation which can cause large quantization errors, or incorporate a highly specific algorithm that can only be used for particular loss functions. To overcome these difficulties, we propose a novel generalized optimization method, named Alternating Binary Matrix Optimization (ABMO), for solving BOPs. ABMO can handle BOPs with/without orthogonality or linear constraints for a large class of loss functions. ABMO involves rewriting the binary, orthogonality and linear constraints for BOPs as an intersection of two closed sets, then iteratively dividing the original problems into several small optimization problems that can be solved as closed forms. To provide a strict theoretical convergence analysis, we add a sufficiently small perturbation and translate the original problem to an approximated problem whose feasible set is continuous. We not only provide rigorous mathematical proof for the convergence to a stationary and feasible point, but also derive the convergence rate of the proposed algorithm. The promising results obtained from four binary optimization tasks validate the superiority and the generality of ABMO compared with the state-of-the-art methods.

Ketersediaan

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE; Vol.44 No.9 Part 1 September 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 4524-4543

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

HASHING
GRAPH BISECTION
BINARY OPTIMIZATION
DENSE SUBGRAPH DISCOVERY
CONSTRAINED IMAGE SEGMENTATION

Info Detail Spesifik

10.1109/TPAMI.2021.3070753

Pernyataan Tanggungjawab

Huan Xiong, Mengyang Yu, Li Liu, Fan Zhu, Jie Qin, Fumin Shen, Ling Shao

Versi lain/terkait

Lampiran Berkas

Komentar