A new approach to optimization under monotonic constraint (Q5927651)

The paper is concerned with the following problem: find \(\max \{{\mathbf c}{\mathbf x}\mid {\mathbf x}\in D,\varphi ({\mathbf g}({\mathbf x}))\leq 1\}\), where \(D\) is a compact convex set in \(\mathbb{R}^n\), \({\mathbf g}=(g_1, \dots,g_m\}\), \(g_i:D \to\mathbb{R}_+\) for \(i=1,\dots,m\) is a continuous positive-valued function and \(\varphi: \mathbb{R}^m_+ \to\mathbb{R}\) is a lower semi-continuous function such that \(\forall {\mathbf y},{\mathbf y}'\in \mathbb{R}_+^m\) \(({\mathbf y}\geq {\mathbf y}'\Leftarrow \varphi({\mathbf y})\geq \varphi({\mathbf y}'))\). The authors first convert the problem into a form exhibiting monotonicity both in the constraints and in the objective function. In the subsequent section some basic properties of the objective function and the constraints are discussed for devising efficient solution strategies. Based on these properties a branch-and bound algorithm for the problem is described as the main result of the paper. Each iteration of the algorithm involves solving an univariate equation \(\varphi (\propto {\mathbf y}^{k+1})=1\) and \(m\) convex programs. Finally, results of computational experiments with the algorithm coded in Pascal language on a PC with Pentium II are presented. Problems with at most \(n=20\), \(m=10\) required at most 2006 iterations and 1307 seconds. Overall, this interesting paper is written in a precise manner presupposing a good familiarity with foundations of analysis and branch-and-bound method. The presented algorithm is usable -- in my opinion -- preferably for small sized problems.