A Study of Piecewise Linear-Quadratic Programs

Ying Cui, Tsung Hui Chang, Mingyi Hong, Jong Shi Pang

Research output: Contribution to journalArticlepeer-review

Abstract

Motivated by a growing list of nontraditional statistical estimation problems of the piecewise kind, this paper provides a survey of known results supplemented with new results for the class of piecewise linear-quadratic programs. These are linearly constrained optimization problems with piecewise linear-quadratic objective functions. We first summarize some local properties of a piecewise linear-quadratic function in terms of their first- and second-order directional derivatives. We next extend some well-known necessary and sufficient second-order conditions for local optimality of a quadratic program to a piecewise linear-quadratic program and provide a dozen such equivalent conditions for strong, strict, and isolated local optimality, showing in particular that a piecewise linear-quadratic program has the same characterizations for local minimality as a standard quadratic program. As a consequence of one such condition, we show that the number of strong, strict, or isolated local minima of a piecewise linear-quadratic program is finite; this result supplements a recent result about the finite number of directional stationary objective values. We also consider a special class of unconstrained composite programs involving a non-differentiable norm function, for which we show that the task of verifying the second-order stationary condition can be converted to the problem of checking the copositivity of certain Schur complement on the nonnegative orthant.

Original languageEnglish (US)
Pages (from-to)523-553
Number of pages31
JournalJournal of Optimization Theory and Applications
Volume186
Issue number2
DOIs
StatePublished - Aug 1 2020

Bibliographical note

Funding Information:
The work of Chang was supported in part by the NSFC, China, under Grant 61731018, and by the Open Research Fund from Shenzhen Research Institute of Big Data, under Grant No. 2019ORF01002. The work of Hong was based on research partially supported by the U.S. National Science Foundation Grant CMMI-1727757 and Army Research Office (Grant W911NF-19-1-0247). The work of Pang was based on research partially supported by the U.S. National Science Foundation grant IIS-1632971 and the Air Force Office of Sponsored Research under Grant FA9550-18-1-0382.

Funding Information:
The work of Chang was supported in part by the NSFC, China, under Grant 61731018, and by the Open Research Fund from Shenzhen Research Institute of Big Data, under Grant No. 2019ORF01002. The work of Hong was based on research partially supported by the U.S. National Science Foundation Grant CMMI-1727757 and Army Research Office (Grant W911NF-19-1-0247). The work of Pang was based on research partially supported by the U.S. National Science Foundation grant IIS-1632971 and the Air Force Office of Sponsored Research under Grant FA9550-18-1-0382.

Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords

  • Directional stationarity
  • Piecewise linear-quadratic programming
  • Second-order directional
  • Second-order local optimality theory
  • Semi- and sub-derivatives

Fingerprint Dive into the research topics of 'A Study of Piecewise Linear-Quadratic Programs'. Together they form a unique fingerprint.

Cite this