Milan Hladík. Interval convex quadratic programming problems in a general form. Cent. Eur. J. Oper. Res., 25(3):725–737, 2017.
[PDF] [gzipped postscript] [postscript] [HTML]
This paper addresses the problem of computing the minimal and the maximal optimal value of a convex quadratic programming (CQP) problem when the coefficients are subject to perturbations in given intervals. Contrary to the previous results concerning on some special forms of CQP only, we present a unified method to deal with interval CQP problems. The problem can be formulated by using equation, inequalities or both, and by using sign-restricted variables or sign-unrestricted variables or both. We propose simple formulas for calculating the minimal and maximal optimal values. Due to NP-hardness of the problem, the formulas are exponential with respect to some characteristics. On the other hand, there are large sub-classes of problems that are polynomially solvable. For the general intractable case we propose an approximation algorithm. We illustrate our approach by a geometric problem of determining the distance of uncertain polytopes. Eventually, we extend our results to quadratically constrained CQP, and state some open problems.
The equation in Theorem 2 is correct, but the proof must be conducted another way. In Theorem 4, a constraint qualification is missing, and the proof also needs more thorough derivation.
@article{Hla2017c,
author = "Milan Hlad\'{\i}k",
title = "Interval convex quadratic programming problems in a general form",
journal = "Cent. Eur. J. Oper. Res.",
fjournal = "Central European Journal of Operations Research",
volume = "25",
number = "3",
pages = "725-737",
year = "2017",
doi = "10.1007/s10100-016-0445-8",
issn = "1613-9178",
bib2html_dl_html = "https://doi.org/10.1007/s10100-016-0445-8",
bib2html_dl_pdf = "http://rdcu.be/nhN2",
abstract = "This paper addresses the problem of computing the minimal and the maximal optimal value of a convex quadratic programming (CQP) problem when the coefficients are subject to perturbations in given intervals. Contrary to the previous results concerning on some special forms of CQP only, we present a unified method to deal with interval CQP problems. The problem can be formulated by using equation, inequalities or both, and by using sign-restricted variables or sign-unrestricted variables or both. We propose simple formulas for calculating the minimal and maximal optimal values. Due to NP-hardness of the problem, the formulas are exponential with respect to some characteristics. On the other hand, there are large sub-classes of problems that are polynomially solvable. For the general intractable case we propose an approximation algorithm. We illustrate our approach by a geometric problem of determining the distance of uncertain polytopes. Eventually, we extend our results to quadratically constrained CQP, and state some open problems.",
bib2html_errata = "The equation in Theorem 2 is correct, but the proof must be conducted another way. In Theorem 4, a constraint qualification is missing, and the proof also needs more thorough derivation.",
keywords = "Convex quadratic programming; Interval analysis; Uncertainty modeling",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44