Session Detail Information
Add this session to your itinerary

Cluster :  Conic Programming

Session Information  : Thursday Aug 27, 15:15 - 16:45

Title:  SDP and Its Applications
Co-Chair: Sunyoung Kim,Professor, Ewha W. University, 11-1 Dahyun dong, Seoul 120-750, Korea, Republic of, skim@ewha.ac.kr
Chair: Masakazu Kojima,Tokyo Institute of Technology, Dept. of Math & Comp Sci, 2-12-1-W8-29 Oh-Okayama Meguro, Tokyo, Japan, kojima@is.titech.ac.jp

Abstract Details

Title: Nonlinear SDPs by Primal-dual Interior Point Method - Global and Superlinear Convergence
 Presenting Author: Hiroshi Yamashita,Mathematical Systems Inc., 2-4-3, Shinjuku, Shinjuku-ku, Tokyo, Japan, hy@msi.co.jp
 Co-Author: Kouhei Harada,Mathematical Systems Inc., 2-4-3, Shinjuku, Shinjuku-ku, Tokyo, Japan, harada@msi.co.jp
 Hiroshi Yabe,Tokyo University of Science, 1-3, Kagurazaka, Shinjuku-ku, Tokyo, Japan, yabe@rs.kagu.tus.ac.jp
 
Abstract: We present a class of primal-dual interior point methods for nonlinear semidefinite programming problems. The methods are based on Newton-like 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 primal-only function and primal-dual 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: Lek-Heng Lim,Morrey Assistant Professor, University of California, Berkeley, 873 Evans Hall, Berkeley CA 94720-3840, United States of America, lekheng@math.berkeley.edu
 Co-Author: 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. 2-tensor) case are NP hard in both the traditional Cook-Karp-Levin sense and the Blum-Shub-Smale sense, making SDP relaxation an attractive, if not inevitable, alternative. The problems include: computing a best rank-1 approximation, the singular values/vectors, or the spectral norm of a 3-tensor; computing the eigenvalues/vectors of a symmetric 3-tensor; determining the feasibility of a system of bilinear equations or solving such a system in either an exact or least-squares sense. These extend Hastad's result on the NP-hardness 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, 2-12-1-W8-29 Oh-Okayama 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.