Recent Research Reports (Revised July 2016)


-->|Front Page |Publications|

B-483: S. Kim, M. Kojima and K. Toh, "Doubly Nonnegative Relaxations for Quadratic and Polynomial Optimization Problems with Binary and Box Constraints", July 2016. pdf file.

B-482: N. Arima, S. Kim, M. Kojima and K. Toh, "A Robust Lagrangian-DNN Method for a Class of Quadratic Optimization Problems", February 2016. pdf file.

B-481: S. Kim and M. Kojima, "Binary Quadratic Optimization Problems That Are Difficult to Solve by Conic Relaxations", July 2015. pdf file.

B-476: N. Arima, S. Kim, M. Kojima and K. Toh, "Lagrangian-Conic Relaxations, Part II: Applications to Polynomial Optimization Problems", January 2014. pdf file.

B-475: N. Arima, S. Kim, M. Kojima and K. Toh, "Lagrangian-Conic Relaxations, Part I: A Unified Framework and Its Applications to Quadratic Optimization Problems", January 2014. pdf file.

B-472: S. Kim, M. Kojima and K. Toh, "A Lagrangian-DNN Relaxation: a Fast Method for Computing Tight Lower Bounds for a Class of Quadratic Optimization Problems ", October 2013. pdf file.

2013-4: S. Burer, S.Kim and M. Kojima, "Faster, but Weaker, Relaxations for Quadratically Constrained Quadratic Programs ", April, 2013, pdf file.

B-471: N. Arima, S. Kim and M. Kojima, "Extension of Completely Positive Cone Relaxation to Polynomial Optimization ", February 2013. pdf file.

B-470: S. Kim, M. Kojima and M. Yamashita, "Parallel Implementation of Successive Sparse SDP Relaxations for Large-Scale Euclidean Distance Geometry Problems ", November 2012. pdf file.

B-469: N. Arima, S. Kim and M. Kojima, "Simplified Copositive and Lagrangian Relaxations for Linearly Constrained Quadratic Optimization Problems in Continuous and Binary Variables ", October 2012. pdf file.

B-468: N. Arima, S. Kim and M. Kojima, "A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming ", September 2012. pdf file.

B-466: S. Kim and M. Kojima, "A Continuation Method for Large-sized Sensor Network Localization Problems", August 2011. pdf file.

B-462: S. Kim and M. Kojima, "Exploiting Sparsity in SDP Relaxation of Polynomial Optimization Problems", May 2010. pdf file.

B-459: M. Kojima and M. Yamashita, "Enclosing Ellipsoids and Elliptic Cylinders of Semialgebraic Sets and Their Application to Error Bounds in Polynomial Optimization", November 2009. pdf file.

B-457: S. Kim, M. Kojima H. Waki and M. Yamashita, "SFSDP: a Sparse Version of Full Semidefinite Programming Relaxation for Sensor Network Localization Problems ", July 2009. pdf file.

B-455: M. Mevissen and M. Kojima, "SDP Relaxations for Quadratic Optimization Problems Derived from Polynomial Optimization Problems", April 2009. Asia-Pacific Journal of Operational Research Vol 27 (1) 15-38 (2010).

B-453: K. Fujisawa, S. Kim, M. Kojima, Y. Okamoto and M. Yamashita, "User's Manual for SparseCoLO: Conversion Methods for SPARSE COnic-form Linear Optimization Problems", February 2009. pdf file. MATLAB Software Package SparseCoLO.

B-452: S. Kim, M. Kojima, M. Mevissen and M. Yamashita, "Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion", January 2009. pdf file. To appear in Mathematical Programming.

B-449: S. Kim, M. Kojima and H. Waki, "User manual for SFSDP: a Sparse Version of Full SemiDefinite Programming relaxation for sensor network localization problem", August 2008. pdf file. MATLAB software package SFSDP.

B-448: Katsuki Fujisawa, Mituhiro Fukuda, Kazuhiro Kobayashi, Masakazu Kojima, Kazuhide Nakata, Maho Nakata and Makoto Yamashita, "SDPA (SemiDefinite Programming Algorithm) User's Manual --- Version 7.0.5", February 2008. pdf file.

B-447: S. Kim, M. Kojima and H. Waki, "Exploiting Sparsity in SDP Relaxation for Sensor Network Localization", January 2008. Revised October 2008. SIAM Journal of Optimization Vol.20 (1) 192-215 (2009). MATLAB software package SFSDP.

