Konno, H. (1974) Maximization of a Convex Quadratic Function Under Linear Constraints. IIASA Working Paper. IIASA, Laxenburg, Austria, WP-74-076
Download (371kB) | Preview
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.
|Item Type:||Monograph (IIASA Working Paper)|
|Research Programs:||System and Decision Sciences - Core (SDS)|
|Depositing User:||IIASA Import|
|Date Deposited:||15 Jan 2016 01:40|
|Last Modified:||28 Oct 2016 08:35|
Actions (login required)