Browse Prior Art Database

Global Concave Minimization

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

Publishing Venue

Software Patent Institute

Related People

X.S. Zhang: AUTHOR [+3]

Abstract

The problem to be considered in this paper is called the Concave Minimization Problem (CMP). It has the form of [Equation ommitted] where [Equation ommitted] are differentiable and concave. Problems of this form were studied earlier by Rosen 0161 in the context of control theory. Avriel and Willisms Ell encountered the same problem in an engineering design setting. In their paper the theory of geometric programming is extended to solve a practical problem, which has product terms with negative coefficients. The same problem also arose in the context of applying Bender's decomposition procedure .to certain type of nonc;oncave optimization problems in networks. Bansal and Jacobsen L2,31, Hill.estad 191 showed that such problems arise when there are budget constraints which reflect economies-of-scale. As pointed out in C21.,, if an efficient procedure can be found for solving the CMP, then a difficult class of network optimization problem may be solved via Bender's decomposition procedure. In Meyer's paper C13I, which discussed the convergence property of a class of nonlinear programming algorithms including Rosen's method C16I, the term "Reverse Convex" was used. Hence the term Reverse Convex Problem (RCP) is used by some authors to describe the problem: (1.2) [Equation ommitted] where f is also concave, but gi are convex-type functions. CMP (RCP) usually has many local minimum solutions. The above mentioned papers - 2

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

Page 1 of 24

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Global Concave Minimization

by

X.S. Zhang J.B. Rosen

Technical Report 83-4 February 1983 ABSTRACT The problem of finding the global minimum of a concave function subject to differentiable concave constraints is investigated in this paper. The first stage of the algorithm consists of solving a sequence of linear programs which explore the nonconvex feasible domain to obtain a point near the global minimum point. In the second stage a sequence of simultaneous nonlinear equations is solved with the starting point obtained by the first stage. The sequence of points obtained will converge superlinearly to the desired solution with appropriate assumptions. This research was supported in part by the Computer Science Section of the National Science Foundation under Research Grant MCS 8101211

I . INTRODUCTION.

The problem to be considered in this paper is called the Concave Minimization Problem (CMP). It has the form of

(Equation Omitted)

where

(Equation Omitted)

are differentiable and concave. Problems of this form were studied earlier by Rosen 0161 in the context of control theory. Avriel and Willisms Ell encountered the same problem in an engineering design setting. In their paper the theory of geometric programming is extended to solve a practical problem, which has product terms with negative coefficients. The same problem also arose in the context of applying Bender's decomposition procedure .to certain type of nonc;oncave optimization problems in networks. Bansal and Jacobsen L2,31, Hill.estad 191 showed that such problems arise when there are budget constraints which reflect economies-of- scale. As pointed out in C21.,, if an efficient procedure can be found for solving the CMP, then a difficult class of network optimization problem may be solved via Bender's decomposition procedure. In Meyer's paper C13I, which discussed the convergence property of a class of nonlinear programming algorithms including Rosen's method C16I, the term "Reverse Convex" was used. Hence the term Reverse Convex Problem (RCP) is used by some authors to describe the problem: (1.2)

(Equation Omitted)

where f is also concave, but gi are convex-type functions. CMP (RCP) usually has many local minimum solutions. The above mentioned papers

- ,2,3,9,167 developed algorithms which locate only one stationary point of the Lagrangian or a Kuhn-Tucker point. We will pay attention here to an algorithm which searches for the global solution. A special case of the CMP is that the constraints are linear functions, which have

University of Minnesota Page 1 Dec 31, 1983

Page 2 of 24

Global Concave Minimization

attracted the attention of many in recent years. Tuy 119,181 first studied this problem in 196,, which he called Concave Programming with the form:_

(Equation Omitted)

where f is a quasi-concave function and D is a convex polyhedral set in Rn. Problem (1.3) has many important practical applications in Op...