B-445: K. Murota, Y. Kanno, M. Kojima and S. Kojima, " A numerical algorithm for block-diagonal decomposition of matrix *-algebras, Part I: proposed approach and application to semidefinite programming", Japan Journal of Industrial and Applied Mathematics Vol.27 125-160 (2010).

B-444: S. Kim and M. Kojima, "Solving polynomial least squares problems via semidefinite programming relaxations", August 2007. Journal of Global Optimization VOL.46 (1) 1-23 (2010).

B-442: M. Mevissen, M. Kojima, J. Nie and N. Takayama, "Solving partial differential equations via sparse SDP relaxations", Pacific Journal of Optimization Vol. 4 (2) 213 - 241(2008). pdf file.

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

B-438: K. Suzuki, N. Miyoshi and M. Kojima, "A Numerical Method for the Survival Probability of Diffusion Processes Using Semidefinite Programming", January 2007 (in Japanese). Transactions of the Operations Research Society of Japan Vol.51 25-43 (2008). pdf file.

B-437: C. Vo, M. Muramatsu and M. Kojima, " Equality Based Contraction of Semidefinite Programming Relaxations in Polynomial Optimization ", December 2006. Journal of the Operations Research Society of Japan Vol. 51 (1) 111-125 (2008).

B-435: H. Waki, M. Muramatsu and M. Kojima, "Invariance under Affine Transformation in Semidefinite Programming Relaxation for Polynomial Optimization Problems ", October 2006. Pacific Journal of Optimization Vol 5 (2) 297-312 (2009). pdf file.

B-434: K. Kobayashi, S. Kim and M. Kojima, "Correlative Sparsity in Primal-Dual Interior-Point Methods for LP, SDP and SOCP", Applied Mathematics and Optimization Vol 58 (1) 69-88. pdf file.

B-433: M. Kojima, "Efficient Evaluation of Polynomials and Their Partial Derivatives in Homotopy Continuation Methods", August 2006. Revised July 2007. Journal of the Operations Research Society of Japan Vol 51 (1) 29-54 (2008).

B-428: S. Kim, M. Kojima and Ph.�`L.�`Toint, " Recognizing Underlying Sparsity in Optimization ", May 2006. Mathematical Programming Vol19 (2) 273-303 (2009). pdf file.

B-422: T.T. Mizutani, A. Takeda and M. Kojima, " Dynamic Enumeration of All Mixed Cells ", Discrete and Computational Geometry Vol. 37 (3) 351-367 (2007).

B-421: M. Kojima and M. Muramatsu, " A Note on Sparse SOS and SDP Relaxations for Polynomial Optimization Problems over Symmetric Cones ", Janurary 2006. Revised February 2007. Computational Optimization and Applications Vol 42 (1) 31-41 (2009). pdf file.

B-419: T. Gunji, S. Kim, K. Fujisawa and M. Kojima, "PHoMpara -- Parallel Implementation of the Polyhedral Homotopy Continuation Method ". October 2005. Revised April 2006. Computing Vol. 77 (4) 387-411 (2006). pdf file.

B-416: K. Kobayashi, K. Nakata and M. Kojima, "A Conversion of an SDP Having Free Variables into the Standard Form SDP" June 2005. Revised April 2006, Computational Optimization and Applications Vol. 36 289-307 (2007).

B-415: M. Yamashita, K. Fujisawa, M. Fukuda, M. Kojima and K. Nakata, "Parallel Primal-dual Interior-Point Methods for SemiDefinite Programs", March 2005. pdf file.

B-414: H. Waki, S. Kim, M. Kojima and M. Muramatsu, "SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems", March 2005. Revised August 2007. ACM Transactions on Mathematical Software Vol 35 (2) 15 (2008).

B-411: H. Waki, S. Kim, M. Kojima and M. Muramatsu, "Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity", October 2004. Revised September 2005. SIAM Journal on Optimization Vol.17 (1) 218-242 (2006).

B-409: K. Fujisawa, M. Fukuda, M. Kojima, K. Nakata and M. Yamashita, "SDPA-C (SemiDefinite Programming Algorithm -- Completion method) User's Manual --- Version 6.10", August 2004. ps file, ps.gz file, pdf file.

B-406: M. Kojima and M. Muramatsu, "An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones ", April 2004. Revised April 2006, Mathematical Programming Vol. 110 (2) 315-336 (2007).

