Browse Prior Art Database

Construction of Large-Scale Global Minimum Concave Quadratic Test Problems

IP.com Disclosure Number: IPCOM000128573D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 11 page(s) / 30K

Publishing Venue

Software Patent Institute

Related People

B. Kalantari: AUTHOR [+4]

Abstract

Construction of problems, with known global solutions is important for the compu tational testing of constrained global minimization algorithms. In this paper it is shown how to construct a concave quadratic function which attains its global minimum at a specified vertex of a polytope in RI+k. The constructed function is strictly concave in the variables xER" and is linear in the variables yERk. The number of linear variables k, may be much larger than n, so that large-scale global minimization test problems can be constructed by the methods described here.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Construction of Large-Scale Global Minimum Concave Quadratic Test Problems

B. Kalantari J.B. Rosen

Computer Science

Institute of Technology

136 Lind Hall

University of Minnesota

Minneapolis, Minnesota 55455

Technical Report 83-5

.. R w. ; ~u~.y 7. Construction of Large-Scale Global Minimum Concave Quadratic Test Problems*

Bahman ICalantari and J. B. Rosen Computer Science Department University of Minnesota

Abstract s

Construction of problems, with known global solutions is important for the compu tational testing of constrained global minimization algorithms. In this paper it is shown how to construct a concave quadratic function which attains its global minimum at a specified vertex of a polytope in RI+k. The constructed function is strictly concave in the variables xER" and is linear in the variables yERk. The number of linear variables k, may be much larger than n, so that large- scale global minimization test problems can be constructed by the methods described here.

Key Words. Global optimization, test problems, concave minimization. This research was supported by the Computer Science Section of tile National Science Foundation under research grant HTCS 8I-012I4.

1. Introduction

Algorithms for finding the global minimum of a concave function aver a polytope have been the subject of continuing investigation since at least 1964 (Ref.1). More recently there has been increased activity in the computational implementation of such algorithms (Refs. 2-5). In order to test such implementations it is important to be able to generate a variety of test problems with known solutions. Methods are frequently used for such constrained test problem generation which construct problems with a known local minimum (Ref. 6). Such a local minimum will of course be a global minimum if the function is convex, but for nonconvex functions (in particular for concave functions) it will generally not be a global minimum. Thus it is necessary to develop new methods for constructing test problems for global minimization algorithms. Several methods have recently been proposed (Refs. 4,7) for the construction of concave quadratic test

University of Minnesota Page 1 Dec 31, 1983

Page 2 of 11

Construction of Large-Scale Global Minimum Concave Quadratic Test Problems

problems, with a known global minimum over a bounded convex polyhedron (polytope) in R -,. These methods require the solution of either a convex programming problem (Ref. 4) or n linear programs (Ref. 7).- Recently larger concave problems which r hay have many linear variables have been considered, and an algorithm for finding the global minimum over a polytope has been proposed (Ref. 5). This larger problem consists of finding the global minimum of the objective function

(Equation Omitted)

in a polytope PcRn+k, where R is an nxrr, symmetric positive definite matrix, and k may be much larger than n ((x,y) denotes the (n+k) column vect...