It is important that we have discussions on improving various shading algorithms using Pixar's Renderman and implementations with modern fast numerical techniques. For such discussions, we may need to have wide knowledge about modern numerical computations. In this seminar, we invite Prof. Waki (IMI, Kyushu University) who is an expert in Optimization theory, and have discussions from this point of view (shading algorithms and their implementations). Moreover, as in the past seminars in this series, we have a talk about an importance in symbolic computations. Any your commitment to this seminar from your academic viewpoint is welcome.
Prof. Waki wrote the following introduction to Optimization theory (at the end of this page) for this workshop. Please take a look at his message if you would like to attend the seminar.
Please bring your lunch since school cafeteria is closed.
Optimization appears not only in science and engineering, but also in various business scenes for decisions-making and is used for selecting a best way with regard to some criteria from some sets of candidates. For instance, decision-making in business, such as logistics, scheduling and facility location. We can also solve sudoku by using optimization. Recently, IBM proposes “Business Analytics and Optimization”, that is, the importance of analytics and optimization for Bigdata in business scenes. You may recognize the importance of optimization from this.
I give a tutorial of optimization which uses mathematical expressions, which is called mathematical optimization. Optimization theory is the fundamentals of solutions and algorithms for solving optimization problems. For instance, linear programming problem, which is one of the fundamentals, is the problem of optimizing a linear function over a polyhedral. It is well-known that an optimal solution is at a vertex of the polyhedral. The simplex method is a practical algorithm for solving linear programming problems and is based on this fact. Actually, the simplex method efficiently traces some vertices to obtain an optimal solution. Optimization theory is necessary for developing algorithms to solve optimization problems effectively.
Optimization theory is related to various scientific fields. One of them is (theoretical) computer science. In fact, computer science studies the difficulty of optimization problems, such as classes P and NP. The concept is important to develop algorithms for optimization problems. Another is graph theory, which is used for optimization problems described by mathematical representation of a set of objects where some pairs of objects are connected by links. (This representation is called “graph”.) You may be able to use graph theory to develop an efficient algorithm for such cases. Gradient descent and newton method are well-used for optimization problems which consist of continuous variables. The products of matrices and vectors are based on these methods. In this sense, optimization theory is closely related to numerical analysis and computation.
High performance computing (HPC), such as super computer, is necessary to exploit big data in optimization. Recently, optimization which uses HPC has been actively researched. For instance, graph search technology for super big graph, such as Facebook, twitter and traffic network is developed by JST CREST team (PI: Katsuki Fujisawa (Chuo Univ. Japan)). In Green Graph500 in SC'13, we top two lists and smash through 6 MTEPS/W and 150MTESP/W in the big data category and small data category, respectively. See http://www.imi.kyushu-u.ac.jp/news/view/458 and http://www.graphcrest.jp/jp/news2013-11-b.html for the details.
Optimization is related to economics, too. Koopmans and Kantrovich (1975), Markowitz (1990) and Nash (1994) won the Sveriges Riksbank Prize in Economics Sciences in Memory of Alfred Nobel. The first two results use linear programming problems and other optimization problems. The result by Nash is related to game theory. In fact, game theory is closely related to the duality of linear programming problems. Optimization not only is useful in solving problems in business scenes, but also contributes to development of some academic fields.
The Institute of Mathematics for Industry (IMI) at Kyushu University was established for industrial mathematics based on diverse fields of mathematics research on April 1, 2011 as the institute in Asia. Mathematics for Industry (MI) is a new research area that will serve as a hub for future technologies, whose aim is to meet to the needs of the industrial field by reorganizing pure and applied mathematics as flexible and versatile forms. See http://www.imi.kyushu-u.ac.jp/eng/ for IMI.
We aim to develop mathematical theories and theorems discovered at IMI into algorithms and to implement them as software. Software will be internationally released in order to contribute to advanced researches in industries and various scientific areas including mathematics itself. Moreover, we organize some of workshop and seminars related to research and development of mathematical software.
IMI has set up an office to provide a broad range of technical consultation to people both inside and outside of Kyushu University on mathematical problems concerning industrial technologies. In addition to providing consultation on practical problems in everyday research or work in relation to numerical simulation, statistical techniques, optimization, etc., consultation is also available to who look for mathematical solutions to problems in the industrial field or in other engineering or information technologies. See http://www.imi.kyushu-u.ac.jp/eng/technical_consultations for technical consultation of IMI.
I graduated from department of mathematical and computing sciences, Tokyo Institute of Technology with PhD in 2007. I have currently been Associate Professor at Institute of Mathematics for Industry, Kyushu University since 2012. My research interests are optimization and development of software for optimization.
My research interests lie in the theory, computation and applications of conic optimization. In particular, I am strongly interested in research for solving nonlinear and nonconvex optimization problems by using conic optimization. In fact, Professor Masakazu Kojima and I proposed an efficient approach for finding global solutions of optimization problems that are described with polynomials. Such optimization problems are called Polynomial Optimization Problems (POPs). We demonstrated that our approach is effective for POPs with a sparse structure. In general, it is known that finding a global solution of POP is NP-hard. Lasserre and Parrilo independently proposed approaches that use SDPs for POPs. Although their results are quite good from the theoretical viewpoint, they are not effective for POPs with more than 20 decision variables. On the other hand, our approach can solve some POPs with more than 1000 variables. Through this work, we developed software for solving POPs: SparsePOP http://sourceforge.net/projects/sparsepop/. This is open-source software and is available at the site above.
An application of POPs is that we dealt with sensor network localization problems, which arise in monitoring and controlling applications using wireless sensors networks, such as gathering environmental data. Although GPS capability is more suitable than wireless sensors for this purpose, it is usually inexpensive for applications, and thus is not an option. For this, we proposed an approach based on our work related to POPs and developed the software: SFSDP http://www.is.titech.ac.jp/~kojima/SFSDP/SFSDP.html. This is also open-source software and is available at the site above.