B-405: C. Vo, A. Takeda and M. Kojima, "A Multilevel Parallelized Brancd and Bound Hybrid Algorithm for Quadratic Optimization", March 2004. IPSJ Transactions on Advanced Computing Systems Vol.45, No.SIG 6(ACS 6) 186-196 (2004).

B-400: K. Fujisawa, M. Kojima, A. Takeda and M. Yamashita, "Solving Large Scale Optimization Problems via Grid and Cluster Computing", December 2003, Journal of Operations Research Society of Japan Vol.47 (4) 265-274 (2004).

B-398: K.Nakata, M.Yamashita, K.Fujisawa, M.Kojima, "A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion", November 2003. Revised July 2005. Parallel Computing Vol.32 24-43 (2006). pdf file.

B-397: M. Kojima, "Sums of Squares Relaxations of Polynomial Semidefinite Programs", November 2003. ps file, ps.gz file, pdf file.

B-396: K. Fujisawa, M. Kojima, A. Takeda and M. Yamashita, "High Performance Grid and Cluster Computing for Some Optimization Problems", October 2003. ps file, ps.gz file, pdf file. Proceedings of SAINT 2004 Workshops, 612-615 (Tokyo, Japan, Jan. 26-30, 2004).

B-395: S. Kim, M. Kojima and H. Waki, ``Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems'', September 2003. Revised July 2004. To appear in SIAM Journal on Optimization. pdf file

B-391: M. Kojima, S. Kim and H. Waki, ``Sparsity in Sums of Squares of Polynomials'', June 2003, Revised June 2004. Mathematical Programming Vol.103 (1) 45-62.

B-390: S. Kim and M. Kojima, ``Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods'', March 2003. Revised February 2004.Computing Vol. 73 (4) 329-348 (2004).

B-386: T. Gunji, S. Kim, M. Kojima, A. Takeda, K. Fujisawa and T. Mizutani, ``PHoM -- a Polyhedral Homotopy Continuation Method", December 2002, revised Janurary 2003. Computing Vol.73 55-77 (2004).

B-384: M. Yamashita, K. Fujisawa and M. Kojima, ``SDPARA : SemiDefinite Programming Algorithm PARAllel Version'', October 2002. ps file, ps.gz file, pdf file. Parallel Computing Vol.29 (8) 1053-1067 (2003).

B-383: M. Yamashita, K. Fujisawa and M. Kojima, ``Implementation and Evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0)'', September 2002, Optimization Methods and Software Vol.18 (4) 491-505 (2003).

B-381: S. Kim, M. Kojima and M. Yamashita, ``Second Order Cone Programming Relaxation of a Positive Semidefinite Constraint'', July 2002. Optimization Methods and Software Vol.18 (5) 535-541 (2003). ps file, ps.gz file, pdf file.

B-380: M. Kojima, S. Kim and H. Waki, ``A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones'', April 2002. Revised June 2002. Journal of Operations Research Society of Japan Vol.46 (2) 125-144 (2003).

B-378: S. Kim and M. Kojima, ``CMPSc: A Continuation Method for Polynomial Systems (C++ version)'' ps file, ps.gz file, pdf file, March 2002. Revised April 2002. Gzipped tarred files of the entire CMPSc system.

B-376: S. Kim and M. Kojima, ``CMPSm : A Continuation Method for Polynomial Systems (MATLAB version)'', January 2002. Revised April 2002. Mathematical Software, ICMS2002 Beijing, China, August 17-19 (Arjeh M Cohen, Xiao-Shan Gao and Nobuki Takakayama, Editors), World Scientific, Singapore, 2002. Gzipped tarred files of the entire CMPSm system.

B-375: S. Kim and M. Kojima, ``Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations,'' January 2002. . Revised February 2003. Computational Optimization and Applications Vol.26 (2) 143-154 (2003).

B-373: Y. Dai, S. Kim and M. Kojima, ``Computing All Nonsingular Solutions of Cyclic-n Polynomial Using Polyhedral Homotopy Continuation Methods'', September 2001. Revised May 2002. Journal of Computational and Applied Mathematics Vol.152, No.1-2, 83-97 (2003). Solution Information on Some Polynomial Systems.

B-370: A. Takeda, K. Fujisawa, Y. Fukaya and M. Kojima, ``Parallel Implementation of Successive Convex Relaxation Methods for Quadratic Optimization Problems'', Journal of Global Optimization, Vol.24, No.2, 237-260.

