next up previous
Next: Sample Runs Up: SDPT3 - a Previous: The main routine

Example files

To solve a given SDP, the user needs to express it in the standard form (1) and (2), and then write a function file, say problem.m, to compute the input data blk,A,C,b,X0,y0,Z0 for the solvers sdp.m or sdphlf.m. This function file may take the form

 function  [blk,A,C,b,X0,y0,Z0] = problem(input arguments).

The user can easily learn how to use this software package by reading the script file demo.m, which illustrates how the solvers sdp.m and sdphlf.m can be used to solve a few SDP examples. The next section shows how sdp.m and sdphlf.m can be used to solve random problems generated by randsdp.m, graph.m, and maxcut.m, and the resulting output, for several of our algorithms.

This software package also includes example files for the following classes of SDPs. In these files, the input variables feas and solve are used as follows:

eqnarray946

If solve is positive, the output variable objval is the objective value of the associated optimization problem, and the output variables after objval give approximately optimal solutions to the original problem and its dual (or possibly indications of infeasibility).

Here are our examples.

(1) Random SDP: The associated M-file is randsdp.m, with initial line

 function   
  [blk,A,C,b,X0,y0,Z0,objval,X,y,Z] = randsdp(de,sp,di,m,feas,solve),

where the input parameters describe a particular block diagonal structure for each tex2html_wrap_inline2161 and C. Specifically, the vector de is a list of dimensions of dense blocks; the vector sp is a list of dimensions of (small) subblocks in a single sparse block; and the scalar di is the size of the diagonal block. The scalar m is the number of equality constraints.

(2) Norm minimization problem:

eqnarray983

where the tex2html_wrap_inline2937 , tex2html_wrap_inline2939 , are tex2html_wrap_inline2941 matrices (possibly complex, in which case x ranges over tex2html_wrap_inline2945 ) and the norm is the matrix 2-norm. The associated M-file is norm_min.m, with initial line

 function   [blk,A,C,b,X0,y0,Z0,objval,x] = 
     norm_min(B,feas,solve),

where tex2html_wrap_inline2949 is a cell array with tex2html_wrap_inline2951 , k = 0,...,m.

(3) Chebyshev approximation problem for a matrix:

  eqnarray997

where the minimization is over the class of monic polynomials of degree m, B is a square matrix (possibly complex) and the norm is the matrix 2-norm. The associated M-file is chebymat.m, with initial line

 function   
   [blk,A,C,b,X0,y0,Z0,objval,p] = chebymat(B,m,feas,solve).

See also igmres.m, which solves an analogous problem with p normalized such that p(0) = 1.

(4) Max-Cut problem:

eqnarray1009

where tex2html_wrap_inline2963 , e is the vector of all ones and B is the weighted adjacency matrix of a graph [6]. The associated M-file is maxcut.m, with initial line

 function  
  [blk,A,C,b,X0,y0,Z0,objval,X] = maxcut(B,feas,solve).

See also graph.m, from which the user can generate a weighted adjacency matrix B of a random graph.

(5) ETP (Educational testing problem):

eqnarray1025

where B is a real tex2html_wrap_inline2973 positive definite matrix and e is again the vector of all ones. The associated M-file is etp.m, with initial line

 function   [blk,A,C,b,X0,y0,Z0,objval,d] = etp(B,feas,solve).

(6) Lovász tex2html_wrap_inline2995 function for a graph:

eqnarray1063

where C is the matrix of all minus ones, tex2html_wrap_inline2999 , and tex2html_wrap_inline3001 , where the (k-1)st edge of the given graph (with m-1 edges) is from vertex i to vertex j. Here tex2html_wrap_inline3011 denotes the ith unit vector. The associated M-file is theta.m, with initial line

 function  
  [blk,A,C,b,X0,y0,Z0,objval,X] = theta(B,feas,solve),

where B is the adjacency matrix of the graph.

(7) Logarithmic Chebyshev approximation problem:

eqnarray1052

where tex2html_wrap_inline2987 is a real tex2html_wrap_inline2989 matrix and f is a real N-vector. The associated M-file is logcheby.m, with initial line

 function   
  [blk,A,C,b,X0,y0,Z0,objval,x] = logcheby(B,f,feas,solve).

(8) Chebyshev approximation problem in the complex plane:

eqnarray1038

where the minimization is over the class of monic polynomials of degree m and tex2html_wrap_inline2979 is a given set of points in the complex plane. The associated M-file is chebyinf.m, with initial line

 function   
  [blk,A,C,b,X0,y0,Z0,objval,p] = chebyinf(d,m,feas,solve),

where tex2html_wrap_inline2981 . See also cheby0.m, which solves an analogous problem with p normalized such that p(0) = 1.

(9) Control and system problem:

eqnarray1075

where tex2html_wrap_inline2937 , tex2html_wrap_inline3017 , are square real matrices of the same dimension. The associated M-file is control.m, with initial line

 function   
  [blk,A,C,b,X0,y0,Z0,objval,P] = control(B,solve),

where tex2html_wrap_inline2949 is a cell array with tex2html_wrap_inline3021 , k = 1,...,L.


next up previous
Next: Sample Runs Up: SDPT3 - a Previous: The main routine