No label defined (Q3703598)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3930734
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3930734 |
Statements
1985
0 references
reverse convex constraint
0 references
concave programming
0 references
0.8840327262878418
0 references
0.8814907670021057
0 references
0.8782974481582642
0 references
[For the entire collection see Zbl 0572.00008.] This paper presents an algorithm for solving the following problem (P): Minimize cx, s.t. (1) \(x\in D\), (2) g(x)\(\leq 0\), where \(D\subset R^ n\) is a polytope and g is a finite concave function on \(R^ n\). Problems of this kind occur in certain economic and engineering applications. All the difficulties of the problem arise from the presence of the constraint (2) which is called a reverse convex constraint, meaning that it is the reverse of a convex constraint. \textit{R. J. Hillestad} and \textit{S. E. Jacobsen} [Appl. Math. Optimization 6, 63-78 (1980; Zbl 0448.90044); ibid. 6, 257-269 (1980; Zbl 0435.90065)] have shown that cuts originally devised for concave programming could be as well used for reverse convex programming. Thus, the problem (P) and, more generally, the reverse convex programming problem, is closely related to the concave minimization problem. The purpose of the present paper is to develop a finite procedure for solving (P) which exploits this relationship in a more systematic way than has been done in the previously cited references. It turns out that a linear program with an additional reverse convex constraint can be decomposed into an alternatig sequence of linear programs (minimizing cx under constraints (1)) and concave programs (minimizing g(x) under constraints (1) and one additional constraint of the form cx\(\leq \alpha)\). Roughly speaking, the proposed algorithm switches between steps of two types: in the open region \(g(x)<0\), we use simplex pivots to improve the current feasible solutions, while at a feasible point on the boundary \(g(x)=0\), we must solve a concave program in order to decide whether or not the current feasible solution is optimal and if not to move to a better feasible solution in the region \(g(x)<0\). To solve these concave programs we can use any available finite algorithm, for instance the algorithm of \textit{Tran Vu Thieu, Bui The Tam} and \textit{Vu Thien Ban} [Acta Math. Vietnam. 8, No.1, 21-40 (1980; Zbl 0562.90069)] or that of \textit{J. E. Falk} and \textit{K. R. Hoffmann} [Math. Oper. Res. 1, 251-259 (1976; Zbl 0362.90082)].
0 references