Text

Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables

This paper begins with the review of a class of strictly convex quadratic programs (QPs) with bounded variables solvable by the parametric principal pivoting algorithm with
strongly polynomial complexity, where is the number of variables of the problem. Extensions of this Hessian class are the main contributions of this paper, which is motivated by a recent paper [P. Liu, S. Fattahi, A. Gómez, and S. Küçükyavuz, Math. Program. (2022), https://doi.org/10.1007/s10107-022-01845-0], wherein the efficient solution of a QP with a tridiagonal Hessian matrix in the quadratic objective is needed for the construction of a polynomial-time algorithm for solving an associated sparse variable selection problem. With the tridiagonal structure, the complexity of the QP algorithm reduces to . Our strongly polynomiality results extend previous works of some strongly polynomially solvable linear complementarity problems with a P-matrix [J. S. Pang and R. Chandrasekaran, Math. Program. Stud., 25 (1985), pp. 13–27]; special cases of the extended results include weakly quasi-diagonally dominant problems in addition to the tridiagonal ones.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.33 No.2 April-June 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 899-920

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

QUADRATIC PROGRAMS
DIAGONAL DOMINANCE
STRONG POLYNOMIALITY
Z-MATRIX

Info Detail Spesifik

https://doi.org/10.1137/21M1463793

Pernyataan Tanggungjawab

Jong-Shi Pang,

Versi lain/terkait

Lampiran Berkas

Komentar