These are additional SDP testproblems in SeDuMi and sparse SDPA format BZIP2 for Windows is at: http://gnuwin32.sourceforge.net/packages/bzip2.htm Gset: http://www.stanford.edu/~yyye/yyye/Gset/ Rendl/Gruber: http://www-sci.uni-klu.ac.at/math-or/home/publications/input_ex1.m biggs: use GLOPTIPOLY to find global min of polynomial problem (see below) butcher: use GLOPTIPOLY for polynomial system (used but not solved in [5]) cancer: [4] below checker: [2] below chs_500: example from http://www.is.titech.ac.jp/~kojima/SparsePOP/ cnhil8: determining copositivity of the 8d checkerboard Hilbertmatrix h_ij = (-1)^(i+j-1)/(i+j-1) (util. SOSTOOLS) cnhil10: determining copositivity of the 10d checkerboard Hilbertmatrix cphil10: determining copositivity of the 10d Hilbert matrix ( util. SOSTOOLS) cphil12: determining copositivity of the 12d Hilbert matrix ( util. SOSTOOLS) diamond_patch: communicated by Jens Keuchel foot: [4] below G40mb: SDP relaxation of the minbisection problem for graph G40 from Gset G40mc: SDP relaxation of the max-cut problem for graph G40 from Gset G48mc: SDP relaxation of the max-cut problem for graph G48 from Gset G55mc: SDP relaxation of the max-cut problem for graph G55 from Gset G59mc: SDP relaxation of the max-cut problem for graph G59 from Gset hand: [3] below ice_2.0: [1] below inc_*: SDPs generated by incdemo of SDE (Semidefinite Embedding) code, [6] neu1: SDP generated by SOSTOOLS applied to bounding below p_neu1 neu1g: same as neu1 but with GLOPTIPOLY, relaxation order 5 neu2: SDP generated by SOSTOOLS applied to bounding below p_neu2 neu2g: same as neu2 but with GLOPTIPOLY, relaxation order 5 neu2c: same as neu2g but with constraints, see below neu3: SDP generated by SOSTOOLS applied to bounding below p_neu3 neu3g: same as neu3 but with GLOPTIPOLY nonc_500: example from http://www.is.titech.ac.jp/~kojima/SparsePOP/ p_auss2: [2] below prob*: due to size only the generating m-files are given, see [7] rabmo: use GLOPTIPOLY for polynomial system (used but not solved in [5]) r1_6_0: Rendl/Gruber example 1, n=600, alpha=0 reimer5: use GLOPTIPOLY for polynomial system (used but not solved in [5]) ros_500: example from http://www.is.titech.ac.jp/~kojima/SparsePOP/ rose13: SDP generated by GLOPTIPOLY applied to the 13-d Rosenbrock function rose15: SDP generated by SOSTOOLS applied to the 15-d Rosenbrock function sdmint3: SeDuMiInt104 demo control example, dimensions tripled sensor*: Yinyu Ye's sensor location examples swissroll: SDP generated by sde.m in SDE (Semidefinite Embedding) code, [6] taha1a: using GLOPTIPOLY to bound constrained polynomial problem, see below taha1b: using GLOPTIPOLY to bound constrained polynomial problem, see below tiger_texture: communicated by Jens Keuchel yalsdp: YALMIP SDP example with n=100 ------------------------------------------------------------------------------- NOTE: neu*, butcher, rabmo, reimer5, rose15 have free variables sdmint3 has quadratic cone constraints, cn*, cp* have c=0 the free variables were transformed into a difference of two nonneg. variables with a converter provided by Brian Borchers ------------------------------------------------------------------------------- p_neu1 = sum(k=1,5)(b_k - f_k)^2, f_k=sum(i=1,5)x_i^k, b=(5,5,5,5,5) p_neu2 = sum(k=1,5)(b_k - f_k)^2, f_k=sum(i=1,5)x_i^k, b=(10,20,40,80,160) p_neu3 = 6x_1^4 + 5x_2^6 + 4x_3^8 + 3x_4^10 + 2x_5^8 + x_6^6 ------------------------------------------------------------------------------- neu2c-constraints: 2*x1+x4-3*x5+x3-x2<=0, x1*x2*x3*x4*x5<=32, x1>=0, x1<=5, x1^5-x5^4+x2^3-x4^2+x3<=22, (x1-x2^2)^2+x3*x4^2*x5^2>=38, x2^2>=1, x2^3<=16, x1^10-x2^9-x3^9+(x4-x5)^8<=0, (x1^3*x4^2-x2*x3*x5^3)^2-4*x1*x3*(2*x5-x2-x4)<=0, x3>=x4, x4>=0, x5<=4 (solution still (2,2,2,2,2) as for neu2) ------------------------------------------------------------------------------- taha1a: min 3*Y1*Y4 + 2*Y1*Y2 + 5*Y4 + 2*Y2*Y3 + 3*Y2*Y3*Y5 s.t.: -1*Y1*Y4 - 1*Y1*Y2 + 1*Y4 + 2*Y2*Y3 - 1*Y2*Y3*Y5 <= 1 -7*Y1*Y4 + 3*Y4 - 4*Y2*Y3 - 3*Y2*Y3*Y5 <= -2 11*Y1*Y4 - 6*Y1*Y2 - 3*Y2*Y3 - 3*Y2*Y3*Y5 <= -1, 0<=Yi<=1 ------------------------------------------------------------------------------- taha1b: min 3*Y1*Y2*Y3*Y4*Y7 + 2*Y3*Y4*Y5*Y6 + 5*Y1*Y2*Y4*Y9*Y10 + 2*Y1*Y2*Y5*Y6*Y7 + 3*Y1*Y4*Y8*Y9*Y10 s.t.: -Y1*Y2*Y3*Y4*Y7-1*Y3*Y4*Y5*Y6 + Y1*Y2*Y4*Y9*Y10 + 2*Y1*Y2*Y5*Y6*Y7 - Y1*Y4*Y8*Y9*Y10 <= 1 -7*Y1*Y2*Y3*Y4*Y7+3*Y1*Y2*Y4*Y9*Y10-4*Y1*Y2*Y5*Y6*Y7 - 3*Y1*Y4*Y8*Y9*Y10 <= -2 11*Y1*Y2*Y3*Y4*Y7-6*Y3*Y4*Y5*Y6-3*Y1*Y2*Y5*Y6*Y7-3*Y1*Y4*Y8*Y9*Y10 <= -1 0<=Yi<=1 ------------------------------------------------------------------------------- biggs-problem: min 2.3*(x1+x4+x7+x10)+1.7*(x2+x5+x8+x11)+2.2*(x3+x6+x9+x12) +.0001*(x1^4+x4^4+x7^4+x10^4+x2^4+x5^4+x8^4+x11^4) +.00015*(x3^4+x6^4+x9^4+x12^4) s.t. 0<=x4-x1+7<=13, 0<=x7-x4+7<=13, 0<=x10-x7+7<=13, 0<=x5-x2+7<=14, 0<=x8-x5+7<=14, 0<=x11-x8+7<=13, 0<=x6-x3+7<=13, 0<=x9-x6+7<=13, 0<=x12-x9+7<=13, x1+x2+x3>=60, x4+x5+x6>=50, x7+x8+x9>=70, x10+x11+x12>=85, x1+x4+x7+x10>=76, 0<=x1<=21, 43<=x2<=57, 3<=x3<=16, 0<=x4<=90, 0<=x5<=120, 0<=x6<=60, 0<=x7<=90, 0<=x8<=120, 0<=x9<=60, 0<=x10<=90, 0<=x11<=120, 0<=x12<=60, ------------------------------------------------------------------------------- [1] J. Keuchel, C. Schnörr, C. Schellewald, D. Cremers: Binary Partitioning, Perceptual Grouping, and Restoration with Semidefinite Programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(11): 1364-1379, Nov. 2003. [2] J. Keuchel, C. Schellewald, D. Cremers, C. Schnörr, Convex Relaxations for Binary Image Partitioning and Perceptual Grouping, B. Radig, S. Florczyk (Eds.), Pattern Recognition, Lecture Notes in Computer Science, Vol. 2191, Springer, Berlin, 353-360, 2001. [3] J. Keuchel, C. Schnörr: Efficient Graph Cuts for Unsupervised Image Segmentation using Probabilistic Sampling and SVD-based Approximation, 3rd International Workshop on Statistical and Computational Theories of Vision, Nice (France), October 12, 2003. [4] M. Heiler, J. Keuchel: Work in progress. [5] D. Henrion, J. B. Lasserre. Solving global Optimization Problems over Polynomials with GloptiPoly 2.1. in C. Bliek, C. Jermann, A. Neumaier (Editors). Global Optimization and Constraint Satisfaction. Lecture Notes on Computer Science, Volume 2861, pp. 43-58, Springer Verlag, Berlin, 2003. [6] http://www.seas.upenn.edu/~kilianw/sde/datasets.htm [7] using genhardSDP.m from http://orion.math.uwaterloo.ca/~hwolkowicz/henry/software/SDP.shtml ------------------------------------------------------------------------------- More cases to be added. Hans Mittelmann February 2006