Symmetric Cone Optimization Algorithmic and Structural Study Application Development

这个项目的主要目标是从算法、数值和软件开发的角度研究对称锥和扩展的优化问题的各个方面。这类优化问题包括半定规划（SDP）和二次约束二次规划（QCQP），并与之密切相关。在第一部分中，将深入研究简并性的一般技术及其对各种算法数值行为的影响。将特别注意处理缺乏严格互补性的问题，迄今为止，在所有已知的算法中都没有令人满意的数值行为。接下来，将最初为分析半定和凸二次约束二次规划而开发的特殊证明技术和工具扩展到更一般的对称锥优化场所。内点研究人员开发的技术将扩展到所有对称锥优化问题。这方面研究的一个潜在影响将是将内部点研究中的各种努力，特别是原始对偶方法，统一到更一般的对称锥优化领域，包括线性，半定和二次约束二次规划作为特殊情况。接下来，将研究使用一个SDP（或QCQP）的最优解来“热启动”另一个SDP（或QCQP）的中心问题，该SDP（或QCQP）与原始SDP（或QCQP）有一个或几个新的约束或变量。这一努力是为了使SDP或QCQP成为通过分支定界、切割平面或类似技术求解大整数或混合整数程序的重要工具。一个特定的目标是发明新的基于对偶的活动集方法来实现这一目标。该项目将从调查QCQP本身的简单问题开始，以便在解决SDP和最终一般对称锥优化问题的努力中获得洞察力。此外，在使用QCQP问题作为整数规划的松弛时，也存在令人困惑的差距。虽然LP和SDP松弛存在，但QCQP方法仅用于有限的问题，如植物定位和斯坦纳树。缺少将任意（0 - 1）整数程序松弛到QCQP的一般方案。这种努力的目标是设计这样一种一般的放松。其潜在影响是巨大的。虽然SDP至少在原则上似乎比LP更强大，作为整数规划的松弛，但解决大规模问题的困难，特别是缺乏令人满意的技术来解决稀疏问题，迄今为止限制了它的广泛应用。QCQP的限制要严重得多，针对这些问题的一般松弛方案可能至少对某些整数规划问题产生重大影响。接下来将研究比传统线性规划或SDP更一般的凸规划的整数规划的新松弛。一个基于使用比欧几里得范数更一般的范数的特殊方案可能会产生新的锥类，人们可以将SDP松弛扩展到这些锥类。这项工作一开始将是理论性的和基础性的。数值研究，特别是稀疏结构的使用包含了项目的另一个方面。特别是不像半定规划，有点像线性规划，在利用稀疏性的一个重要机会，以解决大规模的QCQP问题与原对偶内点法。其细节与线性规划不同，在设计数值稳定和高效的算法方面存在相当大的挑战。软件开发也将是调查的核心部分。特别是由于SDP和QCQP格式的多样性，以及在应用程序中出现的一般对称锥优化问题，如果软件要具有广泛的适用性，用户友好的界面将是必不可少的。因此，除了实现和微调“求解引擎”外，还计划在引擎周围设计一个精心设计的外壳。该接口将被设计用于适应从特征值优化到规范约束和的各种问题。尽可能多的格式转换将自动进行。计划与流行的公共建模语言（如AMPL）的接口。此外，还计划在用户和软件之间进行基于WEB的交互（例如基于WEB的数据提交，或者用户数据和软件之间的跨平台交互）。特别是，在通过WEB将数据提交给服务器解决方案之前，可以在客户端对数据进行一些预处理。

The main goal of this project is to investigate all aspects of optimization problems over symmetric cones and extensions from algorithmic, numerical and software development points of view. Such optimization problems include and are closely related to semidefinite programming (SDP) and quadratically constrained quadratic programming (QCQP). In the first part, general techniques for both degeneracy properties and their impact on numerical behavior of various algorithms will be studied thoroughly. Particular attention will be given to the problem of dealing with absences of strict complementarity which thus far has eluded satisfactory numerical behavior in all known algorithms. Next, the process of extending special proof techniques and tools which were originally developed for analysis of the semidefinite and convex quadratically constrained quadratic programs, to the more general venue of symmetric cone optimization will be carried out. The techniques developed by interior point researchers will be extended to all symmetric cone optimization problems. A potential impact of this aspect of the research will be unification of various efforts in interior point studies, especially the primal-dual methods, to the more general area of symmetric cone optimization which includes linear, semidefinite, and quadratically constrained quadratic programming as special case. Next, the central problem of using the optimal solution of an SDP (or a QCQP) to "warm start" another SDP (or QCQP) that differs from the original by one or few new constraints or variables will be investigated . This effort is central in order to make SDP or QCQP serious tools for solving large integer or mixed integer programs via branch and bound, cutting planes or similar techniques. A particular goal is to invent new dual based active set methods to carry out this goal. The project will start with perhaps the easier problem of investigating QCQP both in its own right and in order to gain insight in the effort to tackle SDP and ultimately general symmetric cone optimization problems. Also there is a puzzling gap in using QCQP problems as relaxation of integer programs. While LP and SDP relaxation abound, the QCQP approach has been use only on limited problems such as plant location and Steiner trees. A general scheme to relax any (zero-one) integer program to QCQP is missing. A goal of this effort is to design such a general relaxation. The impact is potentially significant. While SDP at least in principle seems to be more powerful than LP to as a relaxation of integer programs, the difficulty of solving large scale problems, especially lack of satisfactory techniques to solve sparse problems, has so far limited its wide scale use. The limitations on QCQP are much less severe and a general relaxation scheme to these problems could have significant impact on at least some integer programming problems.Next new relaxation of integer program to more general convex programs than the traditional linear programming or SDP will be studied. A particular scheme based on using norms more general than the Euclidean norm will potentially yield new class of cones to which one can extend SDP relaxation. This work will be theoretical and fundamental at the outset.Numerical study and in particular use of sparse structure encompasses another aspect of the project. In particular unlike semidefinite programming and somewhat like linear programming there is an significant opportunity in taking advantage of sparsity in order to solve large scale QCQP problems with primal-dual interior point methods. The details are different than linear programming and present considerable challenge in designing numerically stable and efficient algorithms. Software development will also be a central part of the investigation. Especially due to the vast variety of formats that SDP and QCQP, and in general symmetric cone optimization problems arise in applications, a user friendly interface will be essential if the software will be of wide applicability. Therefore, in addition to implementing and fine tuning the "solver engine", an elaborate shell around the engine is planned. This interface ill be designed to accommodate various problems form eigenvalue optimization to sum of norms constraints. As much as possible format conversions will be automated. Interface to popular public modeling languages such as AMPL is planned. In addition WEB based interaction between users and software (such as web based submission of data, or cross platform interaction between user's data and the software) is planned. In particular some preprocessing of the data may be done on the client side, before the data is submitted over the WEB to the server for solution.