SERIES B: Operations Research
Contents
1. You can find the latest news at about the SDPA at the index html file A4 How to Build A4 1 Fedora 8 and 9 To build the SDPA GMP type the following bash su Password yum update glibc glibc common yum install gcc gcc c yum install gmp gmp devel exit tar xv z sdpa gmp 7 1 1 src 2008xxxx tar gz cd sdpa gmp 7 1 1 configure make 9 9 93 PH dt dk dt A4 2 MacOSX If you use Leopard Download and install the Xcode 3 from Apple Developer Connection http developer apple com and installit Note that we support only the Xcode 3 on Leopard We do not support Leopard with Xcode 2 5 If you use Tiger Download and install either the Xcode 2 4 1 or the Xcode 2 5 from Apple Developer Connec tion First download GMP from http gmplib org install GMP by You may change Users maho gmp to appropriate one bash tar xvfz gmp 4 2 2 tar gz cd gmp 4 2 2 configure enable cxx prefix Users maho gmp make install H A A NN Y FH make check Then build the SDPA GMP by bash tar xvfz sdpa gmp 7 1 1 src 2008xxxx tar gz cd sdpa gmp 7 1 1 31 CXXFLAGS I Users maho gmp include export CXXFLAGS CPPFLAGS I Users maho gmp include export CPPFLAGS CFLAGS I Users maho gmp include export CFLAGS LDFLAGS L Users maho gmp lib export LDFLAGS configure make A5 How to Install You will find the sdpa_gmp executable binary file at this point and you c2. L home nakata gotoblas lib lgoto with lapack L home nakata gotoblas lib lgoto llapack make You can set the number of threads uses via setting the OMP NUM THREADS environment variable before running the SDPA like following In this case two cores will be used for BLAS operations You need a multi core CPU to accelerate BLAS operations export OMP NUM THREADS 2 sdpa ds examplei dat s o examplel out 1 6 4 Linking Against Intel Math Kernel Library Install Intel Math Kernel Library and assume that the library is installed at opt intel mk1 10 0 3 020 lib em64t Reconfigure and rebuild the SDPA like following make clean configure with blas L opt intel mk1 10 0 3 020 1ib em64t 1mk1_em64t lguide with lapack L opt intel mk1 10 0 3 020 1ib em64t lmkl lapack lmkl sequential 1mkl core make You can set the number of threads uses via setting the DOMP NUM THREADS environment variable before running the SDPA like following In this case four cores will be used for BLAS operations You need a multi core CPU to accelerate BLAS operations export OMP NUM THREADS 4 sdpa ds examplei dat s o examplel out 1 7 Performance Tuning Compiler Options We also recommend adding some optimized flags to the compilers Our recommendations are e 02 funroll all loops default e static 03 funroll all loops march nocona msse3 mfpmath sse on Core2 The above default options are sufficien
3. examplel dat described in Section 4 1 with the sparse input data file examplel dat s above The first 5 lines of the file examplel dat s are the same as those of the file examplel dat Following them each line of the file examplel dat s describes a single element of a constant matrix F the 6th line 0 1 1 1 11 means that the 1 1 th element of the 1st block of the matrix Fo is 11 and the 11th line 3 1 1 2 8 means that the 1 2 th element of the 1st block of the matrix F3 is 8 23 In general the structure of a sparse input data file is as follows Title and Comments m the number of the primal variables x s nBLOCK the number of blocks bLOCKsTRUCT the block structure vector c ky by di ji vi ka ba i2 ja v2 kp bp tp Jp Up kq bq tq Ja vq Here kp 0 1 m bp 1 2 n BLOCK 1 lt ip jp and vy ER Each line kp bp ip jp Up means that the value of the ip jp th element of the b th block of the constant matrix F is vp If the bpth block is an x symmetric non diagonal matrix then ip jp must satisfy 1 lt ip lt jp lt 4 hence only nonzero elements in the upper triangular part of the b th block are described in the file If the b th block is an l x diagonal matrix then ip jp must satisfy 1 lt ip jp lt Ll 7 3 Sparse Initial Point File We show below the file examplel ini s which contains an initial point data of Example 1 i
4. t i 1 Hence we can reduce the above problem to the following standard form SDP m minimize 5 Citi i 1 m subject to X 5 Fizi Fo X gt O i 1 where Fo X nBlock 2 blockStruct n 2 Next we consider the case where inequality constraints are added to the dual standard form of SDP For example maximize FoeY subject to F e Y c F20 Y c9 F360 Y lt cz F4e Y lt c4 F56 Y gt cs YO In this case we add slack variables t3 4 t5 to each inequality constraint maximize Fye Y subject to FyeY c F eY c2 Fe Y t3 c3 FAY t4 C4 F5 X t 065 Y O ts t4 ts gt 0 26 Thus we can reduce the above problem to the following standard form SDP maximize Foe Y m subject to F s Y C1 Fe Y C2 7 F30e Y c3 Fe Y cCa F o Y c5 Y O where Y Fo Fy v t3 0 an 0 Y ta Fo 0 Fi 0 ts 0 0 F Fs F 0 1 0 F 0 F3 0 F 4 1 0 0 0 Fs F j 0 gt nBlock 2 blockStruct n 3 8 2 Norm Minimization Problem Let G R 0 i p The norm minimization problem is defined as p minimize Joos Gizi i 1 subject to z R 1 i p Here G denotes the 2 norm of G i e Bn Gu the square root of the maximum eigenvalue of G7 G ul 1 Gl We can reduce this problem to an SDP minimize Tp 1 O GT I O o G mbi 1 0 subject to x G O Ja O I Jet Gy O 0 Thus if we take E
5. 0 60 65 241 0 0 0 0 00 00 00 00 00 45 0 0 00 00 00 0000 00 3 5 65 5 4 00 00 00 00 0 0 5 4 66 00 00 00 00 0 0 00 0 0 6 7 7 2 3 6 0 0 0 0 F 00 0 0 72 7 3 3 0 00 0 0 00 0 0 3 6 3 0 14 0 0 0 0 00 00 00 00 00 61 0 0 00 00 00 00 00 00 1 5 As shown in this example the SDPA handles block diagonal matrices The data of this example is contained in the file example2 dat see Section 4 2 3 Files Necessary to Execute the SDPA We need the following files to execute the SDPA e sdpa The executable binary for solving an SDP e input data file Any file name with the postfix dat or dat s are accepted for example problem dat and example dat s are legitimate names for input files The SDPA distinguishes a dense input data file with the postfix dat from a sparse input data file with the postfix dat s See Sections 4 and 7 2 for details e param sdpa The file describing the parameters used in the sdpa See Section 5 for details The name is fixed to param sdpa output file Any file name excepting sdpa and param sdpa For example problem 1 and example out are legitimate names for output files See Section 6 for more details The files examplel dat see Section 4 1 and example2 dat see Section 4 2 contain the input date of Example 1 and Example 2 respectively which we have stated in the pr
6. 01 4 19e 01 30 2 2e 21 3 3e 70 5 9e 72 4 19e 01 4 19e 01 31 2 2e 22 3 3e 70 5 9e 72 4 19e 01 4 19e 01 32 2 2e 23 3 6e 70 3 0e 70 4 19e 01 4 19e 01 33 2 2e 24 3 9e 70 1 2e 71 4 19e 01 4 19e 01 34 2 2e 25 4 1e 70 1 2e 71 4 19e 01 4 19e 01 35 2 2e 26 4 1e 70 1 2e 71 4 19e 01 4 19e 01 36 2 2e 27 4 4e 70 1 2e 71 4 19e 01 4 19e 01 37 2 2e 28 4 5e 70 1 2e 71 4 19e 01 4 19e 01 38 2 2e 29 4 6e 70 4 9e 70 4 19e 01 4 19e 01 2 1 w o 2e 30 4 8e 70 1 1e 71 4 19e 01 4 19e 01 phase value pdOPT Iteration 39 mu 2 2051719065342495e 30 relative gap 1 0525880222120523e 31 gap 4 4103438130684991e 30 33 alphaP HG LB oL LB LB HB p p HB B HB LB HB B RRA HP HR BP HP P HP H P P P P dH P HP Q0 Q P 0 q Q Qo PR 0e 00 0e 01 1e 01 9e 00 4e 00 Te 01 9e 01 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 0e 00 alphaD RRORRRRRORRORRORORRRORRRRRORRRPRORO0OoROoo0o0o 0e 01 0e 01 1e 01 6e 01 0e 00 Te 01 9e 01 0e 00 0e 01 0e 00 0e 00 0e 00 0e 00 0e 01 0e 00 0e 00 0e 00 0e 00 0e 00 0e 01 0e 00 0e 00 0e 00 0e 01 0e 00 0e 01 0e 00 0e 00 0e 01 0e 00 0e 00 0e 01 0e 00 0e 00 0e 00 0e 00 0e 00 0e 01 0e 00 0e 00 beta ererrr
7. 1 375 1 375 1 0 In general the initial point file can have any name with the postfix ini for example example ini is a legitimate initial point file name An initial point file contains the data zl x y in this order where the description for the m dimensional vector must follow the same format as the constant vector c see Section 4 7 and the description of X and Y the same format as the constraint matrix F see Section 4 8 7 2 Sparse Input Data File In Section 4 we have stated the dense data format for inputting the data m n c R and F S i 0 1 m When not only the constant matrices F S i 0 1 m are block diagonal but also each block is sparse the sparse data format described in this section gives us a compact description of the constant matrices A sparse input data file must have a name with the postfix dat s for example problem dat s and example dat s are legitimate names for sparse input data files The SDPA distinguishes a sparse input data file with the postfix dat s from a dense input data file with the postfix dat We show below the file examplel dat s which contains the data of Example 1 Section 2 2 in the sparse data format Example 1 mDim 3 nBLOCK 1 12 3 mDIM 1 nBLOCK 2 bLOCKsTRUCT 48 8 20 0111 11 012223 1111 10 11124 2122 8 3112 8 3122 2 Compare the dense input data file
8. 24 22 GotoBLAS 1 24 1 33 91 36 40 23 15 24 53 18 109 72 19 GotoBLAS 1 24 2 24 52 35 18 37 15 16 11 18 71 53 19 CPU Intel Core 2 E8200 2 66GHz x 1 CPU 2 cores OS CentOS Ver 5 1 64bit Compiler Quantum Chemistry Intel C C4 4 amp Fortran 10 1 012 Structural Optimization g1717 dat s Combinatorial Optimization 1 Combinatorial Optimization 2 mcp1000 10 dat s theta5 dat s CH 2Pi STO6G pqg dat s Supply a command line to link against your BLAS e g with blas L home nakata gotoblas lib lgoto e with lapack Supply a command line to link against your LAPACK e g with lapack L home nakata gotoblas lib lgoto llapack 1 6 2 Linking Against ATLAS Install ATLAS and assume that the ATLAS libraries are installed at home nakata atlas lib If there exists liblapack a at home nakata atlas lib we recommend rename or remove it Then reconfigure and rebuild the SDPA like following make clean configure with blas L home nakata atlas lib lptf77blas lptcblas latlas make The number of cores uses is determined at the build process and you need a multi core CPU to accelerate BLAS operations 1 6 3 Linking Against GotoBLAS Install GotoBLAS and assume that the GotoBLAS libraries are installed at home nakata gotoblas lib Reconfigure and rebuild the SDPA like following make clean configure with blas
9. a X Y a feasible solution or an optimal solution resp of the SDP We assume Condition 1 1 F 1 2 m CS is linearly independent If a given SDP does not satisfy this assumption the SDPA can abnormally stop due to some numerical instability but it does not mean that it will necessarily happen If we deal with a different primal dual pair P and D of the form P minimize Age X subject to AjeX b i 1 2 m S gt X gt 0 SDP D maximize y biyi i 1 subject to 3 Ad Z o S gt Z gt 0 i 1 we can easily transform it into the standard form SDP as follows 4 E Ai 0 m Y F i 0 m bi i m gt Ci i 1 m X Y y amp Z X Ne D 2 2 Example 1 P minimize 48y4 8y2 20y3 i 10 4 0 0 0 8 11 0 subject to x 4 Juro 3 mt s 3 0 n X gt O err 11 0 D maximize 0 23 eY 10 4 0 0 subject to 4 o ers t a Y 0 8 28 7 Y 20 Y 0 Here 48 m 3 n 2 8 Pa A n 20 10 4 0 0 0 8 n 0 o 2 P 8 2 The data of this problem is contained in the file examplel dat see Section 4 1 2 3 Example 2 14 32 00 00 00 00 0 0 32 28 00 00 00 00 0 0 0 0 0 0 15 12 2 1 00 0 0 Fo 0 0 0 0 12 16 38 00 0 0 00 0 0 21 3 8 15 0 0 0 0 00 00 00 00 0018 0 0 00 00 00 0 0 00 00 4 0 05 5 2 00 0000 00 0 0 5 2 5 3 00 0000 00 0 0 00 00 78 24 60 00 0 0 Fi 00 0 0 24 42 65 00 00 00 0
10. a ee NUM ee P 1 Build and Installation This section describes how to build and install the SDPA Usually the SDPA is distributed as source codes therefore users must build it by themselves We have done build and installation tests on Fedora 8 9 1386 x86 64 ppc Red Hat Enterprise Linux CentOS 4 5 i386 x86_64 Ubuntu 7 10 1386 x86 64 Vine Linux 4 2 1386 MacOSX Leopard Tiger Intel PowerPC and FreeBSD 6 7 You may also possibly build on other UNIX like platforms and the Windows cygwin environment For better performance the SDPA should link against optimized Basic Linear Algebra Sub programs BLAS and Linear Algebra PACKage LAPACK Please refer to the Section 1 6 for more details Alternatively you can also use our online solver or check for pre build binary packages at the SDPA homepage see Section 1 2 1 1 Prerequisites It is necessary to have at least the following programs installed on your system except for the MacOSX e C C compiler e FORTRAN compiler e BLAS http www netlib org blas and LAPACK http www netlib org lapack For MacOSX Leopard Intel PowerPC you will need the Xcode 3 0 and you cannot build the SDPA on the Leopard with Xcode 2 5 For MacOSX Tiger Intel PowerPC you will need either the Xcode 2 4 1 or the Xcode 2 5 You can download the Xcode at Apple Developer Connection http developer apple com at free of charge In the following instructions we install C
11. aon FP A Ww wow NN WD o o o Qe Parameter File Output 6 1 Execution of the SDPA a 6 2 Output on the Display amp su ido cec ee o REOR a Sh ee ee RU 6 3 Output toa File s sa s saru aa ioe a a aa o9 3o S4 a OR KO E SUP n 6 4 Printing DIMACS Errors Roses Advanced Use of the SDPA Tel Initial Polito oko nune t o a Rod Rox E We demum RUE A Y 7 2 Sparse Input Data File a aaa aa 7 3 Sparse Initial Point File ls 7 4 Obtaining More Precision on the Approximate Solution 7 5 More on Parameter File leer Transformation to the Standard Form of SDP 8 1 Inequality Constraints 422 less 8 2 Norm Minimization Problem a 8 3 Linear Matrix Inequality LMI amp 2 42444 w bd Be EY PRP ed RD 8 4 SDP Relaxation of the Maximum Cut Problem 8 5 Choosing Between the Primal and Dual Standard Forms For the SDPA 6 2 1 Users SDPA GMP Al Build and Installation 2 les A2 Prerequisites 4 0244 ec aTa wa Bh ae GG X Gee A A AD wie wh ey e e A3 How to Obtain the Source Code 2 2e Ad Howto Build cos sacs fe bee ko 9o ee ES ea d AO ee es A4 1 Fedora8and9 o sa saca apaa aama aka naa a ae a a a a a AAD MacOSX me d daca e EUR o kom ala RA Ab How t Install 4 2 4 on ozono eo B ROS ER a Ea E a ws AG Test Rum es 2 abe ate l a a ae amp doe a aoe ab ae ee a a a oe ee Ar Parameters 2 42 eedem EUR ROW ee eR
12. dat s o example2 result p param sdpa example2 3 sdpa ds examplei dat s o example3 result pt 2 Let us solve the SDP examplel dat s sdpa ds examplei dat s o examplel out SDPA start at Fri Dec 7 18 30 56 2007 data is examplei dat s sparse parameter is param sdpa out is examplel out DENSE computations mu thetaP thetaD objP objD alphaP alphaD beta O 1 0e 04 1 0e 00 1 0e 00 0 00e 00 1 20e 03 1 0e 00 9 1e 01 2 00e 01 1 1 6e 03 0 0e 00 9 4e 02 8 39e 02 7 51e 01 2 3e 00 9 6e 01 2 00e 01 2 1 7e 02 2 3e 16 3 6e 03 1 96e 02 3 74e 01 1 3e 00 1 0e 00 2 00e 01 3 1 8e 01 2 3e 16 1 5e 17 6 84e 00 4 19e 01 9 9e 01 9 9e 01 1 00e 01 4 1 9e 00 2 6e 16 1 5e 17 3 81e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 5 1 9e 01 2 6e 16 3 0e 17 4 15e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 6 1 9e 02 2 5e 16 1 6e 15 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 7 1 9e 03 2 6e 16 2 2e 17 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 8 1 9e 04 2 5e 16 1 5e 17 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 9 1 9e 05 2 7e 16 7 5e 18 4 19e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 10 1 9e 06 2 6e 16 5 0e 16 4 19e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 phase value pdOPT Iteration 10 mu 1 9180668442024010e 06 relative gap 9 1554505577840628e 08 gap 3 8361336884048019e 06 digits 7 0383202783481345e 00 objValPrimal 4 1899996163866390e 01 objValDual 4 1899999999999999e 01 p feas error 3 2137639581876834e 14 d feas error 4 796163466380676
13. is advantageous to choose between the primal and the dual standard forms since one of the formulations is more natural has a smaller size it is faster to solve or it avoids numerical instability on the software Let us consider as an example the SDP relaxation of the maximum cut problem Section 8 4 We formulated this SDP as a dual standard form D where the problem size is m n nBLOCK bLOCKsTRUCT m We can also formulate mathematically the same problem as a primal standard form P too Let Hj an n x n symmetric matrix with i j th and j i th element s 1 and all others 0 Problem 3 is equivalent to TL TL n minimize 2 gt Cod gt Ci Vii i l i 1 j gt i n n subject to p H ijzij O 4 i 1 j i Ly gt 1 1 lt i lt nm ty Laren where xij 1 X X n i j n is a variable vector now This SDP is in primal standard form P and its size is m n n 4 1 2 nBLOCK 2 bLOCKsTRUCT n 2n which seems less advantageous than the dual standard from D 3 Also the problem 4 in primal standard form P does not have a strict feasible solution which many cause numerical instability In the case of n 100 a typical running time for the formulation 3 in dual standard form is 0 18s while for the for the formulation 4 in primal standard form is 201 3s In some cases however a slight increase in the size of the problem can be advantageous if the new formulation has more sparsity in its da
14. it neglects the comments The newly added precision sets the number of significant bits used in the SDPA GMP More precicely passing precision to mpf set default prec function of the GMP library When precision is X then log 9 X is the approximate significant digits in the floating point calculation At default precision is set to 200 then logio 22 60 205999133 Therefore we calculate approximately floating point numbers with sixty significant digits If we use double precision this is approximately sixteen Note that the GMP is not IEEE754 compliant References 1 E Anderson Z Bai C Bischof L S Blackford J Demmel J Dongarra J Du Croz A Greenbaum S Hammarling A McKenney and D Sorensen LAPACK Users Guide Third Edition Society for Industrial and Applied Mathematics 1999 Philadelphia PA 2 C Ashcraft D Pierce D K Wah and J Wu The reference manual for SPOOLES release 2 2 An object oriented software library for solving sparse linear systems of equations Boeing Shared Service Group Seattle WA January 1999 Available at http www netlib org linalg spooles spooles 2 2 html 3 S Boyd L El Ghaoui E Feron and V Balakrishnan Linear Matrix Inequalities in System and Control Theory Society for Industrial and Applied Mathematics 1994 Philadelphia PA 34 4 K Fujisawa M Kojima and K Nakata Exploiting sparsity in primal dual interior point methods
15. iteration d feas error max F eY c i 1 2 sma i This value is compared with epsilonDash Section 5 Even if the dual problem is feasible this value may not be 0 due to numerical errors 19 e total time This value indicates how much time the SDPA needs to execute all subroutines e main loop time This value indicates how much time the SDPA needs between the first iteration and the last iteration e file read time This value is how much time the SDPA needs to read from the input file and store the data in memory 6 3 Output to a File We show the content of the file example2 out on which the SDPA has written the computational results of Example 2 SDPA start at Fri Dec Y 18 32 10 2007 Example 2 xmDim 5 nBLOCK 3 2 3 2 data is example2 dat parameter is param sdpa out is example2 out mu thetaP thetaD objP objD alphaP alphaD beta O 1 0e 04 1 0e 00 1 0e 00 0 00e 00 1 44e 03 8 8e 01 6 6e 01 2 00e 01 1 3 3e 03 1 2e 01 3 4e 01 4 94e 02 2 84e 02 1 0e 00 8 2e 01 2 00e 01 2 9 0e 02 4 9e 16 6 2e 02 8 66e 02 2 60e 00 1 0e 00 1 0e 00 2 00e 01 3 1 4e 02 4 9e 16 8 8e 17 9 67e 02 9 12e 01 9 5e 01 5 4e 00 1 00e 01 4 1 8e 01 2 6e 16 8 6e 16 1 46e 02 2 36e 01 9 3e 01 1 5e 00 1 00e 01 5 2 7e 00 3 3e 16 4 2e 16 4 62e 01 2 74e 01 8 1e 01 1 4e 00 1 00e 01 6 5 7e 01 3 2e 16 2 0e 16 3 43e 01 3 03e 01 9 2e 01 9 3e 01 1 00e 01 7 9 5e 02 3 3e 16 4 1e 17 3 24e 01 3 18e 01 9 5e 01 9 6e 01 1 00e 01
16. s artos ee o AA 1 3 2 Ubuntu 7 10 Desktop 1980 x86 04 i zo d ORE X wx Rs 1 3 3 Vine Linux 4 2 i386 et AA A c CRUCE ds 1 3 4 MacOSX Leopard Intel PowerPC 1s sooo RR Rom 23 1 3 5 MacOSX Tiger Intel PowerPC llle 1 3 6 FreeBSD 6and 7 rr L4 Howtolnstal s 225 ko oo o ok o9 oho 9 p RARO eee a L5 West Rm 0 42864 ke Ross Y o EON EUR oe be A Ee e EUN vip E a e aTa 1 6 Performance Tuning Optimized BLAS and LAPACK 1 6 1 Configure Options lll Rss 1 6 2 Linking Against ATLAS 22e 1 6 3 Linking Against GotoBLAS ees 1 6 4 Linking Against Intel Math Kernel Library 1 7 Performance Tuning Compiler Options o 2 Semidefinite Program 2 1 Standard Form SDP and Its Dual 2e 2 2 Example la xerox Peck UR lis Uk Gk BA de cde A ao bd bees cR 23 Example 2 X 4 4 Roe phew hae eee Ro E ER AUR PUR he dU d eee es 3 Files Necessary to Execute the SDPA 4 Input Data File 4 1 examplel dat Input Data File of Examplel 4 2 example2 dat Input Data File of Example2 4 3 Format of the Input Data File 2e 4 4 Title and Comments 4 5 Number of the Primal Variables 22e 4 6 Number of Blocks and the Block Structure Vector 2 4 7 Constant Vector sora e a 2 2 ele hh osos 4 8 Constraint Matrices 2 22 424 sS ses lv v ne pp O0 N N N
17. we can formulate the problem as a nonconvex quadratic program 1 n n maximize ri 2 2 Wi 1 u u subjetto w2 1 1xixn Here each feasible solution u R of this problem corresponds to a cut L R with L i V u 1 and R i V uj 1 If we define W to be the n x n symmetric matrix with elements W Wi 1 4 j E and W 0 1 i n and the n x n symmetric matrix C S by C q diag We W where e R denotes the vector of ones and diag W e the diagonal matrix of the vector We R we can rewrite the quadratic program above as maximize zTCz subject to 22 1 1 lt 1i lt m If x R is a feasible solution of the latter quadratic program then the n x n symmetric and positive semidefinite matrix X whose i j th element X is given by Xij xiz satisfies Ce X zT Cx and Xi 1 1 lt i lt n This leads to the following semidefinite programming relaxation of the maximum cut problem maximize CexX 3 subject to EyeX 1 1 lt i lt n X O Here Ej denotes the n x n symmetric matrix with i i th element 1 and all others 0 28 8 5 Choosing Between the Primal and Dual Standard Forms Any SDP can be formulated as a primal standard form P or as a dual standard form D see Section 2 1 This does not mean that one is the dual of the other but simply that they are indeed two different formulations of the same problem each one having its dual counterpart Many times it
18. 0 24 is Up When sp 2 the line sp bp ip jp Up means that the value of the ip jp th element of the b th block of the constant matrix Y is vp If the bpth block is an x symmetric non diagonal matrix then ip jp must satisfy 1 lt ip lt jp lt hence only nonzero elements in the upper triangular part of the b th block are described in the file If the b th block is an x diagonal matrix then ip jp must satisfy 1 lt i jp lt 7 4 Obtaining More Precision on the Approximate Solution By default each element of the approximate optimal solution z X Y saved in the output file see Section 6 3 has a coefficient with 4 digits in scientific notation It is possible to increase its precision 1 Go to the subdirectory where SDPA source code is 2 Edit the file sdpa struct cpp line 25 define P FORMAT 8 3e to for instance define P FORMAT 8 5e 6 3 Type make clean 6 4 Type make to re compile SDPA Now each element of the approximate optimal solution will have a coefficient with 6 digits in scientific notation 7 5 More on Parameter File We may encounter some numerical difficult during the execution of the SDPA with the default parameter file param sdpa and or we may want to solve many easy SDPs with similar data more quickly In such a case we need to adjust some of the default parameters betaStar betaBar and gammaStar We present below two sets of tho
19. 3 2 Ubuntu 7 10 Desktop i1386 x86 64 To build the SDPA type the following bash sudo apt get install g patch sudo apt get install lapack3 lapack3 dev sudo apt get install atlas3 base atlas3 base dev tar xvfz sdpa 7 1 1 src 2008xxxx tar gz cd sdpa 7 1 1 configure make 1 3 3 Vine Linux 4 2 i386 bash su Modify etc apt sources list add the word extras between updates and nonfree from rpm vine http updates vinelinux org apt 4 2 ARCH main plus updates nonfree rpm src vine http updates vinelinux org apt 4 2 ARCH main plus updates nonfree to rpm vine http updates vinelinux org apt 4 2 ARCH main plus updates extras nonfree rpm src vine http updates vinelinux org apt 4 2 ARCH main plus updates extras nonfree Then type apt get update apt get install gcc g77 apt get install lapack lapack devel blas blas devel exit tar xvfz sdpa 7 1 1 src 2008xxxx tar gz cd sdpa 7 1 1 configure make AAA AH dk dt dt 1 3 4 MacOSX Leopard Intel PowerPC Download and install the Xcode 3 from Apple Developer Connection http developer apple com and install it Note that we support only the Xcode 3 on Leopard We do not support Leopard with Xcode 2 5 bash tar xvfz sdpa 7 1 1 src 2008xxxx tar gz cd sdpa 7 1 1 configure make 1 3 5 MacOSX Tiger Intel PowerPC Download and install either the Xcode 2 4 1 or the Xcode 2 5 from Appl
20. 3e 13 total time 0 010 main loop time 0 010000 total time 0 010000 file read time 0 000000 1 6 Performance Tuning Optimized BLAS and LAPACK We highly recommend to use optimized BLAS and LAPACK for better performance e g e Automatically Tuned Linear Algebra Software ATLAS http math atlas sourceforge net Note that in Section 1 3 we described how to use ATLAS which comes with Fedora Core 6 Fedora 7 8 and Ubuntu ATLAS optimizes itself while it is built and we recommend users to rebuild it on the target computers For convenience some pre build packages are available at https sourceforge net project showfiles php group id 23725 e GotoBLAS http www tacc utexas edu resources software e Intel Math Kernel Library MKL http www intel com cd software products asmo na eng 266858 htm Table 1 and 2 show how the SDPA 7 0 5 performs on several benchmark problems when replacing the BLAS and LAPACK libraries Typically the SDPA 7 0 5 with optimized BLAS and LAPACK seems much faster than the one with BLAS LAPACK 3 1 1 Furthermore we can receive benefits of multi thread computing when using SMP and or multi core machines 1 6 1 Configure Options There are some configure options you need to specify We specify at least two of them when using optimized BLAS and LAPACK Type configure help for more details e with blas Table 1 Numerical experiments SDPA 7 0 5 BLAS library time sec o
21. 4e 00 1 139e 00 1 1 514e 00 3 008e 00 2 264e 00 1 139e 00 2 264e 00 1 705e 00 4 087e 07 3 195e 08 main loop time 0 000000 total time 0 000000 file read time 0 000000 Now we explain the items that appeared above in the file example2 out e Lines with start These lines are comments in example2 dat e Data parameter initial output These are the file names we assigned for data parameter initial point and output respectively e Lines between Predictor time to Total time These lines display the profile data These information may help us to tune up the parameters but the details are rather complicate because the profile data seriously depends on internal algorithms e xVec Approximate optimal primal variable vector e xMat Approximate optimal primal variable matrix X e yMat Approximate optimal dual variable matrix Y 6 4 Printing DIMACS Errors To display the error measures defined at the 7th DIMACS Implementation Challenge on Semidefinite and Related Optimization Problems 6 1 Go to the subdirectory where SDPA source code is 2 Edit the file sdpa_io cpp line 22 21 define DIMACS_PRINT O to define DIMACS_PRINT 1 6 3 Type make clean 4 Type make to re compile SDPA The SDPA will output on the display and in the output file the following DIMACS errors at the last iteration e Errl The relative dual feasibi
22. 634663806763e 13 total time 0 010 main loop time 0 010000 total time 0 010000 file read time 0 000000 file read time 0 000000 17 mu The average complementarity X e Y n optimality measure When both 7 and D get feasible the relation mu I PS cix Foe d n i 1 primal objective function dual objective function n holds thetaP The SDPA starts with thetaP 0 0 if the initial point 2 X of the primal problem P is feasible and thetaP 1 0 otherwise hence it usually starts with thetaP 1 0 In the latter case the thetaP at the kth iteration is given by max X D Fick Fo pq 1255 5 thetaP max X 72 Fiz Folp a ee in The thetaP is theoretically monotone non increasing and when it gets 0 0 we obtain a primal feasible solution z X ky In the example above we obtained a primal feasible solution in the 1st iteration thetaD The SDPA starts with thetaD 0 0 if the initial point Y of the dual problem D is feasible and thetaD 1 0 otherwise hence it usually starts with thetaD 1 0 In the latter case the thetaD at the kth iteration is given by max F e Y c SL max F e Y c ded asm thetaD The thetaD is theoretically monotone non increasing and when it gets 0 0 we obtain a dual feasible solution Y In the example above we obtained a dual feasible solution in the 3rd iteration objP The primal objective fu
23. 8 1 3e 02 3 2e 16 1 9e 17 3 21e 01 3 20e 01 9 8e 01 1 0e 00 1 00e 01 9 1 5e 03 3 5e 16 2 8e 17 3 21e 01 3 21e 01 9 9e 01 1 0e 00 1 00e 01 10 1 5e 04 3 2e 16 1 7e 17 3 21e 01 3 21e 01 9 9e 01 1 0e 00 1 00e 01 11 1 5e 05 3 4e 16 3 7e 17 3 21e 01 3 21e 01 9 9e 01 1 0e 00 1 00e 01 12 1 5e 06 3 2e 16 4 3e 17 3 21e 01 3 21e 01 9 9e 01 1 0e 00 1 00e 01 13 1 5e 07 3 3e 16 3 1e 17 3 21e 01 3 21e 01 9 9e 01 1 0e 00 1 00e 01 phase value pdOPT Iteration 13 mu 1 5017857203245200e 07 relative gap 3 2787330975500860e 08 gap 1 0512500042271640e 06 digits 7 4842939352608049e 00 objValPrimal 3 2062693405e 01 objValDual 3 2062692354e 01 p feas error 3 7747582837e 14 d feas error 5 8841820305e 14 total time 0 000 Parameters are maxIteration 100 epsilonStar 1 000e 07 lambdaStar 1 000e 02 omegaStar 2 000e 00 lowerBound 1 000e 05 upperBound 1 000e 05 betaStar 1 000e 01 20 betaBar 2 000e 01 gammaStar 9 000e 01 epsilonDash 1 000e 07 Time sec Ratio MainLoop Predictor time 0 000000 nan abbreviation Total 0 000000 nan xVec 1 552e 00 6 710e 01 9 815e 01 1 407e 00 9 422e 01 xMat 6 392e 08 9 638e 09 9 638e 09 4 539e 08 7 119e 00 5 025e 00 1 916e 00 1 5 025e 00 4 415e 00 2 506e 00 1 916e 00 2 506e 00 2 048e 00 3 432e 01 4 391e 00 yMat 2 640e 00 5 606e 01 5 606e 01 3 718e 00 7 616e 01 1 51
24. C FORTRAN compilers BLAS and LAPACK and or Xcode as well You can skip this part if your system already have them If not you may need root access or administrative privilege to your computer Please ask your system adminis trator for installing development tools If your system only lacks BLAS and LAPACK you can build them by yourself without root privileges and passing appropriate flags at the command line 1 2 How to Obtain the Source Code You can obtain the source code following the links at the SDPA homepage http sdpa indsys chuo u ac jp sdpa index html You can find the latest news at about the SDPA at the index html file 1 3 How to Build This section describes how to build the SDPA on Fedora 8 9 1386 x86 64 ppc Ubuntu 7 10 1386 x86_64 Vine Linux 4 2 1386 MacOSX Intel PowerPC Leopard Xcode 3 0 Tiger Xcode 2 4 1 and 2 5 and FreeBSD 6 7 We assume that users have a root access via the command su or sudo If you do not have such privileges please ask your system administrators 1 3 1 Fedora 8 and 9 i386 x86_64 ppc Red Hat Enterprise Linux CentOS 4 5 i386 x86_64 To build the SDPA type the following bash su Password yum update glibc glibc common yum install gcc gcc ct gcc gfortran yum install lapack lapack devel blas blas devel yum install atlas atlas devel exit tar xvfz sdpa 7 1 1 src 2008xxxx tar gz cd sdpa 7 1 1 configure make SN 92 NN dk dt dt dt dt 1
25. ISSN 1342 2804 Research Reports on Mathematical and Computing Sciences Department of Mathematical and Computing Sciences Tokyo Institute of Technology SERIES B Operations Research Research Report B 448 Department of Mathematical and Computing Sciences Tokyo Institute of Technology June 2008 SDPA SemiDefinite Programming Algorithm and SDPA GMP User s Manual Version 7 1 1 Katsuki Fujisawa Mituhiro Fukuda Kazuhiro Kobayashi Masakazu Kojima Kazuhide Nakata Maho Nakata and Makoto Yamashita Abstract The SDPA SemiDefinite Programming Algorithm 5 is a software package for solv ing semidefinite programs SDPs It is based on a Mehrotra type predictor corrector infeasible primal dual interior point method The SDPA handles the standard form SDP and its dual It is implemented in C language utilizing the LAPACK 1 for matrix computations The SDPA version 7 1 1 enjoys the following features e Efficient method for computing the search directions when the SDP to be solved is large scale and sparse 4 Block diagonal matrix structure and sparse matrix structure are supported for data matrices Sparse or dense Cholesky factorization for the Schur matrix is automatically selected e An initial point can be specified e Some information on infeasibility of the SDP is provided Also we provide the SDPA GMP multiple precision arithmetic version of the SDPA via the GMP Library the GNU Multiple
26. LOCK 4 bLOCKsTRUCT B Ba dg Be Bees pi if B is a symmetric matrix ME p if B is a diagonal matrix For example if F is of the form 1230000 2450000 3 5 6 0 0 0 0 0001200 2 0002 300 000004 0 000000 5 we have nBLOCK 3 and bLOCKsTRUCT 3 2 2 If k k xk F x x x where x denotes a real number k xk is a usual symmetric matrix with no block diagonal structure we define nBLOCK 1 and bLOCKsTRUCT 3 We separately write each of nBLOCK and bLOCKsTRUCT in one line Any letter after either of nBLOCK and bLOCKsTRUCT through the end of the line is neglected In addition to blank letter s and the tab code s we can use the letters pocb P T3 to separate elements of the block structure vector bLOCKsTRUCT We have 1 nBLOCK bLOCKsTRUCT in Example 1 see the file examplel dat in Section 4 1 and nBLOCK 3 2 3 2 bLOCKsTRUCT in Example 2 see the file example2 dat in Section 4 2 In either case the letters nBLOCK and bLOCKsTRUCT are neglected 13 4 7 Constant Vector Specify all the elements c1 c Cm of the cost vector c In addition to blank letter s and tab code s we can use the letters gt tJ to separate elements of the vector c We have 148 8 20 in Example 1 see the file examplel dat in Section 4 1 and 11 1 10 6 6 19 4 1 in Example 2 see the file example2 dat in Section 4 2 4 8 Constraint Matrices
27. Precision Arithmetic Library with additional feature e Ultra highly accurate SDP solution by utilizing multiple precision arithmetic This manual and the SDPA can be downloaded from the WWW site http sdpa indsys chuo u ac jp sdpa index html Key words Semidefinite programming interior point method computer software multi x1 2 3 x4 x5 x6 7 ple precision arithmetic Department of Industrial and Systems Engineering Chuo University 1 13 27 Kasuga Bunkyo ku Tokyo 112 8551 Japan Global Edge Institute Tokyo Institute of Technology 2 12 1 S6 5 Oh Okayama Meguro ku Tokyo 152 8550 Japan Center for Logistics Research National Maritime Research Institute 6 38 1 Shinkawa Mitaka shi Tokyo 181 0004 Japan Department of Mathematical and Computing Sciences Tokyo Institute of Technology 2 12 1 W8 29 Oh Okayama Meguro ku Tokyo 152 8552 Japan Department of Industrial Engineering and Management Tokyo Institute of Technology 2 12 1 W9 62 Oh Okayama Meguro ku Tokyo 152 8552 Japan Advanced Center for Computing and Communication RIKEN 2 1 Hirosawa Wako shi Saitama 351 0198 Japan Department of Mathematical and Computing Sciences Tokyo Institute of Technology 2 12 1 Oh Okayama Meguro ku Tokyo 152 8552 Japan Preface We are pleased to release a new version 7 1 1 of the SDPA and the SDPA GMP The SDPA 7 1 1 was completely revised from its source code and there are great performance improvements
28. We describe the constraint matrices Fo F1 Fm according to the data format specified by nBLOCK and bLOCKsTRUCT stated in Section 4 6 In addition to blank letter s and tab code s we can use the letters gt 5 to separate elements of the matrices Fo Fy Fm and their elements In the general case of the block diagonal matrix F given in 1 we write the elements of B1 Bo Be sequentially when B is a diagonal matrix we write only the diagonal elements sequentially For instance for the matrix F given by 2 nBLOCK 3 bLOCKsTRUCT 3 2 2 the corresponding representation of the matrix F turns out to be 441 2 3 2 4 5 3 5 6 1 2 2 3 4 5 In Example 1 with nBLOCK 1 and bLOCKsTRUCT 2 we have 11 0 0 23 10 4 4 O 0 0 0 8 0 8 8 2 Y See the file examplel dat in Section 4 1 In Example 2 with nBLOCK 3 and bLOCKsTRUCT 2 3 2 we have 1 4 3 2 3 2 28 15 12 2 4 hs 12 16 3 8 2 1 3 8 15 1 8 4 0 1 1 0 5 5 2 5 2 5 3 14 7 8 2 4 6 0 2 4 4 2 6 5 6 0 6 5 2 1 4 5 3 5 14 AA 6 5 5 4 5 4 6 6 1 6 7 7 2 3 6 7 2 7 3 3 0 F 1 3 6 3 0 1 4 6 1 1 5 7 See the file example2 dat in Section 4 2 Remark We can also write the input data of Example 1 without using any letters tx such a
29. _ O G m ptl n r q Fo g O i o El F G O c 0 1 lt 2 lt p I O Fa E I j Cp 1 1 then we can reformulate the problem as the primal standard form of SDP 27 8 3 Linear Matrix Inequality LMI Let G S 0 i p We define the linear combinations of the matrices p G x Go N tG i 1 where x R The Linear Matrix Inequality LMI 3 is defined as follows G x gt O We want to find x R which satisfies the LMI or detect that any x IR cannot satisfy the LMI Here we introduce an auxiliary variable 2 1 and convert the LMI into an SDP minim1ze Tp 1 p subject to X Go iG tpl O cer i 1 We can reduce this LMI to the primal standard form of SDP if we take m p l Fo Go F G Gq 0 1 lt i lt p Foi I Cp 1 1 One important point of this SDP is that it always has a feasible solution When we can get the optimal solution with 2 1 gt 0 then x1 2p satisfies the LMI On the other hand if 2 1 lt 0 then we can conclude that the LMI cannot be satisfied by any x R 8 4 SDP Relaxation of the Maximum Cut Problem Let G V E be a complete undirected graph with a vertex set V 1 2 n and an edge set E i j i j V i lt j We assign a weight W Wi to each edge i j E The maximum cut problem is to find a partition L R of V that maximizes the cut w L R Vier jer Wij Introducing a variable vector u R
30. an install it as su Password mkdir usr local bin cp sdpa_gmp usr local bin chmod 777 usr local bin sdpa or you can install it to your favorite directory mkdir home nakata bin cp sdpa_gmp home nakata bin A6 Test Run Before using the SDPA type sdpa gmp and make sure that the following message will be displayed sdpa_gmp SDPA GMP start at Fri Apr 4 16 02 00 2008 Please assign data file and output file gt option type 1 sdpa gmp DataFile OutputFile InitialPtFile pt parameters parameters 0 default 1 fast unstable 2 slow stable examplei 1 sdpa gmp example1 dat examplel result examplei 2 sdpa gmp examplei dat s examplei result example1 3 sdpa gmp examplei dat examplei result examplei ini examplei 4 sdpa gmp example1 dat examplel result pt 2 Option type 2 sdpa gmp option filename dd data dense ds data sparse id init dense is init sparse o output 3 p parameter pt parameters 0 default 1 fast unstable 2 slow stable example2 1 sdpa gmp o examplei result dd examplel dat example2 2 sdpa gmp ds examplei dat s o example2 result p param sdpa example2 3 sdpa gmp ds examplei dat s o example3 result pt 2 32 Let us solve the SDP examplel dat s sdpa gmp ds examplei dat s o examplei out SDPA GMP start at Fri Apr 4 16 05 39 2008 data is examplei dat s sparse
31. ata file output file To solve Example 1 type sdpa examplei dat examplel out 6 2 Output on the Display The SDPA shows some information on the display In the case of Example 1 we have SDPA start at Fri Dec 7 18 30 56 2007 data is examplei dat s sparse parameter is param sdpa out is example 1 out DENSE computations mu thetaP thetaD objP objD alphaP alphaD beta O 1 0e 04 1 0e 00 1 0e 00 0 00e 00 1 20e 03 1 0e 00 9 1e 01 2 00e 01 1 1 6e 03 0 0e 00 9 4e 02 8 39e 02 7 51e 01 2 3e 00 9 6e 01 2 00e 01 2 1 7e 02 2 3e 16 3 6e 03 1 96e 02 3 74e 01 1 3e 00 1 0e 00 2 00e 01 3 1 8e 01 2 3e 16 1 5e 17 6 84e 00 4 19e 01 9 9e 01 9 9e 01 1 00e 01 4 1 9e 00 2 6e 16 1 5e 17 3 81e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 5 1 9e 01 2 6e 16 3 0e 17 4 15e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 6 1 9e 02 2 5e 16 1 6e 15 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 7 1 9e 03 2 6e 16 2 2e 17 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 8 1 9e 04 2 5e 16 1 5e 17 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 9 1 9e 05 2 7e 16 7 5e 18 4 19e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 10 1 9e 06 2 6e 16 5 0e 16 4 19e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 phase value pdOPT Iteration 10 mu 1 9180668442024010e 06 relative gap 9 1554505577840628e 08 gap 3 8361336884048019e 06 digits 7 0383202783481345e 00 objValPrimal 4 1899996163866390e 01 objValDual 4 1899999999999999e 01 p feas error 3 2137639581876834e 14 d feas error 4 7961
32. d Comments On the top of the input data file we can write a single or multiple lines for Title and Comments Each line of Title and Comments must begin with or and should consist of no more than 75 letters for example Example 1 mDim 3 nBLOCK 1 12 in the file examplel dat and Example 2 mDim 5 nBLOCK 3 2 3 2 in the file example2 dat The SDPA displays Title and Comments when it starts Title and Comments can be omitted 4 5 Number of the Primal Variables We write the number m of the primal variables in a line following the line s of Title and Comments in the input data file All the letters after m through the end of the line are neglected We have 3 mDIM in the file examplel dat and 5 mDIM in the file example2 dat In either case the letters mDIM are neglected 12 4 6 Number of Blocks and the Block Structure Vector The SDPA handles block diagonal matrices as we have seen in Section 2 3 We express a common matrix data structure for the constraint matrices Fo F1 Fm using the terms number of blocks denoted by nBLOCK and block structure vector denoted by LLOCKsTRUCT If we deal with a block diagonal matrix F of the form B OO O OBO 0 F gt E E O 1 O OO B B a p X pi symmetric matrix 1 2 we define the number nBLOCK of blocks and the block structure vector LLOCKsTRCTURE as follows nB
33. e Developer Connection Then type the following bash tar xvfz sdpa 7 1 1 src 2008xxxx tar gz cd sdpa 7 1 1 configure make 1 3 6 FreeBSD 6 and 7 cd usr ports su Password make update cd usr ports math sdpa make install exit 1 4 How to Install You will find the sdpa executable binary file at this point and you can install it as su Password mkdir usr local bin cp sdpa usr local bin chmod 777 usr local bin sdpa or you can install it to your favorite directory mkdir home nakata bin cp sdpa home nakata bin 1 5 Test Run Before using the SDPA type sdpa and make sure that the following message will be displayed sdpa SDPA start at Tue Jan 22 15 28 59 2008 Please assign data file and output file x x option type 1 sdpa DataFile OutputFile InitialPtFile pt parameters parameters 0 default 1 aggressive 2 stable examplei 1 sdpa examplei dat examplei result examplei 2 sdpa examplei dat s examplel result examplei 3 sdpa examplei dat examplei result examplel ini examplei 4 sdpa examplei dat examplei result pt 2 Option type 2 sdpa option filename dd data dense ds data sparse id init dense is init sparse o output 3 p parameter pt parameters 0 default 1 aggressive 2 stable example2 1 sdpa o examplei result dd examplel dat example2 2 sdpa ds examplei
34. evious section To solve Example 1 type sdpa examplel dat examplel out Here examplel out denotes an output file in which the SDPA stores computational results such as an approximate optimal solution an approximate optimal value of Example 1 etc Similarly we can solve Example 2 10 4 Input Data File 4 1 examplel dat Input Data File of Example 1 Example 1 mDim 3 nBLOCK 1 12 3 mDIM 1 nBLOCK 2 bLOCKsTRUCT 48 8 20 11 0 0 23 10 4 4 0 gt 0 0 0 8 3 1 0 8 8 2 3 4 2 example2 dat Input Data File of Example 2 Example 2 mDim 5 nBLOCK 3 2 3 2 5 mDIM 3 nBLOCK 2 3 2 bLOCKsTRUCT 1 1 10 6 6 19 4 1 1 1 4 3 2 3 2 28 15 12 2 1 12 16 3 8 2 1 3 8 15 1 8 4 0 1 1 0 5 5 2 5 2 5 3 11 7 8 2 4 6 0 2 4 4 2 6 5 6 0 6 5 2 1 4 5 3 5 e e e 1 6 5 5 4 5 4 6 6 11 6 7 7 2 3 6 7 2 7 3 3 0 3 6 3 0 1 4 6 1 1 5 11 4 3 Format of the Input Data File In general the structure of an input data file is as follows Title and Comments m number of the primal variables r s nBLOCK number of blocks bLOCKsTRUCT block structure vector c Fo Fi Fm In Sections 4 4 through 4 8 we explain each item of the input data file in details 4 4 Title an
35. f iterations BLAS library of threads Prob 1 Prob 2 Prob 3 Prob 4 BLAS LAPACK 3 1 1 1 70 51 36 128 36 15 226 24 18 342 42 20 ATLAS 3 8 1 1 53 00 35 49 86 15 41 24 18 182 65 19 ATLAS 3 8 1 4 32 76 35 19 66 15 18 26 18 81 73 19 Intel MKL 10 0 2 018 1 44 25 35 39 92 15 34 63 18 172 05 21 Intel MKL 10 0 2 018 2 32 88 35 24 43 15 22 44 18 110 41 22 Intel MKL 10 0 2 018 4 26 61 35 16 38 15 16 37 18 67 78 18 Intel MKL 10 0 2 018 8 25 17 35 13 38 15 14 83 18 63 01 19 GotoBLAS 1 24 1 42 94 34 40 37 15 32 42 18 160 75 21 GotoBLAS 1 24 2 31 81 35 23 89 15 21 07 18 99 76 20 GotoBLAS 1 24 4 26 60 36 14 81 15 15 59 18 64 29 18 GotoBLAS 1 24 8 23 84 35 11 57 15 13 95 18 67 47 21 CPU Intel Xeon 5345 2 33GHz x 2 CPUs 8 cores OS CentOS Ver 5 1 64bit Compiler Table 2 Numerical experiments SDPA 7 0 5 BLAS library Intel C C amp Fortran 10 1 012 time sec of iterations BLAS library of threads Prob 1 Prob 2 Prob 3 Prob 4 BLAS LAPACK 3 11 1 49 48 36 67 23 15 143 84 18 220 38 20 ATLAS 3 81 1 40 29 35 37 27 15 32 14 18 145 72 20 ATLAS 3 8 1 2 29 76 35 23 22 15 21 12 18 99 04 21 Intel MKL 10 0 2 018 1 33 39 35 30 49 15 26 68 18 129 72 21 Intel MKL 10 0 2 018 2 25 00 35 18 72 15 17 56 18 84
36. for semidefinite programming Mathematical Programming Series B 79 1997 235 253 5 K Fujisawa K Nakata M Yamashita and M Fukuda SDPA project Solving large scale semidefi nite programs Journal of Operations Research Society of Japan 50 2007 278 298 6 H D Mittelmann An independent benchmarking of SDP and SOCP solvers Mathematical Pro gramming Series B 95 2003 407 430 35
37. lity error on the constraints XL Y ap 1 max c 1 2 m e Err2 The relative dual feasibility error on the semidefiniteness MEP 0 mx 14 max c 1 2 m e Err3 The relative primal feasibility error on the constraints X Ez Fish Folly 1 max Fo i j 1 2 n e Err4 The relative primal feasibility error on the semidefiniteness 0 Amin X max 0 zz 1 max Fo ij i j 1 2 n e Err5 The relative duality gap 1 bem ca Fyo Y 1 0 cet Fo e Y e Err6 The relative duality gap 2 X y 1 Eart Foe Y where is a norm defined as a sum of the Frobenius norm of each block diagonal matrix and Aquis is the smallest eigenvalue of a matrix 7 Advanced Use of the SDPA 7 1 Initial Point If a feasible interior solution 2 X Y is known in advance we may want to start the SDPA from z9 X e Y In such a case we can optionally specify a file which contains the data of a feasible interior solution when we execute the SDPA for example if we want to solve Example 1 from a feasible interior initial point 0 X9 y0 _ E 11 0 0 0 5 9 1 375 Qus ge ao 0 0 9 0 1 375 1 0 type 22 sdpa examplei dat examplei out examplei ini Here examplel ini denotes an initial point file containing the data of a feasible interior solution 10 0 4 0 0 0 11 0 0 0 10 0 9 0 5 9
38. may cause numerical instability A reasonable choice is epsilonStar and epsilonDash gt 1 0F 7 lambdaStar This parameter determines an initial point x X Y such that x 0 X lambdaStar x I Y lambdaStar x I Here I denotes the identity matrix It is desirable to choose an initial point x X n Y having the same order of magnitude of an optimal solution a X Y of the SDP In general however choosing such lambdaStar is difficult If there is no information on the magnitude of an optimal solution z X Y of the SDP we strongly recommend to take a sufficiently large lambdaStar such that X XlambdaStar x I and Y lambdaStar x I omegaStar This parameter determines the region in which the SDPA searches an optimal solution For the primal problem P the SDPA searches a minimum solution x X within the region O x X X omegaStar x xX omegaStar x lambdaStar x I and stops the iteration if it detects that the primal problem P has no minimum solution in this region For the dual problem D the SDPA searches a maximum solution Y within the region O lt Y lt omegaStar x y omegaStar x lambdaStar x I and stops the iteration if it detects that the dual problem D has no maximum solution in this region Again we recommend to take a large lambdaStar and a small omegaStar gt 1 lowerBound Lower bound of the minimum objective value of the primal problem P When the SDPA generates a p
39. n the sparse data format 0 0 4 0 0 0 1111 11 11229 2111 5 9 2 1 1 2 1 375 21221 Compare the dense initial point file examplel ini described in Section 7 1 with the sparse initial file examplel ini s above The first line of the file examplel ini s is the same as that of the file exam plel ini which describes z in the dense format Each line of the rest of the file examplel ini s describes a single element of an initial matrix X if the first number of the line is 1 or a single element of an initial matrix Y if the first number of the line is 2 The 2nd line 1 1 1 1 11 means that the 1 1 th element of the 1st block of the matrix X is 11 the 5th line 2 1 1 2 1 375 means that the 1 2 th element of the 1st block of the matrix Y is 1 375 6 A sparse initial point file must have a name with the postfix ini s for example problem ini s and example ini s are legitimate names for sparse input data files The SDPA distinguishes a sparse input data file with the postfix ini from a dense input data file with the postfix ini s In general the structure of a sparse input data file is as follows x s b i1 j v1 s2 ba la ja V2 Sp bp lp jp Up Sq bq dq Ja Va Here s 1 or 2 b 1 2 nBLOCK 1 lt ip lt jp and v R When s 1 each line Sp by tp jp Up means that the value of the ip jp th element of the b th block of the constant matrix X
40. nction value objD The dual objective function value alphaP The primal step length alphaD The dual step length beta The search direction parameter phase value The status when the iteration stops taking one of the values pdOPT noINFO pFEAS dFEAS pdFEAS pdINF pFEAS dINF pINF dFEAS pUNBD and dUNBD pdOPT The normal termination yielding both primal and dual approximate optimal solutions noINFO The iteration has exceeded the maxlteration and stopped with no information on the primal feasibility and the dual feasibility pFEAS The primal problem P got feasible but the iteration has exceeded the maxIteration and stopped dFEAS The dual problem D got feasible but the iteration has exceeded the maxlteration and stopped pdFEAS Both primal problem P and the dual problem D got feasible but the iteration has exceeded the maxlteration and stopped pdINF At least one of the primal problem P and the dual problem D is expected to be infeasible More precisely there is no optimal solution a X Y of the SDP such that O lt X omegaStar x x O lt Y lt omegaStar x y rn Fo e Y i 1 18 pFEAS dINF The primal problem 7 has become feasible but the dual problem is expected to be infeasible More precisely there is no dual feasible solution Y such that O lt Y omegaStar x Y lambdaStar x omegaStar x I pINF dFEAS The dual problem D has become feasible but the primal problem is expected
41. on its computational time and memory usage In particular it uses and stores less variables internally and its overall memory usage is less than half of the previous version Also it performs sparse Cholesky factorization when the Schur Complement Matrix is sparse As a consequence the SDPA can efficiently solve SDPs with a large number of block diagonal matrices or non negative constraints Additional there are some improvements on its numerical stability due to a better control in the interior point algorithm The differences between this version and the previous version 6 2 1 are summarized in Sec tion 9 Finally we also provide the SDPA GMP to solve SDPs highly accurately utilizing multiple precision arithmetic via the GMP Library the GNU Multiple Precision Arithmetic Library Note that the SDPA GMP is typically several hundred times slower than the SDPA Details of the SDPA GMP are summarized in the Appendix We hope that the SDPA and the SDPA GMP support many researches in various fields We also welcome any suggestions and comments that you may have When you want to contact us please send an e mail to the following address kojima sdpa is titech ac jp iii Contents 1 Build and Installation l l Prerequisites s s sa mo 6 oe eae ar a a ewe 12 How to Obtain the Source Code o a L3 Howto Build 2240244 22 8654 kh ko a a a ea 1 3 1 Fedora 8 and 9 i386 x86_64 ppc Red Hat Enterprise Linux CentOS 4 5 IS ROBA
42. ote that the SDPA GMP is typically several ten or hundred times slower than the SDPA A1 Build and Installation This subsection describes how to build and install the SDPA GMP Usually the SDPA is distributed as source codes therefore users must build it by themselves We have build and installation tests on Fedora 8 Ubuntu 7 10 MacOSX Leopard and Tiger and FreeBSD 6 7 You may also possibly build on other UNIX like platforms and Windows cygwin environment A2 Prerequisites It is necessary to have at least the following programs installed on your system except for the MacOSX e C and C compiler e GMP library http gmplib org For MacOSX Leopard you will need the Xcode 3 0 and you cannot build the SDPA on the Leopard with Xcode 2 5 For MacOSX Tiger you will need either the Xcode 2 4 1 or the Xcode 2 5 You can download the Xcode at Apple Developer Connection http developer apple com at free of charge In the following instructions we install C C compilers GMP library and or Xcode as well You can skip this part if your system already have them If not you may need root access or administrative privilege to your computer Please ask your system administrator for installing development tools 30 A3 How to Obtain the Source Code Current source code is sdpa gmp 7 1 1 src 2008xxxx tar gz You can obtain the source code following the links at the SDPA homepage http sdpa indsys chuo u ac jp sdpa index html
43. out is examplel out set is DEFAULT DENSE computations mu thetaP thetaD objP objD O 1 0e 08 1 0e 00 1 0e 00 0 00e 00 1 20e 05 1 1 6e 07 0 0e 00 1 0e 01 1 10e 05 1 20e 04 2 2 5e 06 2 6e 71 9 9e 03 1 68e 05 1 15e 03 3 4 6e 05 4 8e 71 9 4e 04 2 40e 05 7 05e 01 4 7 3e 04 7 8e 71 3 6e 05 1 00e 05 3 76e 01 5 1 5e 04 7 4e 71 5 2e 72 2 99e 04 4 19e 01 6 2 0e 03 7 8e 71 5 9e 72 3 88e 03 4 19e 01 7 2 2e 02 8 1e 71 1 2e 71 3 93e 02 4 19e 01 8 2 2e 01 5 9e 71 1 2e 71 2 19e 00 4 19e 01 9 2 2e 00 6 3e 71 2 4e 70 3 75e 01 4 19e 01 10 2 2e 01 6 8e 71 1 8e 71 4 15e 01 4 19e 01 11 2 2e 02 7 7e 71 1 2e 71 4 19e 01 4 19e 01 12 2 2e 03 7 3e 71 1 2e 71 4 19e 01 4 19e 01 13 2 2e 04 7 7e 71 1 2e 71 4 19e 01 4 19e 01 14 2 2e 05 7 9e 71 3 1e 70 4 19e 01 4 19e 01 15 2 2e 06 8 3e 71 5 9e 72 4 19e 01 4 19e 01 16 2 2e 07 8 5e 71 1 2e 71 4 19e 01 4 19e 01 17 2 2e 08 9 4e 71 1 2e 71 4 19e 01 4 19e 01 18 2 2e 09 1 0e 70 5 2e 72 4 19e 01 4 19e 01 19 2 2e 10 1 1e 70 5 6e 72 4 19e 01 4 19e 01 20 2 2e 11 1 4e 70 1 5e 69 4 19e 01 4 19e 01 21 2 2e 12 1 4e 70 5 9e 72 4 19e 01 4 19e 01 22 2 2e 13 1 5e 70 1 2e 71 4 19e 01 4 19e 01 23 2 2e 14 1 6e 70 5 9e 72 4 19e 01 4 19e 01 24 2 2e 15 1 6e 70 4 1e 70 4 19e 01 4 19e 01 25 2 2e 16 1 8e 70 5 9e 72 4 19e 01 4 19e 01 26 2 2e 17 2 0e 70 3 6e 70 4 19e 01 4 19e 01 27 2 2e 18 2 3e 70 1 2e 71 4 19e 01 4 19e 01 28 2 2e 19 2 7e 70 1 2e 71 4 19e 01 4 19e 01 29 2 2e 20 3 0e 70 1 3e 69 4 19e
44. rimal feasible solution x X E whose objective value 5 cial gets smaller than i 1 the lowerBound the SDPA stops the iteration the primal problem P is likely to be unbounded and the dual problem D is likely to be infeasible if the lowerBound is sufficiently small upperBound Upper bound of the maximum objective value of the dual problem D When the SDPA generates a dual feasible solution Y whose objective value Fo e Y gets larger than the upperBound the SDPA stops the iteration the dual problem D is likely to be unbounded and the primal problem P is likely to be infeasible if the upperBound is sufficiently large betaStar Parameter controlling the search direction when z X Y is feasible As we take a smaller betaStar gt 0 0 the search direction tends to get closer to the affine scaling direction without centering betaBar Parameter controlling the search direction when x X ph do is infeasible As we take a smaller betaBar gt 0 0 the search direction tends to get closer to the affine scaling direction without centering The value of betaBar must be no less than the value of betaStar 0 betaStar lt betaBar gammaStar Reduction factor for the primal and dual step lengths 0 0 lt gammaStar 1 0 16 6 Output 6 1 Execution of the SDPA To execute the SDPA we specify and type the names of three files sdpa an input data file and an output file as follows sdpa input d
45. rrrrrrrrrrrerrrrrrrrerrrrerrrrrrrrerewwwuwuw 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 00e 01 digits 3 0977741576287968e 01 objValPrimal 4 1900000000000000e 01 objValDual 4 1900000000000000e 01 p feas error 4 7832028277324550e 66 d feas error 1 1127618452062264e 66 relative eps 3 7092061506874214e 68 total time 0 080 main loop time 0 080000 total time 0 080000 file read time 0 000000 A Parameters First we show the default parameter file param sdpa below Only the difference between Section 5 is the precision parameter 200 unsigned int maxIteration 1 0E 30 double 0 0 lt epsilonStar 1 0E4 double 0 0 lt lambdaStar 2 0 double 1 0 lt omegaStar 1 0E5 double lowerBound 1 0E5 double upperBound 0 1 double 0 0 lt betaStar lt 1 0 0 3 double 0 0 lt betaBar lt 1 0 betaStar lt betaBar 0 9 double 0 0 lt gammaStar lt 1 0 1 0E 30 double 0 0 lt epsilonDash 200 precision The file param sdpa needs to have these 11 lines which sets 11 parameters Each line of this file contains one of the 11 parameters followed by an comment When the SDPA reads the file param sdpa
46. s Example 1 mDim 3 nBLOCK 1 2 3 1 2 48 8 20 41 0 0 23 10 4 4 0 0 0 0 8 0 8 8 2 5 Parameter File First we show the default parameter file param sdpa below 40 unsigned int maxIteration 1 0E 7 double 0 0 epsilonStar 1 0E2 double 0 0 lt lambdaStar 2 0 double 1 0 lt omegaStar 1 0E5 double lowerBound 1 0E5 double upperBound 0 1 double 0 0 lt betaStar lt 1 0 0 2 double 0 0 lt betaBar lt 1 0 betaStar lt betaBar 0 9 double 0 0 lt gammaStar lt 1 0 1 0E 7 double 0 0 lt epsilonDash The file param sdpa needs to have these 10 lines which sets 10 parameters Each line of this file contains one of the 10 parameters followed by an comment When the SDPA reads the file param sdpa it neglects the comments e maxlteration Maximum number of iterations The SDPA stops when the iteration exceeds max Iteration 15 e epsilonStar epsilonDash The accuracy of an approximate optimal solution of the SDP When the current iterate z X Y satisfies all of the inequalities epsilonDash gt epsilonDash gt epsilonStar gt i 1 max i cue 5 Fiz Folpg I max F e Y c devi md Din otf Fo e Y max O72 cia Fo e Y 2 0 1 0 primal objective value dual objective value max primal objective value dual objective value 2 0 1 0 the SDPA stops Too small epsilonStar and epsilonDash
47. se parameters The one is the set Stable but Slow for difficult SDPs and the other is the set Unstable but Fast for easy SDPs Stable but Slow 1 0E4 double 0 0 lt lambdaStar 0 10 double 0 0 lt betaStar lt 1 0 0 30 double 0 0 lt betaBar lt 1 0 betaStar lt betaBar 0 80 double 0 0 gammaStar lt 1 0 Unstable_but_Fast 0 01 double 0 0 lt betaStar lt 0 02 double 0 0 lt betaBar lt A 0 95 double 0 0 lt gammaStar lt 1 0 1 0 1 0 betaStar lt betaBar Besides these parameters the value of the parameter lambdaStar which determines an initial point x9 X Y affects the computational efficiency and the numerical stability Usually a larger lambdaStar is safe although the SDPA may consume few more iterations 25 8 Transformation to the Standard Form of SDP SDP has many applications but frequently problems are not described in the standard form of SDP In this section we show some examples on how to transform to the standard form of SDP 8 1 Inequality Constraints First we consider the case where inequality constraints are added to the primal standard form of SDP For example m minimize y Cid i 1 m subject to X M Fizi Fo X O m m Xaris o Y up i 1 i 1 Here al a i 2 1 m 81 8 R In this case we add slack variables t t T minimize oe Cid i l subject to X Y Fis Fo X gt O i l m t X Caer Pes eer 6 8420
48. t for better performance in many cases To pass your optimization flags set them in CFLAGS and CXXFLAGS environment variables Here is an example bash make clean export CFLAGS static funroll all loops 03 m64 march nocona msse3 mfpmath sse export CXXFLAGS static funroll all loops 03 m64 march nocona msse3 mfpmath sse configure with blas L home nakata gotoblas lib lgoto with lapack L home nakata gotoblas lib lgoto llapack make 2 Semidefinite Program 2 1 Standard Form SDP and Its Dual The SDPA Semidefinite Programming Algorithm solves the following standard form semidefinite program and its dual m P minimize 1 Citi i 1 SDP subject to X S Fizi Fo S X gt O i 1 D maximize FoeY subject to Fie Y c i 1 2 m S Y gt O S set of n x n real symmetric matrices F e S i 0 1 m constraint matrices Oc zero matrix C1 T C2 T2 c ER cost vector r ER variable vector Cm Tm XES Y ES variable matrices n n UeV inner product between U and V S i e 3 5 Ui Vij i21 j l U gt O lt U ES is positive semidefinite Throughout this manual we denote the primal SDP by P and its dual problem by D The SDP is determined by m n c R and F S 0 1 m When a X is a feasible solution or a minimum solution resp of the primal problem P and Y is a feasible solution or a maximum solution resp we call
49. ta 9 For the SDPA 6 2 1 Users The major differences between the SDPA 6 2 1 and the SDPA 7 1 1 are the followings 29 e The source code was completely revised unnecessary variables were eliminated and auxiliary variables re used Consequently the memory usage became less than half of the previous version e t utilizes the sparse Cholesky factorization when the Schur Complement Matrix becomes sparse For that it uses the SPOOLES library for sparse matrices 2 to obtain an ordering of rows columns which possibly produces lesser fill in Now the SDPA can solve much more efficiently SDPs with multiple block diagonal matrices multiple non negative constraints e There is a modification in the control subroutine in the interior point algorithm which improved its numerical stability when compared to the previous version Though it should be noted there is a remaining problem e The current version does not have a callable library interface as SDPA 6 2 1 does but it will be implemented in the updated version of the SDPA A SDPA GMP The SDPA GMP is an SDP solver intended to solve SDPs very accurately by utilizing the GNU Multiple Precision Arithmetic Library GMP Current version of the SDPA GMP is 7 1 1 which shares the same features with the SDPA except for user settable accuracy usually for extraordinary accurate calculations Expect for newly added one parameters precision user experience is the same as the SDPA N
50. to be infeasible More precisely there is no feasible solution x X such that O lt X omegaStar x X lambdaStar x omegaStar x I pUNBD The primal problem is expected to be unbounded More precisely the SDPA has stopped generating a primal feasible solution z X such that m objP 5 ca lt lowerBound i 1 dUNBD The dual problem is expected to be unbounded More precisely the SDPA has stopped generating a dual feasible solution Y such that objD Fo e Y gt upperBound Iteration The iteration number when the SDPA terminated relative gap The relative gap lobjP objD max 1 0 JobjP lobjD 2 This value is compared with epsilonStar Section 5 gap The gap is mu x n digits This value indicates how objP and objD resemble by the following definition lobjP objD lobjP JobjD 2 0 oe cim Foe Y digits logio log A X cia Fo e Y 2 0 objValPrimal The primal objective function value objValPrimal 5 cat i 1 objValDual The dual objective function value objValD Fo e Y p feas error This value indicates the primal infeasibily in the last iteration II This value is compared with epsilonDash Section 5 Even if the primal problem is feasible this value may not be 0 due to numerical errors p feas error max po 5 Fixt Folp q i 1 d feas error This value indicates the dual infeasibily in the last
Download Pdf Manuals
Related Search