Algorithms to project convex sets with applications in nonconvex programming and for a calculus of convex sets

点击翻译按钮获取中文摘要

The mathematical problem to project a finite dimensional convex set onto a lower dimensional subspace, where the original convex set is given analytically, plays a key role in this project. The projected set is to be represented in two different ways: In the first approach, the set is approximated by a convex polyhedron. In the second method, it is represented, or if not possible, approximated by linear matrix inequalities.The convex projection problem is to be applied to certain classes of non-convex optimization problems, where we aim to find exact solutions. Among these problem classes there are bilevel problems being convex on the lower level, DC programming problems where a DC representation of the objective function is known, and optimization problems with quasi-concave objective function and convex constraints. In the running project this approach was considered for the polyhedral case. The polyhedral projection problem was shown to be equivalent to vector linear programming (VLP). As a consequence, polyhedral versions of the mentioned global optimization problems can be solved by the VLP solver ‘bensolve’. Corresponding results will be developed for the non-polyhedral convex case. This includes the treatment of scalar global optimization problems by solvers for convex vector optimization problems. Alternatively, we plan to apply modified variants of convex vector optimization algorithms directly to the convex projection problem. So-called localized versions of the algorithms solve a projection problem locally (i.e. in a region of interest of the projected set). Thus they lead to an improved performance when applied to the scalar global optimization problems. In the running project, polyhedral projection was used to implement a numerical calculus for polyhedral convex sets and polyhedral convex function in form of the free software ‘bensolve tools’. This tool box will be extended by features from the non-polyhedral convex case.