Quasiconvex relaxations based on interval arithmetic (Q5929744)

Let \(S\) be a convex subset of \(\mathbb{R}^n\). Then \(f: S\to\mathbb{R}\) is called quasiconvex if \(f(\lambda x+(1- \lambda)y)\leq \max\{f(x), f(y)\}\) for all \(x,y\in S\) and \(0\leq\lambda\leq 1\). The function \(f\) is called quasiconcave if \(-f\) is quasiconvex; it is called quasilinear if it is both quasiconvex and quasiconcave. If \(S\) is open and \(f: S\to\mathbb{R}\) is differentiable, and if, in addition, \(f'(x)^T(x- y)\geq 0\) always implies \(f(y)\geq f(x)\) then \(f\) is called pseudoconvex. A quasiconvex relaxation of a global minimization problem \(P\) is a minimization problem \(\widetilde P\) such that (i) each feasible solution of \(P\) is feasible for \(\widetilde P\); (ii) the objective function of \(P\) is greater than or equal to the objective function of \(\widetilde P\) for all feasible points of \(P\); (iii) the objective function of \(\widetilde P\) is pseudoconvex, and the constraints of \(\widetilde P\) are defined by quasilinear or quasiconvex functions. It is known that the objective value of a Kuhn-Tucker point of a quasiconvex relaxation \(\widetilde P\) is equal to the global minimum value of \(\widetilde P\) and therefore a lower bound of the global minimum value of \(P\). The author shows how quasiconvex lower bound and quasiconcave upper bound functions can be calculated for a given function by using the tools of interval arithmetic. With these bound functions he describes the construction of quasiconvex relaxations for global constrained optimization problems and nonlinear systems, where the objective and the constraints are defined by arithmetical expressions. Moreover, he presents a branch-and-bound algorithm which uses quasiconvex relaxations and which solves global constrained optimization problems in a rigorous way. Hints on its implementation and numerical examples conclude the paper.