Interior-Point Methods for Conic Optimization

在这个项目中，研究者和他的学生研究了凸的改进内点算法，特别是二阶和半定的规划问题。特别是，他们研究为这类大规模问题找到更准确的解决方案，将不可行的内点方法的输出解释为在应用于不可行的问题时寻找不可行的证明，使用黎曼几何的思想为可能不可行的问题开发新的内点方法，并研究用于高度不对称问题的新势垒函数，在这些问题中，通常的原始-唯一或原始-对偶方法效率不高。所有这些想法都是通过在软件包SDPT3中实现的，SDPT3是由研究者和他的两个合作者开发的，这是一个竞争性的原始对偶代码，可以在互联网（例如，athttp://www.math.cmu.edu/~reha/sdpt3.html）和NEOS系统（http://www-neos.mcs.anl.gov/neos/server-solvers.html）for分布式计算)中获得。内点算法是解决大规模资源分配和其他优化问题的一种新的、令人兴奋的计算方法。例如，它们已被用于开发更好的桁架结构设计，如桥梁，可以更好地抵抗大范围的外部负载。另一个应用是天线阵列的设计，以突出某些方向的接受性，而在其他所有方向上都静音。在金融领域，它们被用来开发“最优投资组合”，以平衡一个可接受的回报率和低波动性（不幸的是，这些方法只和他们使用的数据一样好，过去的历史往往不能很好地预示未来的表现）。在这种情况和其他情况下，鲁棒优化的思想非常有吸引力，即使在数据受到轻微扰动的情况下，也能找到满足所有约束的问题的解决方案，并且即使在数据发生轻微变化的情况下也能给出良好的性能度量。这类方法在处理这类问题方面也很成功。这里提到的最后一个应用程序目前正在由研究者和一位统计同事进行研究：试图找到一种将新数据分为两类的好方法(例如：（有或没有癌性肿瘤）基于一些训练数据（已知分类）。该问题是数据挖掘和生物医学领域的研究热点。在所有这些问题中，人们都希望更准确地解决越来越大的实例（涉及成千上万的变量和约束）。研究者和他的合作者从理论上和实践上研究改进现有算法的方法，以扩展它们在这些方向上的能力。

Todd0209457 In this project, the investigator and his students studyimproved interior-point algorithms for convex, especiallysecond-order and semidefinite, programming problems. Inparticular, they investigate finding more accurate solutions tolarge-scale problems of this kind, interpreting the output ofinfeasible-interior-point methods as searching for infeasibilitycertificates when applied to infeasible problems, using ideas ofRiemannian geomentry to develop new interior-point methods forpossibly infeasible problems, and studying new barrier functionsto be used in highly asymmetric problems, where usual primal-onlyor primal-dual methods would be inefficient. All these ideas aretested out by implementing them in the software package SDPT3,developed by the investigator and two of his collaborators, whichis a competitive primal-dual code available over the internet (e.g., athttp://www.math.cmu.edu/~reha/sdpt3.html) and within the NEOS system (http://www-neos.mcs.anl.gov/neos/server-solvers.html)for distributed computing. Interior-point algorithms are a new and excitingcomputational method for solving large-scale resource allocationand other optimization problems. For example, they have beenused to develop better designs for truss structures, such asbridges, that are better able to resist a wide range of externalloads. Another application is the design of antenna arrays tohighlight the receptivity in certain directions while muting thatin all other directions. In finance, they are used to develop"optimal portfolios" to balance an acceptable rate of return withlow volatility (unfortunately, these methods are only as good asthe data they employ, and past history often does not give a goodindication of future performance). In this and other contexts,the idea of robust optimization, to find solutions to problemsthat satisfy all constraints even when the data are perturbed alittle, and that give good performance measures even when thedata are slightly changed, is very attractive, and this class ofmethods is successful in treating some problems of this kindalso. A last application mentioned here is currently beingstudied by the investigator and a statistics colleague: trying tofind a good way to classify new data into one of two classes(e.g., with or without a cancerous tumour) on the basis of sometraining data (with known classification). This problem is ofinterest in data mining and biomedical fields. In all theseproblems, there is a desire to solve larger and larger instances(involving tens of thousands of variables and constraints) moreand more accurately. The investigator and his collaboratorsstudy theoretically and practically ways to improve existingalgorithms to extend their capabilities in these directions.