Preprints

- G. Azuma, S. Kim and M. Yamashita, "Tight Semidefinite Relaxations for Verifying Robustness of Neural Networks", arXiv:2504.09934, Apr. 2025.

- M. Kojima, S. Kim and N. Arima, "Extending Exact SDP Relaxations of Quadratically Constrained Quadratic Programs", arXiv:2504.03204, Apr. 2025.

- M. Kojima, N. Arima and S. Kim, "Constructing QCQP Instances Equivalent to Their SDP Relaxations", arXiv:2502.15206, Feb. 2025.

- N. Arima, S. Kim and M. Kojima, "Exact SDP relaxations for a  class of quadratic programs with finite and infinite quadratic constraints", arXiv:2409.07213, Sept. 2024.

- S. Kim and M. Kojima, "Generating cutting inequalities successively for binary quadratic optimization problems",  arXiv:2107.08665, July 2021.

Publications

- G. Azuma, S. Kim and M. Yamashita, "Exact Matrix Completion via High-Rank Matrices in Sum-of-Squares Relaxations",  arXiv:2311.14882,  Journal of Global Optimization, 92, 2, 321-343 (2025).

-  K. Fujii, S. Kim, M. Kojima, H. D. Mittelmann, and Y. Shinano,  "An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c",   arXiv:2401.09439,  Optimization Letters, 19, 6, 1075-1097 (2025). 

- S. Kim and M. Kojima, "Equivalent Sufficient Conditions for Global Optimality of Quadratically Constrained Quadratic Program",  arXiv:2303.05874, Mathematical Methods of Operations Research, 101, 1, 73-94 (2025).

- S. Kim and M. Kojima, "Strong duality of a conic optimization problem with two cones and a single equality constraint",  arXiv:2111.03251,  Optimization, 74, 1, 33-53 (2025). 

- N. Arima, S. Kim and M. Kojima, "Further Development in Convex Conic Reformulation of Geometric Nonconvex Conic Optimization Problems",  arXiv:2308.05922,  SIAM Journal on Optimization, 34, 4, 3194-3211, (2024).

- H. Marumo, S. Kim and M. Yamashita, "T-semidefinite programming relaxation with third-order tensors for constrainded polynomial optimization", arXiv:2402.08438, Computational Optimization and Applications, 89, 183-218 (2024).

  - G. Azuma, M. Fukuda, S. Kim, and M. Yamashita "Exact SDP relaxations of quadratic programs with bipartite graph structures",   arXiv:2204.09509,  Journal of Global Optimization, 86, 671-691 (2023).

- G. Azuma, M. Fukuda, S. Kim, and M. Yamashita "Exact SDP relaxations of quadratically constrained quadratic programs with forest structures",  arXiv:2009.02638, Sep. 2020,  Journal of Global Optimization, 82(2) 243-261 (2022).

- S. Kim, M. Kojima and K.C. Toh, "A Newton-bracketing method for a simple conic optimization problem",  arXiv:1905.12840, May 2019,  Optimziation Methods and Software 36(2-3), 371-388 (2021).

- S. Kim, M. Kojima and K.C. Toh, "Doubly Nonnegative Relaxations for Quadratic and Polynomial Optimization Problems with Binary and Box Constraints", July 2016. Research report B-483, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology,  Mathematical Programming 193, 761-787 (2022). 

- S. Kim, M. Kojima and K.C. Toh, A Geometric Analysis of a Class of Nonconvex Conic Programs for Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems, arXiv:1901.02179, Jan.  2019,  SIAM J. on Optimization, 30(2), 1251-1273 (2020). 

- S. Kim, M. Kojima and K.C. Toh, Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures, arXiv:1903.07325, Mar. 2019,  Journal of Global Optimization, 77(3), 513-541 (2020).

- T. Nakagaki, M. Fukuda, S. Kim, and M. Yamashita, "A Dual Spectral Projected Gradient Method for Log-determinant Semidefinite Problems,  Research Report B-490, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Nov. 2018, arXiv:1812.00253,  Computational Optimization and Applications, 76(1) 33-68 (2020).

- H. Komeiji, S. Kim and M. Yamashita, Sums of Squares Representation of Polynomials by Alternating Directional Augmented Lagrangian Methods with Fast Convergence, March 2018. Research Report B-488, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Computational Optimization and Applications, 74, 317-344 (2019).

- M. Kimizuka, S. Kim and M. Yamashita, Solving Pooling Problems with Time Discretization by SDP, SOCP and LP relaxations and Rescheduling Methods,  Feb. 2018. Research Report  B-487,  Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Journal of Global Optimization, 75(3) 631-654 (2019).

- N. Ito, S. Kim, M. Kojima, A. Takeda, and K.C. Toh, BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints, Mar. 2018, arXiv:1804.00761. ACM Transaction on Mathematical Software, 45(3) 34 (2019). 

- N. Arima, S. Kim, M. Kojima, and K.C. Toh, Lagrangian-Conic Relaxations, Part II: Applications to Polynomial Optimization Problems, Pacific Journal of Optimization, 15(3) 415-439 (2019). 

