Conditions for boundedness in concave programming under reverse convex and convex constraints (Q1006541)

Many algorithms proposed for solving global optimization problems require boundedness of feasible regions. In the present paper, the author addresses the problem of boundedness in the following two classes of problems: (1) maximize \(f_0(x)\) subject to \(f_i(x)\geq 0\), \(i= 1,\dots, m\); (2) maximize \(f_0(x)\) subject to \(f_i(x)\leq 0\), \(i= 1,\dots, m\). In these problems \(x\in\mathbb{R}^n\) and \(f_i(x)\) for \(i= 0,1,\dots, m\) are faithfully convex functions and/or quasi-convex polynomials with unbounded level sets. A function is called faithfully convex, if it is constant along some segment only if it is at the same time constant along the whole line containing this segment. Necessary and sufficient conditions for boundedness (unboundedness) are proved and polynomial algorithms for testing the boundedness are presented. The performance of the algorithms is demonstrated on several numerical examples.