B-369: M. Fukuda, M. Kojima and M. Shida, ``Lagrangian Dual Interior-Point Methods for Semidefinite Programs'' , March 2001. Revised October 2001. , SIAM Journal on Optimization Vol 12, No.4, 1007-1031 (2002).

B-368: Nakata, K. Fujisawa, M. Fukuda, M. Kojima and K. Murota, ``Exploiting Sparsity in Semidefinite Programming via Matrix Completion II: Implementation and Numerical Results'', Mathematical Programming Vol.95 303-327 (2003).

B-365: M. Fukuda and M. Kojima, ``Interior-Point Methods for Lagrangian Duals of Semidefinite Programs'' , December 2000.

B-364: A. Takeda, M. Kojima and K. Fujisawa, ``Enumeration of All Solutions of a Combinatorial Linear Inequality System Arising from the Polyhedral Homotopy Continuation Method'', Journal of the Operations Research Society of Japan Vol.45, No.1, 64-82 (2002).

B-363: S. Kim and M. Kojima, ``Second Order Cone Programming Relaxation of Nonconvex Quadratic Optimization Problems'', Optimization Methods and Software Vol .15, No.3-4 , 201-224 (2001).

B-359: K. Fujisawa, Y. Futakata, M. Kojima, S. Matsuyama, S. Nakamura, K. Nakata and M. Yamashita, ``SDPA-M (SemiDefinite Programming Algorithm in MATLAB) User's Manual Version 2.00'' , January 2000. Revised June 2003

B-358: M. Fukuda, M. Kojima, K. Murota and K. Nakata, ``Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework'', December 1999. Revised May 2000. SIAM Journal on Optimization Vol 11, No.3, 647-674 (2001).

B-356: M. Kojima and L. Tuncel, ``Some Fundamental Properties of Successive Convex Relaxation Methods on LCP and Related Problems'', October 1999. Revised May 2001, Journal of Global Optimization Vol.24, 333-348 (2002).

B-354: M. Kojima and L. Tuncel, ``On the Finite Convergence of Successive SDP Relaxation Methods'' , August 1999. Revised August 2001. European Journal of Operations Research Vol.143, No.2, 325-341 (2002).

B-352: A. Takeda and M. Kojima, ``Successive Convex Relaxation Apporach to Bilevel Quadratic Optimization Problems'', August 1999. Applications and Algorithms of Complementarity (M. C. Ferris, O. L. Mangasarian and J.-S. Pang, Editors), Kluwer Academic Publishers, 2000, pp.317-340.

B-351: M. Fukuda and M. Kojima, ``Branch-and-Cut Algorithms for the Bilinear Matrix Inequality Eignevalue Problem'', April 1999. Revised January 2000. Computational Optimization and Applications Vol.19, No.1, 79-105 (2001).

B-350: M. Kojima and A. Takeda, ``Complexity Analysis of Conceptual Successive Convex Relaxation Methods for Nonconvex Sets'', April 1999. Revised July 2000. To applear in Mathematics of Operations Research.

B-349: M. Kojima, ``Introduction to Mathematical Programming from the Viewpoint of Interior-Point Methods'' (in Japanese), March 1999.

B-348: M. Kojima, T. Matsumoto, and M. Shida ``Moderate Nonconvexity = Convexity + Quadratic Concavity'' , March 1999, Revised April 1999.

B-347: A.Takeda, Y. Dai, M. Fukuda, and M. Kojima, ``Towards Implemenations of Successive Convex Relaxation Methods for Nonconvex Quadratic Optimization Problems'', March 1999. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems (P. M. Pardalos, Editor), Kluwer Academic Publisher, 2000, pp.489-510.

B-342: M. Kojima, ``Semidefinite Programming Relaxation and Global Optimization'' (in Japanese), July 1998.

B-341: M. Kojima and L. Tuncel, ``Discretization and Localization in Successive Convex Relaxation for Nonconvex Quadratic Optimization Problems,''July 1998. Revised May 2000. Mathematical Programming Vol.89, No.1, 79-111 (2000).

B-340: M. Kojima and L. Tuncel, ``Monotonicity of Primal-Dual Interior-Point Algorithms for Semidefinite Programming Problems,'' May 1998, Optimization Methods and Software dedicated to the 65th birthday of Professor Masao Iri, Vol. 10, Number 2, 275-296 (December, 1998).