- N. Ito, S. Kim, M. Kojima, A. Takeda and K.C. Toh, Equivalence and Differences in Conic Relaxation of Combinatorial Quadratic Optimization Problems, July 2019. Research report B-486, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Journal of Global Optimization 72(4) 619-653 (2018). 

- S. Sakaue, A. Takeda, S. Kim and N. Ito, Exact SDP relaxations with truncated moment matrix for binary polynomial optimization problems, Technical Report METR 2016-01, Department of Mathematical Informatics, The University of Tokyo, Jan. (2016). SIAM J. on Optimization, 27(1) 565-582 (2017). 

- N. Arima, S. Kim, M. Kojima, and K.C. Toh,"Lagrangian-Conic Relaxations, Part I: A Unified Framework and Its Applications to Quadratic Optimization Problems, Research Report B-475, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Jan. (2014) Pacific J. Optimization. 14(1) 161-192 (2018). 

- N. Arima, S. Kim, M. Kojima, and K.C. Toh, A Robust Lagrangian-DNN Method for a Class of Quadratic Optimization Problems, Research Report B-482, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Feb. (2016). Computational Optimization and Applications, 66(3) 453-479 (2017).

- S. Kim and M. Kojima, Binary Quadratic Optimization Problems That Are Difficult to Solve by Conic Relaxations, Research Report B-481, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, July (2015) Discrete Optimization, 24, 170-183 (2017).  

- V. Jeyakumar, S. Kim, G.M. Lee, and G. Li, Solving Global Optimization Problems with Sparse Polynomials and Unbounded Semialgebraic Feasible Sets, Journal of Global Optimization, Vol 65, 175-190 (2016).  

- N. Arima, S. Kim, M. Kojima, Extension of Completely Positive Cone Relaxation to Polynomial Optimization, Research Report B-471, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Feb (2013). Journal of Optimization Theory and Applications, Vol 168, 884-900 (2016).

- S. Kim, M. Kojima and K.C. Toh, A Lagrangian-DNN Relaxation: a Fast Method for Computing Tight Lower Bounds for a Class of Quadratic Optimization Problems, Research Report B-472, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Oct (2013). Mathematical Programming, Vol 156, 161-187 (2016).

- N. Arima, S. Kim and M. Kojima, Simplified Copositive and Lagrangian Relaxations for Linearly Constrained Quadratic Optimization Problems in Continuous and Binary Variables, Pacific Journal of Optimization, 10, 437-451 (2014).

- S. Burer, S. Kim and M. Kojima, Faster, but Weaker, Relaxations for Quadratically Constrained Quadratic Programs, Computational Optimization and Applications,  59, 27-45 (2014).

- N. Arima, S. Kim and M. Kojima, A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming,  SIAM J. on Optimization, 23, 2320-2340 (2013).

- S. Kim and M. Kojima, A Continuation Method for Large-sized Sensor Network Localization Problems,  Pacific Journal of Optimization,  9, 1 117-136 (2013).

- S. Kim, M. Kojima, H. Waki, and M. Yamashita, Algorithm 920: SFSDP: a Sparse Version of Full SemiDefinite Programming relaxation for sensor network localization problems, A Matlab package SFSDP,  ACM Transaction on Mathematical Software, 38, 4 (2012).

- S. Kim and M. Kojima, Exploiting Sparsity in SDP Relaxation of Polynomial Optimization Problems, Handbook on Semidefinite, Conic and Polynomial Optimization: theory, algorithm, software and applications, M. Anjos and J.B. Lasserre eds., Nov. (2011)  499-532.

- S. Kim and M. Kojima, A Sparse Semidefinite Programming Relaxation for Sensor Network Localization, Proceedings of 2010 IEEE Multi-conference on Systems and Control, 1- 4 (2010).

- S. Kim, M. Kojima, M. Mevissen and M. Yamashita, Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion ,  Mathematical Programming, 129,  1, 33-68 (2011).

- S. Kim and M. Kojima, Solving Polynomial Least Squares Problems via Semidefinite Programming Relaxations, Journal of Global Optimization,  46., 1, 1-23 (2010).

- S. Kim, M. Kojima, and H. Waki, Exploiting Sparsity in SDP Relaxation for Sensor Network Localization, SIAM Journal on Optimization,  20,  1, 192-215 (2009). Listed in Top 20 Most Downloaded Articles of SIAM Journal on Optimization -- April 2009.

-  S. Kim, M. Kojima and Ph. L. Toint, Recognizing Underlying Sparsity in Optimization, Mathematical Programming,   119, 2, 273-303 (2009).

- H. Waki, S. Kim, M. Kojima, M. Muramatsu, SparsePOP: a Sparse Semidefinite Programming Relaxation of  Polynomial Optimization Problems,  ACM Transaction on Mathematical Software,   35, 2, Algorithm 883, Article No. 15 (2008). 

- K. Kobayashi, S. Kim and M. Kojima,  Sparse Second Order Cone Programming Formulations for Convex Optimization Problems,  Journal of Operations Research Society of Japan,  51, 3, 241-264 (2008). 

