Add this session to your itinerary


Cluster :

Conic Programming


Session Information

: Thursday Aug 27, 15:15  16:45


Title:

SDP and Its Applications

CoChair:  Sunyoung Kim,Professor, Ewha W. University, 111 Dahyun dong, Seoul 120750, Korea, Republic of, skim@ewha.ac.kr

Chair:  Masakazu Kojima,Tokyo Institute of Technology, Dept. of Math & Comp Sci, 2121W829 OhOkayama Meguro, Tokyo, Japan, kojima@is.titech.ac.jp


Abstract Details


Title:  Nonlinear SDPs by Primaldual Interior Point Method  Global and Superlinear Convergence 
 Presenting Author:  Hiroshi Yamashita,Mathematical Systems Inc., 243, Shinjuku, Shinjukuku, Tokyo, Japan, hy@msi.co.jp

 CoAuthor:  Kouhei Harada,Mathematical Systems Inc., 243, Shinjuku, Shinjukuku, Tokyo, Japan, harada@msi.co.jp

  Hiroshi Yabe,Tokyo University of Science, 13, Kagurazaka, Shinjukuku, Tokyo, Japan, yabe@rs.kagu.tus.ac.jp


Abstract:  We present a class of primaldual interior point methods for nonlinear semidefinite programming problems. The methods are based on Newtonlike method for modified KKT conditions. We apply scaling to the modified complementarity equation, and obtain general expression of search directions which include HRVW/KSH/M and NT in linear SDP.
We discuss merit functions that include primalonly function and primaldual function. We also discuss search algorithms that include line search and trust region.
We show that AHO direction has superlinear convergence property under appropriate conditions, and that HRVW/KSH/M and NT directions have two step superlinear convergence under similar conditions.
Finally, a few numerical examples will be shown.

 
Title:  Most Tensor Problems are NP Hard 
 Presenting Author:  LekHeng Lim,Morrey Assistant Professor, University of California, Berkeley, 873 Evans Hall, Berkeley CA 947203840, United States of America, lekheng@math.berkeley.edu

 CoAuthor:  Christopher Hillar,Mathematical Sciences Research Institute, 17 Gauss Way, Berkeley CA 94120, United States of America, chillar@msri.org


Abstract:  We show that tensor analogues of many problems that are readily computable in the matrix (i.e. 2tensor) case are NP hard in both the traditional CookKarpLevin sense and the BlumShubSmale sense, making SDP relaxation an attractive, if not inevitable, alternative. The problems include: computing a best rank1 approximation, the singular values/vectors, or the spectral norm of a 3tensor; computing the eigenvalues/vectors of a symmetric 3tensor; determining the feasibility of a system of bilinear equations or solving such a system in either an exact or leastsquares sense. These extend Hastad's result on the NPhardness of computing tensor rank to other natural tensor problems. 
 
Title:  Duality in the Positive Semidefinite Matrix Completion and Its Application to SDPs 
 Presenting Author:  Masakazu Kojima,Tokyo Institute of Technology, Dept. of Math & Comp Sci, 2121W829 OhOkayama Meguro, Tokyo, Japan, kojima@is.titech.ac.jp


Abstract:  We present a necessary and sufficient condition for a sparse and symmetric matrix A to be positive semidefinite as a dual approach of the positive semidefinite matrix completion method. Here we assume that the sparsity pattern of A is characterized with a chordal graph G(N,E). The ith row or ith column of A corresponds to the node i in N, and nonzero (i,j)th element of A to the edge (i,j) in E. We also discuss how the condition can be utilized for exploiting the sparsity of linear and nonlinear SDPs.

 
