Ewha Womans University Mathematics

Research Areas

Prof. Sunyoung Kim

Math Programming Lab

Faculty Introduction
Prof. Sunyoung Kim
Prof. Sunyoung Kim
Research Area
  • Math programming
  • Numerical Analysis
  • Bigdata
Lab Introduction

Research interests of our group lie in conic programming, global optimization, polynomial optimization, combinatorial optimization, and nonlinear programming.

Conic relaxations have been widely studied for modeling real-world applications. We study semidefinite relaxations, second-order cone relaxations, doubly nonnegative relaxations, copositive relaxations, and completely positive relaxations from the theoretical and computational viewpoints. - Our strengths have been exploiting the sparsity in the conic relaxations of the problems, especially the chordal sparsity by combining the result from graph theory. The sparsity technique is employed to increase the efficiency of solving the problems. -

Based on theoretical studies of modeling problems, software packages have been developed in Matlab. The released software packages are 'SparsePOP' for polynomial problems, 'SFSDP' for sensor network problems, 'SparseCoLO' for conic problems with sparsity exploitation, 'BBCPOP' for polynomial problems in binary and box variables, and 'NewtBracket' for conic optimization problems.

For combinatorial optimization problems, finding the solutions of fundamental problems such as the max-cut problems, the max-clique problems, multiple-knapsack problems, and quadratic assignment problems are the main subjects of our research. These problems are NP-hard problems. Solutions of NP-hard problems are sought with approximating schemes or branch and bound methods. Our focus is first on developing efficient and effective approximating schemes, more precisely, tight convex relaxations and providing their theoretical convergence results. Second, the approximation schemes are incorporated into the branch and bound methods to find the exact solutions of the problems. Various branching rules and cutting methods are studied and developed.

We actively participate in international conferences and collaborate with internationally renowned scientists.

Major research projects and Research achievements
Conic programming
Conic programming
  • Semidefinite programming
  • Second order cone programming
  • Polynomial optimization
  • Sparsity exploitation
  • Doubly nonnegative relaxations
  • Huge-scale quadratic optimization problems
Software packages
Software packages
  • “SparsePOP” for sovlingpolynomial optimization problems
  • “SparseCoLO” for exploiting the chordal sparsity
  • “SFSDP” for solving sensor network localization problems
  • “BBCPOP” for solving polynomial optimization problems in binary and boxed variables
  • “NewtBracket” for simple conic optimization problems
Selected research papers
  • S. Kim, M. Kojima, K.C. Toh, ”Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and boxed constraints”, to appear in Mathematical Programming (published online).
  • S. Kim, M. Kojima, K.C. Toh, “A geometrical analysis of a class of nonconvex conic programs for convex conic reformulations of quadratic and polynomial optimization problems”, SIAM J. on Optimization, 30(2) 1251-1273 (2020).
  • S. Kim, M. Kojima, K.C. Toh, “Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique structures”, Journal of Global Optimization, 77(3), 513-541 (2020).
  • T. Nakagaki, M. Fukuda, S. Kim, M. Yamashita, “A dual spectral projected gradient method for log-determinant semidefinite problems”, Computational Optimization and Applications, 76(1) 33-68 (2020).
  • H. Komeiji, S. Kim, M. Yamashita, ”Sums of squares representation of polynomials by alternating directional augmented Lagrangian methods with fast convergence”, Computational Optimization and Applications, 74, 317-344 (2019).
Graduate Students
  • Ji-Young Yoo Master's student
    Research Area: Exact solution methods for Polynomial Optimization Problems
  • Min-Jun Kim Master's student
    Research Area: Numerical methods for Quadratic Assignment Problems
  • Seo Young Hong Master's student
    Research Area: Effective methods for processing big data
  • Eunjoo Cho Master's student
    Research Area: Linear programming algorithms