Maximization of a Convex Quadratic Function Under Linear Constraints

Konno, H. (1974). Maximization of a Convex Quadratic Function Under Linear Constraints. IIASA Working Paper. IIASA, Laxenburg, Austria: WP-74-076

Preview

Text WP-74-076.pdf Download (371kB) | Preview

Abstract

Since the appearance of a paper by H. Tui, maximization of convex function over a polytope has attracted much attention. In his paper, two algorithms were proposed: one cutting plane and the other enumerative. However, the numerical experiments reported on the naive cutting plane approach were discouraging enough to shift the researchers more to the direction of enumerative approaches.

In this paper, we will develop a cutting plane algorithm for maximizing a convex quadratic function subject to linear constraints. The basic idea is much the same as Tui's method. It also parallels some of the recent results by E. Balas and C-A. Burdet. We will, however, use standard tools which are easier to understand and will fully exploit the special structure of the problem. The main purpose of the paper is to demonstrate that the full exploitation of special structure will enable us to generate a cut which is much deeper than Tui's cut and that the cutting plane algorithm can be used to solve a rather big problem efficiently.

Actions (login required)

View Item