Formalization of algorithms for optimization with block structures

Li, Chenyi

doi:10.1007/s11425-025-2516-2

Formalization of algorithms for optimization with block structures

2026-01-01

0

PRE

AI

DOI：10.1007/s11425-025-2516-2

Original

Original request for help

Save

Abstract

En 中文

Block-structured problems are central to advances in numerical optimization and machine learning. In this paper, we provide the formalization of convergence analysis for two pivotal algorithms in such settings: the block coordinate descent (BCD) method and the alternating direction method of multipliers (ADMM). Utilizing the type-theory-based proof assistant Lean 4, we develop a rigorous framework to formally represent these algorithms. Essential concepts in nonsmooth and nonconvex optimization are formalized, notably subdifferentials, which extend the classical differentiability to handle nonsmooth scenarios, and the Kurdyka-Lojasiewicz (KL) property, which provides essential tools to analyze convergence in nonconvex settings. Such definitions and properties are crucial for the corresponding convergence analyses. We formalize the convergence proofs of these algorithms, demonstrating that our definitions and structures are coherent and robust. These formalizations lay a basis for analyzing the convergence of more general optimization algorithms. Our implementation is available at https://github.com/optsuite/optlib.

Keywords:

numerical optimization

Lean

the block coordinate descent (BCD) method

the alternating direction method of multipliers (ADMM)

Formalization of algorithms for optimization with block structures

Abstract

Journal

Organization