Text

First-Order Methods for Problems with O (1) Functional Constraints Can Have Almost the Same Convergence Rate as for Unconstrained Problems

First-order methods (FOMs) have recently been applied and analyzed for solving problems with complicated functional constraints. Existing works show that FOMs for functional constrained problems have lower-order convergence rates than those for unconstrained problems. In particular, an FOM for a smooth strongly convex problem can have linear convergence, while it can only converge sublinearly for a constrained problem if the projection onto the constraint set is prohibited. In this paper, we point out that the slower convergence is caused by the large number of functional constraints but not the constraints themselves. When there are only m=O(1) functional constraints, we show that an FOM can have almost the same convergence rate as that for solving an unconstrained problem, even without the projection onto the feasible set. In addition, given an ε>0, we show that a complexity result that is better than a lower bound can be obtained if there are only m=o(ε−12) functional constraints. Our result is surprising but does not contradict the existing lower complexity bound because we focus on a specific subclass of problems. Experimental results on quadratically constrained quadratic programs demonstrate our theory.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.32 No.3 July-September 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1759-1790

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

FIRST-ORDER METHOD
ITERATION COMPLEXITY
CUTTING-PLANE METHOD
NONLINEARLY CONSTRAINED PROBLEM

Info Detail Spesifik

https://doi.org/10.1137/20M1371579

Pernyataan Tanggungjawab

Yangyang Xu

Versi lain/terkait

Lampiran Berkas

Komentar