A Study of Piecewise Linear-Quadratic Programs

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

Research output: Contribution to journalArticle

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

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