Abstract
Convex piecewise quadratic functions (CPQF) play an important role in mathematical programming, and yet their structure has not been fully studied. In this paper, these functions are categorized into difference-definite and difference-indefinite types. We show that, for either type, the expressions of a CPQF on neighboring polyhedra in its domain can differ only by a quadratic function related to the common boundary of the polyhedra. Specifically, we prove that the monitoring function in extended linear-quadratic programming is difference-definite. We then study the case where the domain of the difference-definite CPQF is a union of boxes, which arises in many applications. We prove that any such function must be a sum of a convex quadratic function and a separable CPQF. Hence, their minimization problems can be reformulated as monotropic piecewise quadratic programs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Rockafellar, R. T.,Large-Scale Extended Linear-Quadratic Programming and Multistage Optimization, Advances in Numerical Partial Differential Equations and Optimization, SIAM Publications, Edited by S. Gomez, J.-P. Hennart, and R. Tapia, pp. 247–261, 1991.
Rockafellar, R. T.,Linear-Quadratic Programming and Optimal Control, SIAM Journal on Control and Optimization, Vol. 25, pp. 781–814, 1987.
Rockafellar, R. T., andWets, R. J. B.,Generalized Linear-Quadratic Problems of Deterministic and Stochastic Optimal Control in Discrete Time, SIAM Journal on Control and Optimization, Vol. 28, pp. 810–822, 1990.
Louveaux, F.,A Solution Method for Multistage Stochastic Programs with Recourse with Applications to an Energy Investment Problem, Operations Research, Vol. 28, pp. 889–902, 1980.
Perold, A. F.,Large-Scale Portfolio Optimization, Harvard University, Graduate School of Business Administration, Report HBS 82-24, 1981.
Sun, J.,A Study on Monotropic Piecewise Quadratic Programming, the Australian Society for Operations Research Special Publication on Mathematical Programming, Edited by S. Kumar, Gordon and Breach, Melbourne, Australia, to appear.
Sun, J.,Tracing the Characteristic Curve of a Quadratic Black Box, Networks, Vol. 19, pp. 637–650, 1989.
Wilde, D. J., andAcrivos, A.,Minimization of a Piecewise Quadratic Function Arising in Production Scheduling, Operations Research, Vol. 8, pp. 652–674, 1960.
Sun, J.,On Monotropic Piecewise Quadratic Programming, University of Washington, PhD Thesis, 1986.
Robinson, S. M.,Some Continuity Properties of Polyhedral Multifunctions, Mathematical Programming Study, Vol. 14, pp. 206–214, 1981.
Rockafellar, R. T., andSun, J.,A Simplex-Active-Set Algorithm for Monotropic Piecewise Quadratic Programming, Technical Report 86-10, Department of Industrial Engineering and Management Sciences, Northwestern University, 1986.
Han, S. P.,A Decomposition Method and Its Application to Convex Programming, Mathematics of Operations Research, Vol. 14, pp. 237–248, 1989.
Author information
Authors and Affiliations
Additional information
Communicated by F. Zirilli
This research was supported by Grant DDM-87-21709 of the National Science Foundation.
Rights and permissions
About this article
Cite this article
Sun, J. On the structure of convex piecewise quadratic functions. J Optim Theory Appl 72, 499–510 (1992). https://doi.org/10.1007/BF00939839
Issue Date:
DOI: https://doi.org/10.1007/BF00939839