- T. Gunji, S. Kim, K. Fujisawa, M. Kojima, PHoMpara - Parallel Implementation of the Polyhedral Homotopy Continuation Method, Computing,  77,  4, 387-411 (2006).

- H. Waki, S. Kim, M. Kojima, M. Muramatsu, Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity,  SIAM Journal on Optimization, 17,  1, 218-242 (2006).

- M. Kojima,  S. Kim and H. Waki, Sparsity in  Sums of Squares of Polynomials,  Mathematical  Programming,} 103, 1, 45-62 (2005).

- S. Kim, M. Kojima and H. Waki, Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems, SIAM Journal on Optimization,   15,  3, 697-719 (2005).

- S. Kim and  M. Kojima, Numerical Stability of Path Tracing in Polyhderal Homotopy Continuation Methods, Computing,  73,  4, 329-348 (2004).

- T. Gunji, S. Kim, M. Kojima, A. Takeda, K. Fujisawa and T. Mizutani, PHoM - a Polyhderal Homotopy Continuation Method for Polynomial Systems, Computing, 73,  1, 57-77, (2004).

- S. Kim, M. Kojima and M. Yamashita Second Order Cone Programming Relaxation of a Positive Semidefinite Constraint, Optimization Methods and Software,  18,  5, 535-541 (2003).

- S. Kim and M. Kojima, Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP relaxations, Computational Optimization and Applications,   26,  2, 143-154 (2003).

- M. Kojima, S. Kim and H. Waki, A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones,  Journal of Operation Research Society of Japan,  46,  2, 125-144 (2003).

-  Y. Dai, S. Kim and M. Kojima, Computing All Nonsingular Solutions of Cyclic-n Polynomial Using Polyhedral Homotopy Continuation Methods,  Journal of Computational and Applied Mathematics,   152, 1/2, 83-97 (2003).

-  S. Kim and M. Kojima, CMPSc: A Continuation Mathod for Polynomial Systems (C++ Version), CMPSm: A Continuation Mathod for Polynomial Systems (Matlab Version), Mathematical Software, ICMS2002 Beijing, China, August 17-19 (Editors: Arjeh M Cohen, Xiao-Shan Gao and Nobuki Takakayama), World Scientific, 248-259 (2002).

-  H. Ahn, H. Moon, S. Kim and R. Kodell, A Newton-Based Approach for Attributing Tumor Lethality in Animal Carcinogenicity Studies, Computational Statistics and Data Analysis, 38,  3, 263-283 (2002).

- S. Kim and M. Kojima, Second Order Cone Programming Relaxation Methods of Nonconvex Quadratic Optimization Problem,  Optimization Methods and Software, 15,  3, 201-224 (2001).

- S. Kim, Solutions of Nonconvex Quadratic Optimization Problems via Diagonalization, Korean Society for Industrial and Applied Mathematics, 2, 137-147 (2001).

- S. Kim, A Convergence Criterion for Secant Method with Approximate Zeros, Korean Journal of Computational and Applied Mathematics, 6, 3, 575-588 (1999).

- S. Kim, Numerical Solutions of Cauchy Singular Integral Equations Using Generalized Inverses, Computers and Mathematics with Applications,  38, 5, 183-195 (1999).

- S. Kim, Solving Singular Integral Equations Using Gaussian Quadrature and Overdetermined System, Computers and Mathematics with Applications,  35, 10, 63-71 (1998).

- S. Kim,Generalized Inverses In Numerical Solutions, Communication of Korean Mathematical Society,  13, 4, 875-888 (1998).

- S. Kim and R. Srivastav, Computation Techniques for Inverse Problems,  Applied Mathematics Letter, 9, 3, 77-81 (1996).

- S. Kim, Kantorovich-type Convergence Analysis of Quasi-Gauss-Newton Methods,  Journal of Korean Mathematical Society, 33, 4, 865-878 (1996).

- S. Kim, Numerical Methods using Trust- Region Approach for Solving  Nonlinear Ill-Posed Problems, Communication of Korean Mathematical Society, 11,4, 1147-1157 (1996).

- S. Kim and R. P. Tewarson, The Convergence of Quasi- Gauss-Newton Methods for Nonlinear Equations, Computers and Mathematics with Application,  29, 3, 27-38 (1995).

- S. Kim, A Quasi-Newton Algorithm Using Directional Derivatives for Communication of Korean Mathematical Society, 9, 2, 112-120 (1994).

- S. Kim, On Improving Gauss-Newton Methods for Nonlinear Equations, Communication of Korean Mathematical Society}, 9, 3, 739-751 (1994).

- S. Kim and R. P. Tewarson, A Quasi-Newton Method for Solving Nonlinear  Algebraic Equations, Computers and Mathematics with Application, 24, 4, 93-97 (1992).

- S. Kim and R. P. Tewarson, Using Quasi-Newton Methods for Kidney Modeling Equations, Applied Mathematics Letter, 3, 2, 93-96 (1990).