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

投影凸集的算法及其在非凸规划和凸集微积分中的应用

• 批准号: 271835661
• 负责人: Professor Dr. Andreas Löhne
• 金额: --
• 依托单位: Lehrstuhl für Mathematische Optimierung
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2015
• 资助国家: 德国
• 起止时间: 2014-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/271835661?language=en
• 关键词: Algorithms; project; convex; sets; applications

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.

将有限维凸集投影到低维子空间上的数学问题，在低维子空间中原凸集是解析给定的，在该问题中起着关键作用。投影集将以两种不同的方式表示：在第一种方法中，该集合由凸多面体近似表示。在第二种方法中，用线性矩阵不等式来表示，或者如果不可能，用线性矩阵不等式来近似。凸投影问题将应用于某些非凸优化问题，我们的目标是找到精确解。在这些问题类别中，有底层凸的双层问题，已知目标函数的DC表示的DC规划问题，以及具有拟凹目标函数和凸约束的优化问题。在运行的项目中，这种方法被考虑用于多面体情况。多面体投影问题等价于向量线性规划（VLP）。因此，上述全局优化问题的多面体版本可以通过VLP求解器“bensolve”来求解。对于非多面体凸情况，将得到相应的结果。这包括通过求解凸向量优化问题来处理标量全局优化问题。或者，我们计划将改进的凸向量优化算法直接应用于凸投影问题。所谓的局部版本的算法解决一个局部的投影问题（即在一个区域的兴趣的投影集）。因此，当应用于标量全局优化问题时，它们可以提高性能。在正在运行的项目中，采用多面体投影，利用自由软件“bensolve tools”实现多面体凸集和多面体凸函数的数值演算。此工具箱将通过非多面体凸情况的特征进行扩展。