B-339: K. Nakata, K. Fujisawa and M. Kojima, ``Using the Conjugate Gradient Method in Interior-Point Methods for Semidefinite Programs'' (in Japanese), April 1998, in Proceedings of the Institute of Statistical Mathematics (Tokeisuuri ), Vol 46, No.2, 297-316 (December, 1998).

B-338: M. Kojima and L. Tuncel, ``Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets,'' March 1998. Revised June 1999. SIAM Journal on Optimization Vol.10, No. 3, 750-778 (2000).

B-331: M. Kojima, ``Semidefinite Programming and Its Applications to Combinatorial Optimization'' (in Japanese), September 1997.

B-330: K. Fujisawa, M. Fukuda, M. Kojima and K. Nakata, ``Numerical Evaluation of SDPA (SemiDefinite Programming Algorithm),'' High Performance Optimization, H.Frenk, K. Roos, T. Terlaky and S. Zhang eds., Kluwer Academic Press, 1999, pp.267-301.

B-327: M. Kojima, M. Shida and S. Shindoh, ``Search Directions in the SDP and the Monotone SDLCP: Generalization and Inexact Computation,'' March 1997, Mathematical Programming Vol 85, No.1, 51-80 (May, 1999).

B-324: K. Fujisawa, M. Kojima and K. Nakata, ``Exploiting Sparsity in Primal-Dual Interior-Point Methods for Semidefinite Programming'', Mathematical Programming, Vol. 79, 235-253 (1997).

B-314: M. Kojima, ``Semidefinite Programming and Interior-Point Methods (in Japanese),'' April 1996, Bulletin of the Japan Society for Industrial and Applied Mathematics, Vol. 6 (1996) pp.16-25.


B-313: M. Kojima, M. Shida and S. Shindoh, ``A Note on Nesterov-Todd and Kojima-Shindoh-Hara Search Directions in Semidefinite Programming,'' April 1996, Optimization Methods and Software Vol.11&12, 47-52 (December, 1999).

B-312: M. Shida and S. Shindoh, ``Monotone Semidefinite Complementarity Problems,'' April 1996.

B-311: M. Kojima, M. Shida and S. Shindoh, ``A Predictor-Corrector Interior-Point Algorithm for the Semidefinite Linear Complementarity Problem Using the Alizadeh-Haeberly-Overton Search Direction'', SIAM Journal on Optimization Vol.9, No.2, 444-465.

B-310 M. Shida, S. Shindoh and M. Kojima, ``Existence of Search Direction in Interior-Point Algorithms for the SDP and the Monotone SDLCP,'' January 1996. SIAM Journal on Optimization, Vol.8, 387-396 (1998).

B-308: K. Fujisawa, M. Kojima, K. Nakata and M. Yamashita, ``SDPA (Semidefinite Programming Algorithm) User's Manual --- Version 6.0, '' December 1995, Revised July 2002. ps file, ps.gz file, pdf file

B-306: M. Kojima, M. Shida and S. Shindoh, ``Local Convergence of Predictor-Corrector Infeasible-Interior-Point Algorithms for SDPs and SDLCPs,'' December 1995, Revised October 1996. Mathematical Programming, Vol. 80, 129-161 (1998).
Appendix: Mathematica Program Used in Example 3.3

B-303: M. Shida, S. Shindoh and M. Kojima, ``Centers of Monotone Generalized Complementarity Problems'',Mathematics of Operations Research, Vol. 22, 969-976 (1997)

B-298: T. Fujie and M. Kojima, ``Semidefinite Programming Relaxation for Nonconvex Quadratic Programs'', Journal of Global Optimization, Vol. 10 (1997) pp.367-380.

B-296: M. Kojima, M. Shida and S. Shindoh, ``Reduction of Monotone Linear Complementarity Problems over Cones to Linear Programs over Cones'' , Acta Mathematica Vietnamica, Vol. 22, 147-157 (1997).

B-293: M. Kojima, ``A Primitive Interior Point Algorithm for Semidefinite Programs in Mathematica,'' December 1994.

B-290: M. Kojima, S. Kojima and S. Hara, ``Linear Algebra for Semidefinite Programming,'' RIMS Kokyuroku 1004 (1997) pp.1- 23, Research Institute of Mathematical Sciences, Kyoto University, Kyoto, Japan.

B-282: M. Kojima, S. Shindoh and S. Hara, ``Interior-Point Methods for the Monotone Linear Complementarity Problem in Symmetric Matrices,'' SIAM Journal on Optimization, Vol.7, 86-125 (1997).


-->|Front Page |Publications |