-->|Front Page |Publications|

B-486: N. Ito, S. Kim, M. Kojima, A. Takeda and K. Toh, " Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems", July 2017. pdf file.

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 __P__olyhedral __Ho__motopy Continuation __M__ethod
". 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 __P__olyhedral __Ho__motopy Continuation __M__ethod",
December 2002, revised Janurary 2003. *Computing *Vol.73 55-77 (2004).*
*

B-384: M. Yamashita, K. Fujisawa and M. Kojima, ``SDPARA : __S__emi__D__efinite__
P__rogramming __A__lgorithm PA__RA__llel 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 V*ol 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 |