SMCP Documentation
Contents
1. Interface to chordalsolver_esd Returns dictionary with solution solve_cvxopt primalstart dualstart Interface to cvxopt solvers sdp Returns dictionary with solution Note that this simple inter face does not yet specify block structure properly The following example demostrates how to load and solve a problem from an SDPA sparse data file 16 Chapter 5 Feedback and bug reports SMCP Documentation Release 0 3 1 gt gt gt from smcp import SDP gt gt gt P SDP qp611 dat s gt gt gt print P lt SDP n 1600 m 800 nnz 3200 gt qpG11 gt gt gt sol P solve_feas kktsolver chol gt gt gt print sol primal objective 2448 6588977 gt gt gt print sol dual objective 2448 65913565 gt gt gt print sol gap 0 00023794772363 gt gt gt print sol relative gap 9 71747121876e 08 5 3 5 Auxiliary routines smcp completion X Computes the maximum determinant positive definite completion of a sparse matrix X Example gt gt gt from smcp import mtxnorm_SDP completion gt gt gt P mtxnorm_SDP p 10 q 2 r 10 gt gt gt sol P solve_feas kktsolver chol gt gt gt X completion sol x smcp misc ind2sub siz ind Converts indices to subscripts Parameters e siz integer matrix order e ind matrix vector with indices Returns matrix I with row subscripts and matrix J with column subscripts2. Example gt gt gt from smcp import mtxnorm_SDP gt gt gt P mtxnorm_SDP p 200 q 10 r 200 gt gt gt print P lt SDP n 210 m 201 nnz 2210 gt mtxnorm_p200_q10_r200 gt gt gt sol P solve_feas kktsolver qr class base band_SDP n m bwl seed Generates random SDP with band sparsity and m constraints of order n and with bandwidth bw bw 0 cor responds to a diagonal bw 1 is tridiagonal etc Returns SDP object The optional parameter seed sets the random number generator seed Example gt gt gt from smcp import band_SDP gt gt gt P band_SDP n 100 m 100 bw 2 seed 10 gt gt gt print P lt SDP n 100 m 100 nnz 297 gt band_n100_m100_bw2 gt gt gt X plsol P solve_phasel kktsolver qr gt gt gt P solve_feas kktsolver gr primalstart x X gt gt gt print sol primal objective sol dual objective 31 2212701455 31 2212398351 class base rand_SDP V ml densityl seed Generates random SDP with sparsity pattern V and m constraints Returns SDP object The sparsity of A can optionally be chosen by specifying the parameter density which must be a float between 0 and 1 default is 1 which corresponds to dense matrices 5 4 Test problems The SMCP repository contains a number of SDP problem instances that were created with SMCP and have been used for benchmarks The files follow the SDPA sparse data format and are compress
3. smcp misc sub2ind siz I J Converts subscripts to indices Parameters e siz integer tuple matrix size e I matrix row subscripts e J matrix column subscripts Returns matrix with indices smcp misc sdpa_read file_obj Reads data from sparse SDPA data file file extension dat s A description of the sparse SDPA file format can be found in the document SDPLIB FORMAT and in the SDPA User s Manual Example gt gt gt f open qpGl1 dat s gt gt gt A b blockstruct smcp misc sdpa_read f gt gt gt f close 5 3 Documentation 17 SMCP Documentation Release 0 3 1 smcp misc sdpa_readhead file_obj Reads header from sparse SDPA data file and returns the order n the number of constraints m and a vector with block sizes Example gt gt gt f open qpGl1 dat s gt gt gt n m blockstruct smcp misc sdpa_readhead f gt gt gt f close smcp misc sdpa_write file_obj A b blockstruct Writes SDP data to sparse SDPA file Example gt gt gt f open my_data_file dat s w gt gt gt smcp misc sdpa_write f A b blockstruct gt gt gt f closel 5 3 6 Analysis routines smcp analysis embed_SDP PL orderl cholmod 1 Computes chordal embedding and returns SDP object with chordal sparsity pattern Parameters e P SDP SDP object with problem data e order string AMD default or METIS e cholmod boolean use Chol
4. solves the KKT system via a QR factorization The solver returns a dictionary with the following keys primal objective dual objective primal objective value and dual objective value primal infeasibility dual infeasibility residual norms of primal and dual infeasibil ity 12 Chapter 5 Feedback and bug reports SMCP Documentation Release 0 3 1 x s and y primal and dual variables iterations number of iterations cputime time total cputime and real time gap duality gap relative gap relative duality gap status e has the value optimal if lb A X ll2 AY y S Cllr A lt feas lt feas X gt 0 S gt 0 max 1 lola 7 max 1 Cl i and Xes lt j bTy lt lt Xes lt abs Or minc X b y lt 0 anda y 6 e has the value unknown otherwise The following options can be set using the dictionary smcp solvers options delta default 0 9 a positive constant between 0 and 1 an approximate tangent direction is computed when the Newton decrement is less than delta eta default None None or a positive float If eta is a positive number a step in the approximate tangent direction is taken such that Q X aAXxX S aAS mn where Q X S is the proximity function S n Q X S 6 X 0 5 ecto n If eta is None the step length a in the approximate tangent d
5. P and D using an extended self dual embedding This solver is currently experimental The columns of the sparse matrix A are vectors of length n and the m 1 columns of A are vec C vec A1 vec Am Only the rows of A corresponding to the lower triangular elements of the aggregate sparsity pattern V are accessed The optional argument primalstart is a dictionary with the key x which can be used to specify an initial value for the primal variable X Similarly the optional argument dualstart must be a dictionary with keys s and y The optional argument scaling takes one of the values primal default or dual The optional argument kktsolver is used to specify the KKT solver Possible values include chol default solves the KKT system via a Cholesky factorization of the Schur complement qr solves the KKT system via a QR factorization The solver returns a dictionary with the following keys primal objective dual objective primal objective value and dual objective value primal infeasibility dual infeasibility residual norms of primal and dual infeasibil ity x s and y primal and dual variables iterations number of iterations cputime time total cputime and real time gap duality gap relative gap relative duality gap status e has the value optimal if 1 mlrb AO lla lt G DAY y S 7Cllp lt feas lt Efeas X Fel
6. S gt 0 max 1 bll2 max 1 Cl 7 and Xes lt abs or mintes x bT y lt 0 1 T X eS ES min Ce X bTy ae 14 Chapter 5 Feedback and bug reports SMCP Documentation Release 0 3 1 e has the value primal infeasible if 144 y Sle bT Efes S gt 0 i max 1 C e has the value dual infeasible if X CeX 1 ACA ll X gt 0 me ela lt feas e has the value unknown if maximum number iterations is reached or if a numerical error is en countered The following options can be set using the dictionary smcp solvers options show_progress True or False turns the output to the screen on or off default True maxiters maximum number of iterations default 100 abstol absolute accuracy default 1e 6 reltol relative accuracy default 1e 6 feastol tolerance for feasibility conditions default 1e 8 refinement number of iterative refinement steps when solving KKT equations default 1 cholmod use Cholmod s AMD embedding defaults False dimacs report DIMACS error measures default True 5 3 3 Solver interfaces The following functions implement CVXOPT like interfaces to the experimental solver chordalsolver_esd smcp solvers conelp c G Al dims kktsolver chol Interface to chordalsolver_esd smcp solvers 1p c G Al kktsolver chol 1 Interface to cone 1p
7. 0 3 1 Sr is the set of symmetric matrices of order n and with sparsity pattern V i e X Sy if and only if X 0 for all i j 4 V We will assume that all diagonal elements are included in V The projection Y of X on the subspace Sr is denoted Y Py X i e Yi Xi if i j V and Y 0 otherwise The inequality signs and gt denote matrix inequality We define V as the number of nonzeros in the lower triangular part of V and nnz A denotes the number of nonzeros in the matrix A_1 Sr and Sy are the sets of positive semidefinite and positive definite matrices in S and similarly Sy Py X X Of and S e4 Py X X gt 0 are the sets of matrices in S that have a positive semidefinite completion and a positive definite completion respectively We denote with and gt matrix inequality with respect to the cone Sy SMCP solves a pair of primal and dual linear cone programs P minimize CeX D maximize by subjectto A e X b i 1 m subjectto X yidi 8 C X r0 S gt 0 The variables are X S S S and y R and the problem data are the matrix C Sy the vector b R and A S i 1 mM Compositions of cones are handled implicitly by defining a block diagonal sparsity pattern V Dense blocks and general sparse blocks correspond to standard positive semidefinite matrix constraints diagonal blocks corresponds to linear inequality c
8. 184 4 sec thetaG51 M1 64 8 sec Mic 58 0 sec and truss8 M1 17 9 sec Mlc 17 9 sec 5 5 8 Nonchordal sparsity patterns The following problems are based on sparsity patterns from the University of Florida Sparse Matrix Collection UFSMC We use as problem identifier the name rsX where X is the ID number of a sparsity pattern from UFSMC Each problem instance has m constraints and the number of nonzeros in the lower triangle of A is max 1 round 0 005 V where V is the number of nonzeros in the lower triangle of the aggregate sparsity pattern V and C has V nonzeros Experiment 10 5 5 Benchmarks 23
9. matrix is given by max 1 dpq where the parameter d 0 1 determines sparsity The locations of nonzero entries in F are random Thus the problem family is parameterized by the tuple p q r d Experiment 4 variable number of rows p q 10 columns r 100 variables and density d 1 Experiment 5 p 400 rows q 10 columns r 200 variables and variable density 5 5 Benchmarks 21 SMCP Documentation Release 0 3 1 Experiment 6 p 400 rows q 10 columns variable number of variables r and density d 1 Experiment 7 p q 1000 r 10 variables and density d 1 5 5 6 Overlapping cliqes We consider a family of SDPs which have an aggregate sparsity patterns V with cliques of order N The cliques are given by W 1 N u 4 1 1 N u 14 u t 1 1 where u 0 lt u lt N 1 is the overlap between neighboring cliques The sparsity pattern is illustrated below cia gt N 16 n 200 49u Note that u 0 corresponds to a block diagonal sparsity pattern and u N 1 corresponds to a band pattern Experiment 8 m 100 constraints clique size N 16 and variable overlap u 5 5 7 SDPLIB problems The following experiment is based on problem instances from 22 Chapter 5 Feedback and bug reports SMCP Documentation Release 0 3 1 Experiment 9 SDPLIB problems with n gt 500 Three problems required a phase I thetaG11 M1 227 2 sec Mic
10. SMCP Documentation Release 0 3 1 Martin S Andersen and Lieven Vandenberghe August 20 2014 Contents Current release 3 Future releases 5 Availability 7 Authors 9 Feedback and bug reports 11 Dsl COpyrightiand license iv assi ae id A a AA es a eee 11 32 Download and installation s i scs 6 4 4 2 6 44a A EGA E a e a 11 3 3 Doc mematon s sa soc ce 5 Sev oh eke ee wh ew ani he Be ap BBO A Bend oe i 11 DA Test Problems e s ea ie A A be eee 19 3 3 Benchmarks cinc A e ew SGA S 19 SMCP Documentation Release 0 3 1 SMCP is a software package for solving linear sparse matrix cone programs The code is experimental and it is released to accompany the following paper See also 13 S Andersen J Dahl and L Vandenberghe Implementation of nonsymmetric interior point methods for linear optimization over sparse matrix cones Mathematical Programming Computation 2010 The package provides an implementation of a nonsymmetric interior point method which is based on chordal matrix techniques Only one type of cone is used but this cone includes the three canonical cones the nonnegative orthant the second order cone and the positive semidefinite cone as special cases The efficiency of the solver depends not only on the dimension of the cone but also on its structure Nonchordal sparsity patterns are handled using chordal embedding techniques In its current form SMCP is implemented in Python and C and it relies o
11. ed with Bzip2 5 5 Benchmarks To assess the performance of our preliminary implementation of SMCP we have conducted a series of numerical experiments 5 4 Test problems 19 SMCP Documentation Release 0 3 1 5 5 1 SDP solvers The following interior point solvers were used in our experiments Method M1 SMCP 0 3a feasible start solver with kktsolver chol Method Mic SMCP 0 3a feasible start solver with kktsolver chol and solvers options cholmod True Method M2 SMCP 0 3a feasible start solver with kktsolver qr CSDP 6 0 1 DSDP 5 8 SDPA 7 3 1 SDPA C 6 2 1 binary dist SDPT3 4 0b 64 bit Matlab SeDuMi 1 2 64 bit Matlab 5 5 2 Error measures We report DIMACS error measures when available The six error measures are defined as X b e X y S eae 2 X y S max f0 eb 3 X y S an le e4 X y S max o ee es X y S AH co X y S 7 E bTy Here C max max Ci and Co X tr CTX Note that es X y S 0 and 4 X y S 0 since all iterates X y S satisfy X SY and SES 5 5 3 Experimental setup The following experiments were conducted on a desktop computer with an Intel Core 2 Quad Q6600 CPU 2 4 GHz 4 GB of RAM and running Ubuntu 9 10 64 bit The problem instances used in the experiments are available for download here and the SDPLIB problems are available here We use the least norm solution to the set
12. irection is computed as Qp argmax a 0 1 X aAX gt 0 aq argmax a 0 1 S aAS gt 0 a step min ap ag where step is the value of the option step default 0 98 prediction default True True or False This option is effective only when eta is None If prediction is True a step in the approximate tangent direction is never taken but only used to predict the duality gap If prediction is False a step in the approximate tangent direction is taken step default 0 98 positive float between 0 and 1 lifting default True True or False determines whether or not to apply lifting before taking a step in the approximate tangent direction 5 3 Documentation 13 SMCP Documentation Release 0 3 1 show_progress True or False turns the output to the screen on or off default True maxiters maximum number of iterations default 100 abstol absolute accuracy default 1e 6 reltol relative accuracy default 1e 6 feastol tolerance for feasibility conditions default 1e 8 refinement number of iterative refinement steps when solving KKT equations default 1 cholmod use Cholmod s AMD embedding defaults False dimacs report DIMACS error measures default True smcp solvers chordalsolver_esd A bl primalstart dualstart scaling primal kkt solver chol Solves the pair of cone programs
13. mod to compute embedding default is false Returns SDP object with chordal sparsity Note that CVXOPT must be compiled and linked to METIS in order to use the METIS ordering The following routines require Matplotlib smcp analysis spy PI il file scale Plots aggregate sparsity pattern of SDP object P or sparsity pattern of Aj Parameters e P SDP SDP object with problem data e i integer index between 0 and m e file string saves plot to file e scale float downsamples plot smcp analysis clique_hist P Plots clique histogram if P ischordal1 is true and otherwise an exception is raised Parameters P SDP SDP object with problem data smcp analysis nnz_hist P Plots histogram of number of nonzeros in lower triangle of A1 Am Parameters P SDP SDP object with problem data 18 Chapter 5 Feedback and bug reports SMCP Documentation Release 0 3 1 5 3 7 Random problem generators class mtxnorm_SDP p q rl density seed Inherits from SDP class Generates random data F G RP 4 for the matrix norm minimization problem minimize F z Glla with the variable z R and where F z z1 F zrFr The problem is cast as an equivalent SDP minimize t tI F z G F z G tI 0 subject to The sparsity of F can optionally be chosen by specifying the parameter density which must be a float between 0 and 1 default is 1 which corresponds to dense matrices
14. n the Python extensions CHOMPACK and CVXOPT for most computations Contents 1 SMCP Documentation Release 0 3 1 2 Contents CHAPTER 1 Current release Version 0 4 June 16 2014 includes e Nonsymmetric feasible start interior point methods primal and dual scaling methods e Two KKT system solvers one solves the symmetric indefinite augmented system and the other solves the positive definite system of normal equations e Read write routines for SDPA sparse data files dat s e Simple interface to CVXOPT SDP solver SMCP Documentation Release 0 3 1 4 Chapter 1 Current release CHAPTER 2 Future releases We plan to turn SMCP into a C library with Python and Matlab interfaces Future releases may include additional functionality as listed below e Explicitly handle free variables e Iterative solver for the KKT system e Automatic selection of KKT solver and chordal embedding technique SMCP Documentation Release 0 3 1 6 Chapter 2 Future releases CHAPTER 3 Availability The source package is available from the Download and installation section The source package includes source code documentation and installation guidelines SMCP Documentation Release 0 3 1 8 Chapter 3 Availability CHAPTER 4 Authors SMCP is developed by Martin S Andersen and Lieven Vandenberghe SMCP Documentation Release 0 3 1 10 Chapter 4 Au
15. of equations A e X i 1 m as starting point when it is strictly feasible and otherwise we solve the phase I problem minimize s subjectto A eX b i 1 m tr x lt M X s 6 I gt 0 s gt 0 20 Chapter 5 Feedback and bug reports SMCP Documentation Release 0 3 1 Here e is a small constant and the constraint tr X lt M is added to bound the feasible set 5 5 4 SDPs with band structure We consider a family of SDP instances where the data matrices C A1 Am are of order n and banded with a common bandwidth 2w 1 Experiment 1 m 100 constraints bandwidth 11 w 5 and variable order n Experiment 2 order n 500 bandwidth 7 w 3 and variable number of constraints m The problem band_n500_m amp 00_w3 required a phase I M1 311 5 sec M2 47 8 sec Experiment 3 order n 200 m 100 constraints and variable bandwidth 2w 1 Two problems required a phase I band_n200_m100_w0 M1 1 12 sec M2 0 53 sec and band_n200_m100_wl M1 3 18 sec M2 1 45 sec 5 5 5 Matrix norm minimization We consider the matrix norm minimization problem minimize F x Gl2 where F x 214F1 F and G F R are the problem data The problem can be formulated as an SDP minimize t tI Fla G Fo rar u subject to This SDP has dimensions m r 1 and n p q We generate G as a dense p x q matrix and the matrices F are generated such that the number of nonzero entries in each
16. onstraints and second order cone constraints can be embedded in an LMI with an arrow pattern Le T lel lt t e E o 5 3 2 The chordal SDP solvers smcp solvers chordalsolver_feas A bl primalstart dualstart scaling primal kkt solver chol Solves the pair of cone programs P and D using a feasible start interior point method If no primal and or dual feasible starting point is specified the algorithm tries to find a feasible starting point based on some simple heuristics An exception is raised if no starting point can be found In this case a Phase I problem must be solved or the experimental infeasible start interior point method chordalsolver_esd can be used The columns of the sparse matrix A are vectors of length n and the m 1 columns of A are vec C vec A1 vec Am Only the rows of A corresponding to the lower triangular elements of the aggregate sparsity pattern V are accessed The optional argument primalstart is a dictionary with the key x which can be used to specify an initial value for the primal variable X Similarly the optional argument dualstart must be a dictionary with keys s and y The optional argument scaling takes one of the values primal default or dual The optional argument kktsolver is used to specify the KKT solver Possible values include chol default solves the KKT system via a Cholesky factorization of the Schur complement qr
17. see CVXOPT documentation for more information smcp solvers socp cl Gl rll Gq hal kktsolver chol 1 Interface to cone 1p see CVXOPT documentation for more information smcp solvers sdp cl Gl All Gs hsl kktsolver chol 1 Interface to cone 1p see CVXOPT documentation for more information 5 3 4 The SDP object class SDP filename Class for SDP problems Simplifies reading and writing SDP data files and includes a wrapper for chordalsolver_esd The constructor accepts sparse SDPA data files extension dat s and data files created with the save method extension pkl Data files compressed with Bzip2 can also be read extensions dat s bz2 and pkl bz2 m Number of constraints Order of semidefinite variable 5 3 Documentation 15 SMCP Documentation Release 0 3 1 A Problem data sparse matrix of size n x m 1 with columns vec C vec A1 vec Am Only the lower triangular elements of C 41 Am are stored b Problems data vector of length m V Sparse matrix with aggregate sparsity pattern lower triangle nnz Number of nonzero elements in lower triangle of aggregate sparsity pattern nnzs Vector with number of nonzero elements in lower triangle of Ag Am nzcols Vector with number of nonzero columns in A Am issparse True if the number of nonzeros is less than 0 5 n n 1 2 otherwise false ischordal True if aggregate sparsity pat
18. tern is chordal otherwise false get_A i Returns the th coeffiecient matrix A 0 lt i lt m as a sparse matrix Only lower triangular elements are stored write_sdpa mamel compress False Writes SDP data to SDPA sparse data file The extension dat s is automatically added to the filename The method is an interface to sdpa_write If compress is true the data file is compressed with Bzip2 and bz2 is appended to the filename save mame compress False Writes SDP data to file using cPickle The extension pk is automatically added to the filename If compress is true the data file is compressed with Bzip2 and bz2 is appended to the filename solve_feas scaling primal kktsolver chol primalstart dualstart Interface to the feasible start solver chordalsolver_feas Returns dictionary with solution solve_phasel kktsolver chol M 1e5 Solves a Phase I problem to find a feasible primal starting point minimize s subjectto AjeX b i i tr X lt M X s e6 I 0 5 gt 0 yc IM The variables are X S and s R and e Ry is a small constant If s lt e the method returns X which is a strictly feasible starting point in the original problem and a dictionary with information about the Phase I problem If s gt e the method returns None None solve_esd scaling primal kktsolver chol primalstart dualstart
19. thors CHAPTER 5 Feedback and bug reports We welcome feedback and bug reports are much appreciated Please report bugs through our Github repository 5 1 Copyright and license Copyright 2009 2014 M Andersen and L Vandenberghe SMCP is free software you can redistribute it and or modify it under the terms of the GNU General Public License as published by the Free Software Foundation either version 3 of the License or at your option any later version SMCP is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details 5 2 Download and installation 5 2 1 Installation from source The package requires Python version 2 7 or newer To build the package from source the Python header files and libraries must be installed as well as the core binaries SMCP also requires the Python extension modules CVXOPT 1 1 7 or later and CHOMPACK 2 0 or later The entire source package is available here and it includes documentation installation instructions and examples 5 2 2 Installation with pip SMCP can be installed via pip using the following command pip install smcp user 5 3 Documentation 5 3 1 Overview Let S denote the set of symmetric matrices of order n and let and let C e X denote the standard inner product on S 11 SMCP Documentation Release
Download Pdf Manuals
Related Search