What is new in SparsePOP220? August 20, 2009 (1) SDPA can be used to solve the SDP relaxation problem by setting a new parameter param.SDPsolver = 'sdpa'. The default is param.SDPsolver = 'sedumi', which indicates that SeDuMi will be used to solve the SDP relaxaion problem. (2) Additional installation to use the SDPA ---- What is revised in SparsePOP215? June 22, 2009 (1) The function for writing an SDP in the sdpa sparse format is modified and included in the function solveBySeDuMi.m (2) If param.scalingSW = 1 and param.sdpaDataFile is not empty, then SparsePOP generates a file with "info" extension. This file contains three columns for information on scaling for a given POP. One can retrieve a solution of the original POP from a solution of the scaled POP, which is generated by SparsePOP, by using this file. The first column is an index of variables in the POP. The second and third colmuns indicate coefficients for scaling. For example, assume that this file has the following three columns: 1 0.50000 4.0000 2 -2.00000 0.7000 3 -0.50000 1.0000 4 1.00000 0.0000 If z is obtained as a solution of the scaled POP, x can be computed as follows: x(1) = 0.50000*z(1) + 4.0000, x(2) =-2.00000*z(2) + 0.7000, x(3) =-0.50000*z(3) + 1.0000, x(4) = 1.00000*z(4) + 0.0000, ---- SparsePOP210: a revision of SparsePOP200 April 3, 2009 (1) Input for nonlinear least square problem. The user can represent a constrained nonlinear least square problem minimize \sum_{j=1}^m f_j(x)^2 subject to g_k(x) >= 0 (or = 0) (k=1,2,...,m), lbd_i <= x_i <= ubd_i in the SparsePOP format. Each function f_j in the objective function is described in terms of objPoly{j}, while the constraint of the problem in terms of ineqPolySys, lbd and ubd in the same way as a nominal POP. When size(objOpt,2) >= 2, the sparsePOP automatically regards that the given problem is a nonlinear least square problem, and applies the sparse/dense SDP relaxation to it. For example, >> sparsePOP('BroydenTriLS.m'); (2) Refinement of solutions by local optimization methods. Optimization Toolbox is necessary to use this feature. The new version incorporated MATLAB functions fmincon, fminunc and lsqnonlin in Optimization Toolbox, so that the user can refine the solution obtained from the sparse/dense SDP relaxation by setting the parameter param.POPsolver = 'active-set'; param.POPsolver = 'interior-point'; param.POPsolver = 'trust-region-reflective'; or param.POPsolver = 'lsqnonlin'; The former three methods are for general polynomial optimization problems, while the last 'lsqnonlin' is valid only for polynomial least square problems with bounded variables and no equality/inequality constraints; size(objPoly,2) >= 2 and ineqPolySys =[]. For example, >> param.POPsolver = 'active-set'; >> sparsePOP210('example1.gms',param); to apply fmincon with 'active-set' method. Or >> pram.POPsolver = 'lsqnonlin'; >> sparsePOP210('BroydenTriLS(10)',param); to apply lsqnonlin to the nonlinear least square problem 'BroydenTriLS(10)' with bounds. (3) function [x,fval,exitflag,output] ... = POPfmincon(objPoly,ineqPolySys,lbd,ubd,x0,options); The user can use POPfmincon.m as standalone MATLAB progams to solve a POP in the SparsePOP format. Optimization Toolbox is necessary to utilize this feature. There are two ways of using POPfmincon.m. The one is: >> POPfmincon('DataFile)'), where DataFile) is a file name of a POP in the gms format or the SparsePOP format. For example, >> [x,fval,exitflag,output] = POPfmincon('example1.gms'); Here x is the approximate optimal solution computed and fval the objective function value at x. exitflag and output are output arguments from fmincon. The user can specify an initial point x0 and options for fmincon; >> x0 = ones(10,1); >> [x,fval,exitflag,output] = POPfmincon('example1.gms',x0); >> options = optimset('Algorithm','active-set','GradObj','on',... 'GradConstr','on','HessFcn',@hessianfcn,'Display','iter'); >> [x,fval,exitflag,output] = POPfmincon('example1.gms',x0,options); The user can choose 'active-set', 'trust-region-reflective' or 'interior-point' for the option Algorithm. The function can process a polynomial least square problem with inequality/equality constraints and bounds described in the SparsePOP format. See (1) above. For example, >> x0 = ones(10,1); >> [x,fval,exitflag,output] = POPfmincon('BroydenTriLS(10)',x0); The other way is: >> [x,fval,exitflag,output] = POPfmincon(objPoly,ineqPolySys,lbd,ubd); >> [x,fval,exitflag,output] = POPfmincon(objPoly,ineqPolySys,lbd,ubd,x0); or >> [x,fval,exitflag,output] = POPfmincon(objPoly,ineqPolySys,lbd,ubd,x0,options); See the help on fmincon for detais of exitflag, output and options. (4) function [x,fval,exitflag,output] = POPlsqnonlin(LSobjPoly,lbd,ubd,x0,options) The user can use POPlsqnonlin.m as standalone MATLAB programs to solve a polynomial least square problem with bounds in the SparsePOP format. If the problem involves equality/inequality constraits besides bounds, i.e., inequPolySys is nonempty, then use POPfmincon above. Optimization Toolbox is necessary to utilize this feature. There are two ways of using POPlsqnonlin.m. The one is: >> POPlsqnonlin('DataFile'), where DataFile is a file name of a polynomial least square problem POP in the SparsePOP format; the gms formt file is not available. For example, >> [x,fval,exitflag,output] = POPlsqnonlin('BroydenTriLS(12)'); Here x is the approximate optimal solution computed and fval the objective function value at x. exitflag and output are output arguments from lsqnonlin. The user can specify an initial point x0 and options for lsqnonlin; >> x0 = ones(10,1); >> [x,fval,exitflag,output] = POPlsqnonlin('BroydenTriLS(12)',x0); >> options = optimset('Jacobian','on','Display','iter'); >> [x,fval,exitflag,output] = POPfmincon('example1.gms',x0,options); See the help on lsqnonlin for detais of exitflag, output and options. ---- SparsePOP200: a revision of SparsePOP120 1) C++ subroutines can be used to speedup the construction of a sparse SDP relaxation problem from a given a sparse polynomial optimization problem. 2) Two kinds of SparsePOP are included: A set of MATLAB programs combined with C++ subroutines and a set of all MATLAB programs. Input and output are same for both SparsePOPs, and they construct the same SDP relaxation problem from a polynomial optimization problem. 3) User interface is improved.