scientific article; zbMATH DE number 3930734
[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)].
- Convex programs with several additional reverse convex constraints
- Minimizing a quasi-concave function subject to a reverse convex constraint
- On the global minimization of a convex function under general nonconvex constraints
- Linear programs with an additional rank two reverse convex constraint
- Comments on a reverse convex programming algorithm
- A parallel algorithm for linear programs with an additional reverse convex constraint
- A finite algorithm for globally optimizing a class of rank-two reverse convex programs
- Decomposition algorithm for reverse convex programs
- Linear programs with an additional separable concave constraint
- Computational experience using an edge search algorithm for linear reverse convex programs
- On solving general reverse convex programming problems by a sequence of linear programs and line searches
- Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization
- scientific article; zbMATH DE number 4174658 (Why is no real title available?)
- A conical branch-and-bound algorithm for a class of reverse convex programs
- Multilevel (Hierarchical) Optimization: Complexity Issues, Optimality Conditions, Algorithms
- scientific article; zbMATH DE number 3943567 (Why is no real title available?)
- scientific article; zbMATH DE number 3961360 (Why is no real title available?)
- Optimization of linear-convex programs
- scientific article; zbMATH DE number 94024 (Why is no real title available?)
- scientific article; zbMATH DE number 1281678 (Why is no real title available?)
- scientific article; zbMATH DE number 1461854 (Why is no real title available?)
- Intersection Disjunctions for Reverse Convex Sets
- Methods for solving some classes of reverse convex programs
- scientific article; zbMATH DE number 2190134 (Why is no real title available?)
- A cutting plane algorithm for linear reverse convex programs
- Sign reversion approach to concave minimization problems
- Duality and optimality conditions for reverse convex programs via a convex decomposition
- A level set algorithm for a class of reverse convex programs
- Quasiconjugates of functions, duality relationship between quasiconvex minimization under a reverse convex constraint and quasiconvex maximization under a convex constraint, and applications
- A finite cutting plane method for solving linear programs with an additional reverse convex constraint
- On the use of cuts in reverse convex programs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3703598)