Interior-Point Methods for Conic Optimization

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

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.