SDPA-M - The UK Mirror Service
Contents
1. changing the current maxlteration for a large number does not make the result better In the first case you have to make gammaStar smaller In the other case you have to change betaStar betaBar gammasStar by try and error but it is possible that the problem itself is hard to compute by this algorithm 25 9 Sample Runs The function sdpam can be overloaded as shown below gt gt objVal x X Y INFO sdpam mDIM nBLOCK bLOCKsTRUCT c F gt gt objVal x X Y INFO sdpam mDIM nBLOCK bLOCKsTRUCT c F OPTION gt gt objVal x X Y INFO sdpam mDIM nBLOCK bLOCKsTRUCT c F x0 XO YO gt gt objVal x X Y INFO sdpam mDIM nBLOCK bLOCKsTRUCT c F x0 XO YO OPTION If you want to specify the initial point include 2 X Y as input argument gt gt objVal x X Y INFO or gt gt objVal x X Y INFO sdpam mDIM nBLOCK bLOCKsTRUCT c F x0 XO YO OPTION sdpam mDIM nBLOCK bLOCKsTRUCT c F x0 XO YO Otherwise initial point is calculated from parameter lambdaStar If you want to modify OPTION make sure to include OPTION as input argument gt gt objVal x X Y INFO sdpam mDIM nBLOCK bLOCKsTRUCT c F OPTION or gt gt objVal x X Y INFO sdpam mDIM nBLOCK bLOCKsTRUCT c F x0 XO YO OPTION Otherwise the default values take precedence even if you modify OPTION value 10 SDP Feasibility Problem 10 1 Conversion into Standard Form SDP In this section we explain how to solve an SDP feasibility problem i e in th2. ON maxIteration 40 epsilonStar 1 0000e 07 lambdaStar 100 omegaStar 2 lowerBound 100000 upperBound 100000 betaStar 0 1000 betaBar 0 2000 gammaStar 0 9000 epsilonDash 1 0000e 07 isSymmetric 0 print display maxlteration The maximum number of iterations The SDPA M stops when the iteration exceeds the maxIteration epsilonStar epsilonDash The accuracy of an approximate optimal solution of an SDP to be solved When the current iterate a X Y satisfies the inequalities m X S Fiz Folpg epsilonDash gt max f i 1 O epsilonDash gt max F sy Ci X cit Foe Y max 07 cxf Fo e Y 2 0 1 0 lthe primal objective value the dual objective value max the primal objective value the dual objective value 2 0 1 0 A IV epsilonStar the SDPA M stops Too small epsilonStar and epsilonDash may cause a numerical instability A reasonable choice is epsilonStar gt 1 0E 7 lambdaStar This parameter determines an initial point x X a 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 2 X Y hav ing the same order of magnitude as an optimal solution a X Y of the SDP In general however choosing such a lambdaStar is difficult If there is no information on the magnitude of an optimal solution x X Y of the SDP we strongly
3. 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 Fizi als Xk E Folpa Pq A a max X Fit X Folpa ppq 1 2 N thetaP The thetaP is theoretically monotone nonincreasing and when it gets 0 0 we obtain a primal feasible solution a X In the example above we obtained a primal feasible solution in the 1st iteration e thetaD The SDPA M 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 t O max F e Y LoS 1 2 my thetaD The thetaD is theoretically monotone nonincreasing 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 23 objP The primal objective function 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
4. 2 2 where x denotes a real number 10 is a usual symmetric matrix with no block diagonal structure we define nBLOCK 1 and bLOCKsTRUCT 3 We have gt gt nBLOCK 1 gt gt bLOCKsTRUCT 2 in Example 1 and gt gt nBLOCK 3 gt gt bLOCKsTRUCT 2 3 2 in Example 2 LLOCKsTRUCT can be a column vector c Constant vector We write all the elements c1 C2 Cm of the constant vector c We have gt gt c 48 8 20 in Example 1 and gt gt c 1 1 10 6 6 19 4 1 in Example 2 F Constraint matrices F is nBLOCKx mDIM 1 cell matrix Fo Fy Fm Ist block F 1 1 F 1 2 F 1 m 1 2nd block F 2 1 F 2 2 F 2 m 1 n th block F n 1 F n 2 F n m 1 Here each F i j denotes the ith block of F _1 i 1 nBLOCK j 1 For simplicity nBLOCK is denoted as n In Example 1 we have gt gt F cell 1 4 gt gt F 1 1 11 0 0 23 gt gt F 1 4 0 8 8 2 gt gt F F 2x2 double 2x2 double 2x2 double 2x2 double and in Example 2 11 mDIM 1 gt gt F cell 3 6 gt gt F 1 1 1 4 3 2 3 2 28 gt gt F 3 6 6 1 1 5 gt gt F F Columns 1 through 4 2x2 double 2x2 double 2x2 double 2x2 double 3x3 double 3x3 double 3x3 double 3x3 double 2x1 double 2x1 double 2x1 double 2x1
5. Then the problem 6 is converted into minimize cx subject to Fix Fora F3x3 Fat Fo O 7 where e eR ls a 0 0 0 HG x x 2 T3 lie T2 T3 Q21 22 2a11 a 2 O 0 0 2a91 a11 a2 0 0 0 a12 0 0 0 0 7 022 2412 0 0 0 BS 0 0 1 010 F2 0 0 110 0 0 JO 0 0 0 1 0 0 0 0 JO 0 0 0 0 0 0 0 az2 0 0 0 1 0 0 010 0 0 0 0 0 ie 2a92 0 0 a E 110 0 o E 0 0 0 0 F3 0 0 0 0 0 Fa 0 0 1 0 0 Fo 0 0 1 O 0 0 0 0 1 0 0 0 0 110 0 0 0 1 0 0 0 0 0 0 00 0 0 1 0 0 0 0O 1 Note that the 1st diagonal block of F matrices corresponds with XA ATX lt tI the 2nd diagonal block corresponds with X I gt tI and the 8rd diagonal block corresponds with t gt 1 respectively Let us solve the case 0 1 are that is all eigenvalues are negative A 1 3 To solve this problem we write the following MATLAB code A 0 1 3 4 mDIM 4 27 nBLOCK 3 bLOCKsTRUCT 2 2 1 c 0 0 0 1 F ce11 3 5 F_ 0 F 2 1 eye 2 F 3 1 1 F_ 1 F 1 2 2 A 1 1 A 1 2 A 1 2 01 F 2 2 1 0 0 0 F_ 2 F 1 3 2 A 2 1 A 1 1 A 2 2 A 1 1 A 2 2 2 A 1 2 F 2 3 0 1 1 0 F_ 3 F 1 4 0 A 2 1 A 2 1 2 A 2 2 F 2 4 0 0 O 1 F_ 4 F 1 5 eye 2 2 F 2 5 eye 2 2 F13 5 1 solve the problem by SDPA M objVal x X Y INFO sdpam mDIM nBL
6. solutions noINFO The iteration has exceeded the maxIteration 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 maxltera tion and stopped dFEAS The dual problem D got feasible but the iteration has exceeded the maxIteration 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 XomegaStar x X O lt Y lt omegaStar x Y m y Citi F poe Y i l pFEAS_dINF The primal problem P 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 lt omegaStar x Y lambdaStar x omegaStar x TI pINF_dFEAS The dual problem D has become feasible but the primal problem is expected to be infeasible More precisely there is no feasible solution a X such that O lt X lt omegaStar x X lambdaStar x omegaStar x I pUNBD The primal problem is expected to be unbounded More precisely the SDPA M has stopped generating a primal feasible solution a X R such that m objP y cx lt lowerBound i l dUNBD The dual problem is expected to be unbounded More precis
7. 00 1 0e 00 0 00e 00 1 20e 03 1 0e 00 9 1e 01 2 00e 01 1 1 6e 03 1 0e 16 9 4e 02 8 39e 02 7 51e 01 2 3e 00 9 6e 01 2 00e 01 2 1 7e 02 1 9e 16 3 6e 03 1 96e 02 3 74e 01 1 3e 00 1 0e 00 2 00e 01 22 O ON DOP W PRPrPrPrPrP RP PB 8e 01 1 6e 16 9 9 1 9e 00 1 6e 16 1 0e 00 1 0e 00 1 00e 01 9e 01 1 6e 16 1 0e 00 1 0e 00 1 00e 01 9e 02 1 6e 16 7 5e 18 4 19e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 1 1 1 1 9 1 1 1 1 1 1 1 2 2e 17 6 84e 00 4 19e 01 1 1 7 9e 03 1 6e 16 5 8e 16 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 2 3 2 5e 17 3 81e 01 4 19e 01 5e 17 4 15e 01 4 19e 01 9e 01 9 9e 01 1 00e 01 9e 04 1 8e 16 2 2e 17 4 19e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 9e 05 1 5e 16 3 1e 15 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 9e 06 1 6e 16 2 2e 17 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 phase value pdOPT Iteration 10 mu 1 9180668442025276e 06 relative gap 9 1554506595324411e 08 gap 3 8361336884050552e 06 digits 7 0383202735216370e 00 objValPrimal 4 1899996163866327e 01 objValDual 4 1899999999999977e 01 p feas error 1 9317880628477724e 14 d feas error 2 1316282072803006e 14 e mu The average complementarity X e Y n an optimality measure When both P and D get feasible the relation m mu Seat ro n i 1 the primal objective function the dual objective function n holds e thetaP The SDPA M starts with thetaP 0 0 if the initial point 2
8. 06 relative gap 9 1554506595324411e 08 gap 3 8361336884050552e 06 digits 7 0383202735216370e 00 objValPrimal 4 1899996163866327e 01 objValDual 4 1899999999999977e 01 p feas error 1 9317880628477724e 14 d feas error 2 1316282072803006e 14 In the following sections each arguments and contents of the output are explained 5 Problem Data Input 5 1 Input Arguments e mDIM The number of primal variables We have gt gt mDIM 3 in Examplel and gt gt mDIM 5 in Example2 e nBLOCK bLOCKsTRUCT The number of blocks and the block structure vector The SDPA M handles block diagonal matrices as we have seen in Section 4 In terms of the number of blocks denoted by nBLOCK and the block structure vector denoted by bLOCK sTRUCT we express a common matrix data structure for the constraint matrices Fo F1 Fm If we deal with a block diagonal matrix F of the form F B B OO O OBO 0 A pT a O A 1 OOO Be a pi X pi Symmetric matrix i 1 2 2 we define the number nBLOCK and the block structure vector LLOCKsTRCTURE as fol lows nBLOCK bLOCKsTRUCT pi For example if F is of the form we have If l B1 Ba a Be pi if B is a pi x pi symmetric matrix p if B is a p x pi diagonal matrix O OT OJO MN o ojlo oO oe N O OTD Oos ow O O N e ej o o Oo O Ol NO O O O AJo oOo O O DUO OOO O O SS nBLOCK 3 and bLOCKsTRUCT 3
9. Binary Package ei aui a A A AS E as 1 22 Source Package 2 neg aca A a a cies 2 2 3 Using Self compiled ATLAS and CLAPACK 5 2A After Installati no e rs a a ee eet 6 Semidefinite PrograM e 6 3 1 Standard Form SDP and Its Dual o e 6 2 gt Example Wis Sek ee gt A A A Se ee A A et 7 30 obixample 2 es art A A BEL eee te be ee 8 Quick Stars is Oy mn ety cea Be Ue E oa eaves Ae i wh ince pecan A as 8 Problem Data Tnp t ies ENANA 10 Dil TnputeAreiiments 2000 xeon eee we hae pa ed oie Maar oe De ee a 10 52 File Input a 4 E ee be A a aS 12 5 3 Dense Input Data File 0 020 020 2000 00 13 5A Sparse InputiBlle itv pert ait ie wg ee a a Se A o 16 Initial Point mp AI A Ea eS A 17 6 1 t TnitialsPoint e lt RE OE ee BY ee AA E ki 6 2 Bale Mput recse ne ah ene a ee Woe il ech ental e des tet 18 6 3 Dense Initial Point File o e e 18 6 4 Sparse Initial Point File e e e 19 Optional Setting erorien AAA AA A EGS 19 TL Option Valde A A A A ri oe 19 7 2 More on Option Value e 21 A RR RN 22 8 1 Output Arguments a iee a o aa e a a 22 8 27 File DUDA ai 22 8 9 Error Message a A A th a Ee ee 25 Sample RUNS ota teo e elo a eE a a Bas A aed 26 SDP Feasibility Problem o o o e 26 10 1 Conversion into Standard Form SDP o 26 10 2
10. If you finish the above operations successfully read Section 2 4 to complete the installation If you have a problem in compiling source files please check your mex command path as in the Linux installation guide 2 3 Using Self compiled ATLAS and CLAPACK For installing the self compiled ATLAS and CLAPACK version you have to install SDPA version 6 2 0 beforehand and please check that the installation of SDPA was correctly done For installing this package download the following package from the above site e sdpam 6 2 0 src tar gz To extract the package enter tar zxvf sdpam 6 2 0 src tar gz To install the package you have to change 2 Makefiles At the top directory of the package you can find Makefile and there is a line Line 12 INSTALL_DIR HOME work sdpam In this line you can select the directory in which you want to install SDPA M Therefore if you want to install it in home user1 matlab sdpam replace this line with INSTALL _DIR home user1 matlab sdpam Next in mex directory you can find Make extatlas Copy this file to Makefile that is cp Make extatlas Makefile There are 2 lines to modify in this file Line 7 LAPACK HOME lapack Line 8 SDPA HOME sdpa Each line implies where ATLAS CLAPACK and SDPA exist For example if you installed ATLAS and CLAPACK in home user1 lapack and SDPA in home user1 sdpa Replace these lines with LAPACK home user1 lapack SDP
11. m constraint matrices OES the zero matrix C1 T c ER a cost vector R a variable vector Cm Tm XES Y ES variable matrices UeV the inner product of U VES i e y y Ui Vij i 1 j 1 U gt O lt U S is positive semidefinite Throughout this manual we denote the primal dual pair of P and D by the SDP The SDP is determined by m n c R F S i 0 1 2 m When a X is a feasible solution or a minimum solution respectively of the primal problem P and Y is a feasible solution or a maximum solution respectively of the dual problem D we call a X Y a feasible solution or an optimal solution respectively of the SDP We assume Condition 1 1 F 1 2 m CS is linearly independent If the SDP did not satisfy this assumption it might cause some trouble numerical instability that would abnormally stop the execution of the SDPA M If we deal with a different primal dual pair of P and D of the form P minimize AgeX subject to Aj e X b i 1 2 m S gt X gt 0 m SDP D maximize SS biyi La subject to S Ay Z Ap S gt Z gt 0 1 we can easily transform the SDP into the SDP as follows 4 R A i 0 m F i TA 0 mM b i 1 m gt i 1 mM X Y y Tr Z X Ne i 3 2 Example 1 P minimize 48y1 8y2 20y3 10 4 0 0 0 8 o A subject to x 4 SERIE ajet s 3 ae 0 A X gt O
12. recommend to take a sufficiently large lambdaStar such that X lt lambdaStar x I and Y lt lambdaStar x I e omegaStar This parameter determines the region in which the SDPA M searches an optimal solution For the primal problem P the SDPA M searches a minimum solution a X within the region O lt X lt omegaStar x X omegaStar x lambdaStar x T 20 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 M 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 larger lambdaStar and a smaller omegaStar gt 1 lowerBound Lower bound of the minimum objective value of the primal problem P When m the SDPA M generates a primal feasible solution a X whose objective value gt car i 1 gets smaller than the lowerBound the SDPA M 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 M generates a dual feasible solution Y whose objective value Foe Y gets larger than the upperBound the SDPA M stops the iteration the dual problem D is likely to be u
13. tab code s we can use the letters E E to separate elements of the block structure vector LLOCKsTRUCT We have 1 2 nBLOCK bLOCKsTRUCT in Example 1 see the file examplel dat in Section 5 3 and 14 nBLOCK 3 2 3 2 bLOCKsTRUCT in Example 2 see the file example2 dat in Section 5 3 In either case the letters nBLOCK and LLOCKsTRUCT are neglected c In addition to blank letter s and tab code s we can use the letters gt ae 3 to separate elements of the vector c We have 148 8 20 in Example 1 see the file examplel dat in Section 5 3 and 1 1 10 6 6 19 4 1 in Example 2 see the file example2 dat in Section 5 3 F In addition to blank letter s and tab code s we can use the letters E E ee to separate elements of the matrices Fo F1 Fm and their elements In the general case of the block diagonal matrix F given in 1 we write the elements of B1 B2 Bi sequentially when B is a diagonal matrix we write only the diagonal element sequentially If the matrix F is given by 2 aBLOCK 3 LLOCKsTRUCT 3 2 2 the corresponding representation of the matrix F turns out to be 1 2 3 2 4 5 3 5 6 1 2 2 3 4 53 In Example 1 with nBLOCK 1 and LLOCKsTRUCT 2 we have 11 0 0 23 10 4 14 0 0 0 0 8 0 8 8 2 See the file examplel dat in Section 5 3 In Examp
14. 01 9 8e 01 1 1e 00 1 00e 01 phase value pdOPT Iteration 14 9277516936612115e 09 9638726311832500e 08 gap 1 9638758468306057e 08 digits 7 6501264737392791e 00 mu 3 1 1 7 objValPrimal 8 7748519224301846e 01 8 8 1 relative gap objValDual 8 7748517260429215e 01 p feas error 8 1712414612411521e 14 d feas error 1 9984014443252818e 15 Since t gt 0 we conclude that this problem is not feasible as we expected 29 References 1 M Kojima K Fujisawa K Nakata and M Yamashita SDPA SemiDefinite Programming Algorithm User s Mannual Version 6 20 Research report Dept of Mathematical and Computing Sciences Tokyo Institute of Technology 2 12 1 W8 29 Oh Okayama Meguro ku Tokyo 152 8552 Japan 2005 Available via the WWW site at http grid r dendai ac jp sdpa 2 J L fberg YALMIP A toolbox for modeling and optimization in MATLAB In Proceedings of the CACSD Conference Taipei Taiwan 2004 Available from http control ee ethz ch joloef yalmip php 3 M J Todd Semidefinite optimization Acta Numerica 10 515 560 2001 4 L Vandenberghe and S Boyd Semidefinite programming SIAM Review 38 49 95 1996 30
15. A home user1 sdpa The last step is to compile and install these files After moving the top directory enter make make install If you finish the above operations successfully read Section 2 4 to complete the installation If you have a problem in compiling source files please check your mex command path as in the Linux installation guide 2 4 After Installation After installing the necessary files we recommend you to add the path for SDPA M to the MAT LAB search path by adding the following line addpath lt INSTALL_DIR gt to MATLAB toolbox local startup m for Windows and to HOME matlab startup m for Linux Solaris or Mac OS X Here lt INSTALL_DIR gt means the path in which you installed SDPA M and MATLAB is the folder in which MATLAB is installed For examples if you installed SDPA M in home user1 matlab sdpam add the line into HOME matlab startup m addpath home user1 matlab sdpam Now you have completed the installation of SDPA M Check whether the installation is finished successfully by solving a simple SDP See Section 4 3 Semidefinite Program 3 1 Standard Form SDP and Its Dual The SDPA M solves the following standard form semidefinite program 3 4 and its dual Here P minimize 2 Gti i 1 SDP subject to X X Fizi Fo S gt X gt 0 i 1 D maximize FoeY subject to F e Y c i 1 2 m S gt Y gt 0 S the set of n x n real symmetric matrices F S 0 1 2
16. Examples Genui o ada ld A a ts a tow ett 27 1 What s New SDPA M version 6 2 0 provides the MATLAB interface for SDPA version 6 2 0 The big change from the previous version is that users don t have to install ATLAS and CLAPACK anymore users can use the built in LAPACK and BLAS in MATLAB We still provide the version which uses the self compiled ATLAS and CLAPACK as the previous versions But we only support the Linux system for the self compiled ATLAS and CLAPACK version Another change from the previous version is that param m is written as M function instead of M script The change of the interface is only in this part and we checked that YALMIP 2 worked correctly in its test program YALMIP provides an advanced MATLAB interface for using several numerical optimization programs and SDPA M is one of the solvers which YALMIP supports Finally we added gensdpafile m for reducing our support difficulties This new function creates an SDP problem file with SDPA sparse format For example after users create an SDP problem in MATLAB with mDIM nBLOCK bLOCKsTRUCT c F variables users create an SDP problem file with SDPA sparse format by gt gt gensdpafile sdp dat s mDIM nBLOCK bLOCKsTRUCT c F Users can find the file sdp dat s in the current directory Sending this file to us will make our support easier 2 Installation The SDPA M package is available at the following WWW site http grid r dendai ac j
17. HOME work sdpam In this line you can select the directory in which you want to install SDPA M Therefore if you want to install it in home user1 matlab sdpam replace this line with Line 12 INSTALL _DIR home user1 matlab sdpam Next in mex directory you can find Make linux Copy this file to Makefile that is cp Make linux Makefile The last step is to compile and install these files After moving the top directory enter make make install If you finish the above operations successfully read Section 2 4 to finish the installation com pletely If you have a problem in compiling source files please check that the command path for mex command exists To check it out enter which mex If there is no path modify Makefile in mex directory Line 7 MEX mex For example if your mex command exists in opt matlab bin modify it as MEX opt matlab bin mex and repeat make make install gt Solaris Download the following package from the above site e sdpam 6 2 0 src tar gz To extract the package enter gzip cd sdpam 6 2 0 src tar gz tar xvf To compile source files you need SUN C compiler So if you don t have the compiler please use a binary package After extracting the package you have to modify 2 Makefiles First in the top directory you can find Makefile and there is a line Line 12 INSTALL_DIR HOME work sdpam In this line you can se
18. NNNNE l 00 Compare the dense input data file examplel dat described in Section 5 3 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 Each line of the rest 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 F s is 8 In general the structure of a sparse input data file is as follows Title and Comment m the number of the primal variables x s nBLOCK the number of blocks bLOCKsTRUCT the block structure vector c s b iy ji 01 82 ba i2 ja va Sp bp tp Jp Up Sq bq tq Ja Va Here sp 0 1 Mm bp 1 2 0BLOCK 1 lt ip jp and vp E R Each line sp bp ip Jp Up means that the value of the ip jp th element of the bpth block of the constant matrix F is Up 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 byth block are described in the file If the byth block is an x diagonal matrix then ip jp must satisfy 1 lt ip jp lt l 6 Initial Point Input 6 1 Initial Point If a feasible interior soluti
19. OCK bLOCKsTRUCT c F The output from SDPA M is as follows SDPA library start built at May 23 2005 14 54 57 mu thetaP thetaD objP objD alphaP alphaD O 1 0e 04 1 0e 00 1 0e 00 0 00e 00 1 00e 02 1 0e 00 9 0e 01 1 1 4e 03 2 8e 16 1 0e 01 1 39e 02 9 60e 00 9 0e 01 9 0e 01 2 2 3e 02 2 8e 16 1 1e 02 1 73e 02 9 19e 01 2 6e 00 8 6e 01 3 4 6e 01 2 8e 16 1 5e 03 1 64e 01 4 21e 02 1 9e 00 9 0e 01 4 7 8e 00 5 6e 16 1 6e 04 7 37e 01 8 98e 01 9 3e 00 8 9e 01 5 3 5e 00 7 0e 15 1 7e 05 8 26e 01 9 87e 01 9 0e 01 9 0e 01 6 5 8e 01 9 8e 15 1 8e 06 3 62e 01 9 99e 01 1 1e 00 9 0e 01 7 7 8e 02 9 1e 15 1 8e 07 9 36e 01 1 00e 00 1 2e 00 9 0e 01 8 1 1e 02 1 4e 14 1 8e 08 9 94e 01 1 00e 00 1 4e 00 9 0e 01 9 1 6e 03 1 7e 14 1 8e 09 9 99e 01 1 00e 00 1 8e 00 9 0e 01 10 2 4e 04 1 8e 14 1 8e 10 1 00e 00 1 00e 00 3 8e 00 9 0e 01 11 5 4e 05 5 6e 14 1 8e 11 1 00e 00 1 00e 00 6 0e 00 9 0e 01 12 8 0e 06 7 2e 14 1 8e 12 1 00e 00 1 00e 00 8 9e 01 8 9e 01 13 1 4e 06 1 2e 14 1 9e 13 1 00e 00 1 00e 00 1 1e 00 9 0e 01 14 2 0e 07 7 3e 14 2 0e 14 1 00e 00 1 00e 00 1 1e 00 9 0e 01 phase value pdOPT Iteration 14 mu 1 9969468324606384e 07 relative gap 7 8366267142193635e 08 28 beta 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 gap 9 9847341623031924e 07 digits 7 1058708226647997e 00 objValPrimal 9 9999992160167883e 01 obj
20. Research Reports on Mathematical and Computing Sciences Series B Operations Research Department of Mathematical and Computing Sciences Tokyo Institute of Technology 2 12 1 W8 29 Oh Okayama Meguro ku Tokyo 152 8552 Japan SDPA M SemiDefinite Programming Algorithm in MATLAB User s Manual Version 6 2 0 K Fujisawa Y Futakata M Kojima S Matsuyama S Nakamura K Nakata and M Yamashita B 359 January 2000 Revised May 2005 Abstract The SDPA M Semidefinite Programming Algorithm in MATLAB Version 6 2 0 is a MATLAB interface of the SDPA Version 6 2 0 1 which is known as a fast and numerically stable solver for SDPs semidefinite programs 3 4 The SDPA M inherits various features from the SDPA Particularly the SDPA M can read SDPA dense and sparse format input data files of SDPs In addition users can easily manipulate and transform their own problems in the MATLAB language and then solve them by the SDPA M This manual and the SDPA M can be found at the WWW site http grid r dendai ac jp sdpa Key words Semidefinite Programming Interior Point Method Computer Software MATLAB x email fujisawa r dendai ac jp b email YoshiakiFutakata virginia edu e mail kojimaQis titech ac jp t email knakataQ me titech ac jp i e mail Makoto YamashitaQie kanagawa u ac jp Contents 10 What s NWE 6624 8 F525 HS oO aE OSE ORR SERS EOE E SS 1 Tnstallation io pe rd leia se ae als o lada ee 1 2 1
21. ValDual 9 9999999996794597e 01 p feas error 7 3980821468921931e 12 d feas error 1 7688923188844278e 11 Since t lt 0 see a value of objValPrimal in the above result we conclude that the original problem is feasible On the other hand if we choose 01 a 34 which has positive eigenvalues A 1 3 we obtain SDPA library start built at May 23 2005 14 54 57 mu thetaP thetaD objP objD alphaP alphaD beta O 1 0e 04 1 0e 00 1 0e 00 0 00e 00 1 00e 02 1 0e 00 9 0e 01 2 00e 01 1 1 4e 03 1 4e 19 1 0e 01 1 40e 02 9 80e 00 9 0e 01 9 0e 01 2 00e 01 2 2 1e 02 2 8e 16 9 7e 03 1 84e 02 1 21e 00 9 3e 01 9 3e 01 2 00e 01 3 4 9e 01 5 6e 16 6 4e 04 1 84e 02 3 07e 01 1 1e 00 1 0e 00 2 00e 01 4 8 5e 00 8 4e 16 1 6e 19 4 26e 01 2 70e 01 9 6e 01 1 4e 01 1 00e 01 5 1 1e 00 8 0e 16 1 0e 17 6 11e 00 6 33e 01 9 5e 01 9 7e 00 1 00e 01 6 1 4e 01 8 0e 16 8 3e 17 1 45e 00 7 23e 01 9 6e 01 1 0e 00 1 00e 01 7 1 9e 02 8 1e 16 1 1e 18 9 41e 01 8 47e 01 9 5e 01 9 8e 01 1 00e 01 8 2 5e 03 8 1e 16 3 2e 19 8 86e 01 8 73e 01 9 4e 01 1 0e 00 1 00e 01 9 3 3e 04 8 1e 16 1 7e 18 8 79e 01 8 77e 01 9 7e 01 1 1e 00 1 00e 01 10 3 6e 05 8 1e 16 2 7e 18 8 78e 01 8 77e 01 9 7e 01 1 1e 00 1 00e 01 11 3 8e 06 8 1e 16 1 1e 18 8 77e 01 8 77e 01 9 7e 01 1 1e 00 1 00e 01 12 3 9e 07 8 1e 16 1 3e 18 8 77e 01 8 77e 01 9 8e 01 1 1e 00 1 00e 01 13 3 9e 08 8 1e 16 4 3e 18 8 77e 01 8 77e 01 9 8e 01 1 1e 00 1 00e 01 14 3 9e 09 8 1e 16 2 9e 18 8 77e 01 8 77e
22. ave a name with the postfix ini s for example problem ini are legitimate names for sparse initial point data files The SDPA M ini from a dense initial point data s and example ini s distinguishes a sparse initial point data file with the postfix file with the postfix ini s In general the structure of a sparse initial point data file is as follows x s b 41 j U1 s2 ba i2 ja va Sp bp ip jp Up Sq ba ig Ja Yq Here sp 1 or 2 bp 1 2 nBLOCK 1 lt ip lt jp and vp R When sp 1 each line Sp bp ip jp Up means that the value of the ip jp th element of the bpth block of the constant matrix X is vp 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 Up If the bpth block is an x symmetric non diagonal matrix then ip jp must satisfy 1 lt ip lt jp lt l hence only nonzero elements in the upper triangular part of the bpth block are described in the file If the b th block is an x diagonal matrix then ip jp must satisfy 1 lt ip jp lt 7 Optional Setting 7 1 Option Value We can specify various parameters before an execution of SDPA M s its name indicates OPTION can be omitted as input argument see Section 9 In that case the default values are used First we show the default option values below Then each element is explained 19 OPTI
23. bLOCKsTRUCT gt gt gt gt next command is to redirect the output into the file named examplel out gt gt default output is on display gt gt OPTION param print examplel out gt gt gt gt solve the problem using sdpam gt gt objVal x X Y INFO sdpam mDIM nBLOCK bLOCKsTRUCT c F x0 X0 Y0 OPTION Now we have output arguments objVal x X Y INFO and generated an output file named exam plel out To see the file examplel out gt gt type examplel out SDPA library start built at May 23 2005 14 54 57 mu thetaP thetaD objP objD alphaP alphaD beta O 1 0e 04 1 0e 00 1 0e 00 3 20e 01 4 19e 01 1 0e 00 9 1e 01 2 00e 01 1 1 6e 03 1 0e 16 9 4e 02 8 39e 02 7 51e 01 2 3e 00 9 6e 01 2 00e 01 2 1 7e 02 1 9e 16 3 6e 03 1 96e 02 3 74e 01 1 3e 00 1 0e 00 2 00e 01 3 1 8e 01 1 6e 16 2 2e 17 6 84e 00 4 19e 01 9 9e 01 9 9e 01 1 00e 01 4 1 9e 00 1 6e 16 1 5e 17 3 81e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 5 1 9e 01 1 6e 16 1 5e 17 4 15e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 6 1 9e 02 1 6e 16 7 5e 18 4 19e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 7 1 9e 03 1 6e 16 5 8e 16 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 8 1 9e 04 1 8e 16 2 2e 17 4 19e 01 4 19e 01 1 0e 00 9 0e 01 1 00e 01 9 1 9e 05 1 5e 16 3 1e 15 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 10 1 9e 06 1 6e 16 2 2e 17 4 19e 01 4 19e 01 1 0e 00 1 0e 00 1 00e 01 phase value pdOPT Iteration 10 mu 1 9180668442025276e
24. ckage you need Microsoft C compiler therefore if you don t have the compiler please install a binary package After unzipping the package run a command prompt application and move to mex folder in sdpam which is the top folder of this package If you are in the folder sdpam enter cd mex Before compiling the package please see the line 11 in Make win32 It is a folder name where you installed MATLAB Line 11 MATLAB_ROOT C AMATLAB7 If you installed MATLAB in C Program Files MATLAB7 modify it as Line 11 MATLAB_ROOT C Program Files MATLAB7 After checking that the line 11 in Make win32 is correct to compile source files enter nmake f Make win32 If you finish the compile successfully you can find mexsdpam d11 in the same folder Next step is to copy the following 6 files into the folder in which you want to install SDPA M gensdpafile m initial_point m param m read_data m sdpam m mexsdpa dll Note that M files are in the top folder of the package but MEX file is in the mex folder After copying these files read Section 2 4 to finish the installation completely gt Linux Download the following package from the above site e sdpam 6 2 0 src tar gz To extract the package enter tar zxvf sdpam 6 2 0 src tar gz After extracting the package you have to modify 2 Makefiles First in the top directory you can find Makefile and there is a line Line 12 INSTALL_DIR
25. double Columns 5 through 6 2x2 double 2x2 double 3x3 double 3x3 double 2x1 double 2x1 double Note that the diagonal blocks the third block of each column in the above are expressed as vectors Sparse matrices are also available as input In this case input can be only the upper or lower triangular part of the block In Example 2 gt gt F 1 1 ans 1 1 1 4000 1 2 3 2000 2 2 28 0000 is the correct input of 1 1 th element of F Diagonal blocks are expressed as symmetric matrices like non diagonal blocks Dense matrices and sparse matrices can be used simulta neously gt gt F 2x2 sparse 2x2 double 2x2 double 2x2 double is legitimate as input F of Example 1 At the end the empty cell is assumed to be a zero matrix 5 2 File Input As we have seen in Section 4 we can input data of an SDP from files Use read data function to read data files There are two types of input data file formats One is the dense format and the 12 other is the sparse format The function read_data recognizes the file extension dat s or dat automatically So both gt gt mDIM nBLOCK bLOCKsTRUCT c F read_data examplel dat and gt gt mDIM nBLOCK bLOCKsTRUCT c F read_data examplel dat s are allowed Next two sections explain the dense and sparse formats for input data 5 3 Dense Input Data File e examplel dat Input Data File of Example 1 Exampl
26. e 1 mDim 3 nBLOCK 1 12 3 mDIM 1 nBLOCK 2 bLOCKsTRUCT 48 8 20 11 0 0 23 10 4 4 0 0 0 0 8 _ 0 8 8 2 e 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 4 3 2 3 2 28 15 12 2 1 12 16 3 8 2 1 3 8 15 Y 1 8 4 0 4 0 5 5 2 5 2 5 3 7 8 2 4 6 0 2 4 4 2 6 5 6 0 6 5 2 1 4 4 5 3 5 13 Ah 6 5 5 4 5 4 6 6 6 7 7 2 3 6 7 2 7 3 3 0 3 6 3 0 1 4 7 6 1 1 5 In general the structure of an input data file is as follows Title and Comment m the number of the primal variables z s nBLOCK the number of blocks bLOCKsTRUCT the block structure vector c Fo Fy Fm Title and Comment This part is ignored by read data function mDIM 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 199 in the file example2 dat In either case the letters mDIM are neglected nBLOCK bLOCKsTRUCT We separately write each of nBLOCK and LLOCKsTRUCT 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
27. e case of c 0 First of all the SDP feasibility problem is defined by find ER such that X X Fizi Fo S3X O 3 i l where 2 t2 m and z R for all i This problem can be converted into the standard form SDP by introducing a slack variable t such as m minimize t subject to X y Fix Fo tI S gt X gt 0 4 i 1 Therefore x and c become x 1 m t T e 0 0 1 7 By solving the problem 4 if we obtain t lt 0 then we conclude that the problem is feasible But to solve the problem 4 by SDPA M we have to add one more constraint which gives a lower bound of t otherwise we will find a numerical problem For choosing the lower bound of 26 t the most natural one is t gt 1 Although changing the lower bound of t makes the solution different the solution itself is not important as long as a sign of the solution t doesn t change Therefore in practice instead of solving the problem 3 directly we solve the problem m minimize t subject to X 3 Fiz Fo tl S gt X gt 0 t gt 1 5 i 1 10 2 Example Let us consider the following feasibility problem of the linear matrix inequalities find X R such that XA A X lt 0 X gt O 6 where A R is given It is known that if the real part of all eigenvalues of A are negative then there exists X this is nothing but a Lyapunov stability condition To avoid the numerical problem we replace X gt 0 with X gt I in 6
28. ely the SDPA M has stopped generating a dual feasible solution Y such that objD Foe Y gt upperBound 24 Iteration The iteration number which the SDPA M needs to terminate relative gap The relative gap means that lobjP objD max 1 0 JobjP JobjD 2 This value is compared with epsilonStar Section 7 gap The gap means that mu x n digits This value indicates how objP and objD resemble by the following definition lobjP objD digits lo E 10 objP objD 2 0 y log oie Ceti Foe Y 1 OE ceil Fo e Y1 2 0 objValPrimal The primal objective function value m objValPrimal y Cit i 1 objValDual The dual objective function value objValDual Foe Y p feas error This value is the primal infeasibily in the last iteration m D Fiz X Folp q i 1 p feas error max p9 12 0 This value is compared with epsilonDash Section 7 Even if primal is feasible this value may not be 0 because of numerical error d feas error This value is the dual infeasibily in the last iteration d feas error max F e Y c i 1 2 m This value is compared with epsilonDash Section 7 Even if dual is feasible this value may not be 0 because of numerical error Error Message During a computation if there is a message such as e Step length is too small or e cholesky miss condition not positive definite
29. file contains the data x x y in this order where the description of the m dimensional vector x must follow the same format as the constant vector c see Section 5 3 and the description of X and Y the same format as the constraint matrix F see Section 5 3 We show below the file examplel ini which contains an initial point data of Example 1 in the dense data format 0 0 4 0 0 0 11 0 0 0 0 0 9 0 5 9 1 375 1 375 1 0 18 6 4 Sparse Initial Point File We show below the file examplel ini s which contains an initial point data of Example 1 in the sparse data format 0 0 4 0 0 0 111111 11229 21115 9 2 1 1 2 1 375 2i 22i Compare the dense initial point file examplel ini described in Section 6 3 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 examplel ini which describes 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 Ist block of the matrix Y is 1 375 A sparse initial point file must h
30. le 2 with nBLOCK 3 and bLOCK sTRUCT 2 3 2 we have 1 4 3 2 3 2 28 qed IS 125 2 12 16 3 C 213 Be 15 1 8 4 0 15 0 5 5 2 5 2 5 3 7 8 2 4 6 0 2 4 4 2 6 5 6 0 6 5 Zed CH 4 5 3 5 6 5 5 4 5 4 6 6 6 7 7 2 3 6 7 2 7 3 3 0 3 6 3 0 1 4 6 1 1 5 Remark We could also write the input data of Example 1 without using any letters aoe Joia such as Example 1 mDim 3 nBLOCK 1 2 3 1 2 48 8 20 11 0 0 23 10 4 4 0 0 0 0 8 0 8 8 2 5 4 Sparse Input File In the previous subsection we have stated the dense data format for inputting the data m n c R and F S i 0 1 2 m When not only the constant matrices F S i 0 1 2 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 We show below the file examplel dat s which contains the data of Example 1 Section 3 2 in the sparse data format 16 Example 1 mDim 3 nBLOCK 1 42 3 mDIM 1 nBLOCK 2 bLOCKsTRUCT 48 8 20 1 1 11 2 23 WWNrRHrR OO RRA 1 2 al 1 2 1 2
31. lect the directory in which you want to install SDPA M Therefore if you want to install it in home user1 matlab sdpam replace this line with INSTALL_DIR home user1 matlab sdpam Next in mex directory you can find Make solaris Copy this file to Makefile that is cp Make solaris Makefile The last step is to compile and install these files After moving the top directory enter make make install solaris If you finish the above operations successfully read Section 2 4 to complete the installation If you have a problem in compiling source files please check your mex command path as in the Linux installation guide gt Mac OS X Download the following package from the above site e sdpam 6 2 0 src tar gz To extract the package enter tar zxvf sdpam 6 2 0 src tar gz After extracting the package you have to modify 2 Makefiles First in the top directory you can find Makefile and there is a line Line 12 INSTALL _DIR HOME work sdpam In this line you can select the directory in which you want to install SDPA M Therefore if you want to install it in home user1 matlab sdpam replace this line with INSTALL_DIR home user1 matlab sdpam Next in mex directory you can find Make macX Copy this file to Makefile that is cp Make macX Makefile The last step is to compile and install these files After moving the top directory enter make make install
32. nbounded and the primal problem P is likely to be infeasible if the upperBound is sufficiently large betaStar A parameter controlling the search direction when a X Y is feasible As we take a smaller betaStar gt 0 0 the search direction can get close to the affine scaling direction without centering betaBar A parameter controlling the search direction when X Y is infeasible As we take a smaller betaBar gt 0 0 the search direction can get close to the affine scaling direction without centering The value of betaBar must be not less than the value of betaStar O lt betaStar lt betaBar gammaStar A reduction factor for the primal and dual step lengths 0 0 lt gammaStar lt 1 0 isSymmetric a 0 1 flag indicating whether to check the symmetricity of input matrices print Destination of file output gt gt OPTION print display to have file output on display filename to have file output on the file named filename no to have no file output More on Option Value We may encounter some numerical difficulty during the execution of the SDPA M with the default option values set by param m 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 option values betaStar betaBar and gammaStar We present below two sets of those option values The one is the set Stable but Slow for difficult SDPs and
33. on 2 X Y is known in advance we may want to start the SDPA M from 2 X Y 9 In such a case we can optionally specify the feasible interior solution as initial 17 point It is often the case that such an initial point is not known or you want to execute without any initial point In such case an initial point can be omitted as an input argument see Section 9 e x Initial point of P mDIMx1 vector e X Initial point of P nBLOCKx1 cell matrix e Y Initial point of D nNBLOCKx1 cell matrix 0 can be a column vector Like F in Section 5 1 each cell of X and Y can be dense or sparse In case of using sparse matrices input only the upper or lower triangular part Sparse cell and dense cell can be used simultaneously x 6 2 File Input We can import an initial point from a file by using initiall point function An initial point file also has dense or sparse format As the initial_point function reads an initial point from a file it recognizes the file extension ini and ini s Both gt gt x0 X0 Y0 initial_point example1 ini mDIM nBLOCK bLOCKsTRUCT and gt gt x0 X0 Y0 initial_point examplel ini s mDIM nBLOCK bLOCKsTRUCT are allowed 6 3 Dense Initial Point File In general an initial point file can have any name with the postfix ini or ini s for example example ini is a legitimate initial point filename An initial point
34. p sdpa You can select both the binary and source packages If you are not good at compiling source files please download the binary package In the following explanation we write the command prompt as 2 1 Binary Package gt Windows Download the following package from the above site e sdpam 6 2 0 bin zip After unzipping the package copy the following 6 files into the folder in which you want to install SDPA M gensdpafile m initial_point m param m read_data m sdpam m mexsdpa dll After copying these files read Section 2 4 to finish the installation completely gt Linux Solaris or Mac OS X Download the following package from the above site e sdpam 6 2 0 bin tar gz To extract the package if your system is Linux or Mac OS X enter tar zxvf sdpam 6 2 0 bin tar gz and if your system is Solaris enter gzip cd sdpam 6 2 0 bin tar gz tar xvf To install SDPA M for your system enter cd sdpam bin sh install sh lt INSTALL_DIR gt Replace lt INSTALL_DIR gt with the directory name in which you want to install SDPA M For example if you want to install SDPA M in home user1 matlab sdpam enter cd sdpam bin sh install sh home user1 matlab sdpam When you finish the above operations read Section 2 4 to finish the installation completely 2 2 Source Package gt Windows Download the following package from the above site e sdpam 6 2 0 src zip Note that to compile this pa
35. ras 11 0 D maximize 0 A 10 4 0 0 subject to 4 7 Ys de 2 Y 0 8 gt e e 20 Y gt O Here 48 m 3 n 2 c 8 oe a 20 10 4 4 0 8 Fy _9 1D 19 23 The data see Section 5 3 of this problem is contained in the file examplel dat 3 3 Example 2 1 1 10 m 5 n 7 c 6 6 19 4 1 1 4 3 2 0 0 0 0 0 3 2 28 0 0 0 0 0 0 0 15 12 2 1 0 0 Fo 0 o 12 16 3 8 0 0 0 0 21 3 8 15 0 0 0 0 0 0 0 1 8 0 0 0 0 0 0 0 4 0 0 5 5 2 0 0 0 0 0 9 2 5 3 0 0 0 0 0 0 0 7 8 2 4 6 0 0 0 Fy 0 0 2 4 4 2 6 5 0 0 0 0 6 0 6 5 2 1 0 0 0 0 0 0 0 4 5 0 0 0 0 0 0 0 3 5 6 5 5 4 0 0 0 0 0 5 4 6 6 0 0 0 0 0 0 0 6 7 72 3 6 0 0 F 0 0 7 2 7 3 3 0 0 0 0 0 36 3 0 1 4 0 0 0 0 0 0 0 6 1 0 0 0 0 0 0 o 1 5 As shown in this example the SDPA M handles block diagonal matrices The data see Sec tion 5 3 of this example is contained in the file example2 dat 4 At first let s take a simple example to confirm that SDPA M is correctly installed and to know Quick Start the basic usage of SDPA M gt gt read a problem data from the data file example1 dat gt gt mDIM nBLOCK bLOCKsTRUCT c F read_data examplel dat gt gt gt gt read an initial point from the initial point file examplel ini gt gt x0 X0 Y0 initial_point example1 ini mDIM nBLOCK
36. the other is the set Unstable but Fast for easy SDPs Stable but Slow 21 OPTION betaStar 0 1 OPTION betaBar 0 2 OPTION gammaStar 0 9 Unstable but Fast OPTION betaStar 0 01 OPTION betaBar 0 02 0 OPTION gammaStar 98 Besides these options the value of lambdaStar which determines an initial point 2 X Y affects the computational efficiency and the numerical stability Usually a larger lambdaStar is safe although the SDPA M may consume a few more iterations 8 Output 8 1 Output Arguments The function sdpam has five output arguments e objVal Objective function value objVal is a 1x2 matrix such as objValP objValD They are objective function value of a standard form SDP problem P and D see Section 3 1 respectively e x Solution of P mDIM x 1 vector e X Solution of P nBLOCK x 1 cell matrix e Y Solution of D nBLOCK x 1 cell matrix e INFO Information about the execution result INFO is a structure including the infor mation noted below phasevalue the status when the iteration stops iteration the number of iterations cputime the total CPU time seconds The value which phasevalue takes is explained in the next section 8 2 File Output By defaults SDPA M shows some information on the display In the case of Example 1 we have SDPA library start built at May 23 2005 14 54 57 mu thetaP thetaD objP objD alphaP alphaD beta O 1 0e 04 1 0e
Download Pdf Manuals
Related Search