University of Liverpool | School of Electrical Engineering, Electronics and Computer Science | Liverpool | United Kingdom
Supervisors:
Prof Piotr Krysta (Computer Science)
Dr Matthew Dyer {Chemistry)
Prof Rahul Savani (Computer Science)
Application Deadline: Wednesday, July 31, 2019
Project Description
This position will remain open until a suitable candidate has been found.
This PhD position is funded by the Leverhulme Centre for Functional Materials Design that has been recently launched at the University of Liverpool. This centre is one of only 4 such centres funded in the UK and brings together expertise in chemistry with state-of-the-art computer science and automated technologies to develop a new approach to revolutionise the design of functional materials at the atomic scale.
The research questions that we are going to consider within this new PhD project on "Design and Analysis of Algorithms for Continuous Optimisation with Applications to Crystal Structure Prediction" will be related to several areas of Theoretical Computer Science (e.g., the design and theoretical analysis of algorithms and computational complexity theory), Discrete and Continuous Optimisation (e.g., mathematical programming, convex and non-convex optimisation), as applied to Crystal Structure Prediction (CSP), a topic in Computational Chemistry.
The prediction of crystal structures with lowest potential energy, and therefore most stable, configuration of the atoms is still a largely unresolved challenging computational problem. The main complexity comes from the combinatorial explosion in the number of possibilities and unpredictable nature of non-convex energy landscape. The current computational methods mainly fail to provide reliable low energy structures prediction for atomic structures containing more than 100-150 atoms per the unit cell and become even useless with significant increase of potentially available types of atoms for new structures. The currently used variants of simulated annealing or genetic algorithms also have their own different limitations.
We will consider a family of continuous optimisation problems with convex or smooth but non-convex objective functions, where various fast algorithms have been developed by the Theoretical Computer Science community, with proven polynomial time bounds on their running time. These algorithms find global (approximate) optima, in the case of convex optimisation, and (approximately) local optima in case of non-convex smooth optimisation. The goal of this research is to design and analyse (new variants of) such algorithms for classes of such optimisation problems inspired by crystal structure prediction.
In crystal structure prediction (CSP), specific energy functions are minimised in search of minimal energy constellations of a collection of atoms of different kinds. The energy functions are known to be smooth but highly non-convex, so finding global optima may be challenging. However, even local optima are of importance, because they also correspond to chemically stable crystal structures. This area opens very interesting avenues to theoretical optimisation algorithmics, where faster such solvers for classes of optimisation problems motivated by CSP will be sought.
This project will look at the design and analysis of state of the art algorithms for classes of such continuous optimisation problems, where the focus of this PhD project will mostly be theoretical analysis. In addition, to evaluate the usefulness of these new algorithms, we will also implement them and test them on real-world CSP problems.
Qualifications
We welcome talented and highly motivated candidates with good first degree (BSc or MSc) in Computer Science, Mathematics or closely related subject. A programming experience and/or previous research experience would be a distinct advantage though it is not essential.
Informal enquiries should be addressed to Prof Piotr Krysta (P.Krysta@liverpool.ac.uk)
Please apply by completing the online postgraduate research application form here: https://www.liverpool.ac.uk/study/postgraduate-research/how-to-apply/
Please ensure you quote the following reference on your application: "Design and Analysis of Algorithms for Continuous Optimisation with Applications to Crystal Structure Prediction" (Reference: LRC CS1909)
Funding Notes
The award is primarily available to students resident in the UK/EU and will pay full tuition fees and a maintenance grant for 3.5years (£14,777 pa in 2018/19). Non-EU nationals are not eligible for this position and applications from non-EU candidates will not be considered unless you have your own funding.
References
Yurii Nesterov and Boris T. Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177–205, 2006.
Scott M. Woodley and Richard Catlow. Crystal structure prediction from first principles.
Nature Materials 7, 937–946 (2008) doi:10.1038/nmat2321
http://www.nature.com/articles/nmat2321
-----
Professor Piotr Krysta
University of Liverpool
Department of Computer Science
Ashton Building, Ashton Street
Liverpool L69 3BX, U.K.
http://www.csc.liv.ac.uk/~piotr
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
