[37] | 1 | function diagnostic = callbmilin(F,h,options) |
---|
| 2 | % |
---|
| 3 | % EXTREMELY naive implementation of a local BMI solver |
---|
| 4 | % using linearizations and a simple trust-region. |
---|
| 5 | % |
---|
| 6 | % To be precise, it not only "solves" problems with BMIs |
---|
| 7 | % but also PMIs (polynomial matrix inequalities). |
---|
| 8 | % |
---|
| 9 | % Moreover, the objective may be nonlinear. |
---|
| 10 | % |
---|
| 11 | % The default behaviour of the solver can be |
---|
| 12 | % altered by using the field bmilin in sdpsettings. |
---|
| 13 | % |
---|
| 14 | % bmilin.trust - Trust region norm p in ||x-x0||_p < alpha*||x0||_p+beta [1|2|inf (2)] |
---|
| 15 | % bmilin.alpha - Trust region parameter [real > 0 (0.5)] |
---|
| 16 | % bmilin.beta - Trust region parameter [real > 0 (0)] |
---|
| 17 | % bmilin.solver - Solver for linearized SDP [Any of the solvers above ('')] |
---|
| 18 | % bmilin.maxiterls - Maximum number of iterations in line search [integer (10)] |
---|
| 19 | % bmilin.maxiter - Maximum number of iterations [integer (25)] |
---|
| 20 | % |
---|
| 21 | |
---|
| 22 | disp('***********************************************') |
---|
| 23 | disp('') |
---|
| 24 | disp('Warning : This code is just for illustration ') |
---|
| 25 | disp('and should be seen as an example on how you can') |
---|
| 26 | disp('implement your own local BMI solver.') |
---|
| 27 | disp('') |
---|
| 28 | disp('Note also that this solver is slow since it is') |
---|
| 29 | disp('implemented using high-level YALMIP code') |
---|
| 30 | disp('') |
---|
| 31 | disp('***********************************************') |
---|
| 32 | |
---|
| 33 | % Recover all used variables |
---|
| 34 | x = recover(depends(F)); |
---|
| 35 | |
---|
| 36 | % Set up for local solver |
---|
| 37 | verbose = options.verbose; |
---|
| 38 | options.verbose = max(options.verbose-1,0); |
---|
| 39 | options.solver = options.bmilin.solver; |
---|
| 40 | |
---|
| 41 | % Initial values hopefully supplied |
---|
| 42 | if options.usex0 |
---|
| 43 | % Initialize to 0 if not initialized |
---|
| 44 | not_initial = isnan(double(x)); |
---|
| 45 | if any(not_initial) |
---|
| 46 | setsdpvar(x(find(not_initial)),repmat(0,length(find(not_initial)),1)); |
---|
| 47 | end |
---|
| 48 | else |
---|
| 49 | % No initials, set to zero |
---|
| 50 | setsdpvar(x,repmat(0,length(x),1)); |
---|
| 51 | F_linear = F(find(is(F,'linear'))); |
---|
| 52 | % Find some non-zero by solving for the linear constraints |
---|
| 53 | if length(F_linear) > 0 |
---|
| 54 | sol = solvesdp(F_linear,linearize(h)+x'*x,options); |
---|
| 55 | if sol.problem~=0 |
---|
| 56 | diagnostic.solvertime = 0; |
---|
| 57 | diagnostic.info = yalmiperror(0,'BMILIN'); |
---|
| 58 | diagnostic.problem = sol.problem; |
---|
| 59 | return |
---|
| 60 | end |
---|
| 61 | end |
---|
| 62 | end |
---|
| 63 | |
---|
| 64 | % Outer linearization loop |
---|
| 65 | goon = 1; |
---|
| 66 | outer_iter = 0; |
---|
| 67 | alpha = 1; |
---|
| 68 | problem = 0; |
---|
| 69 | while goon |
---|
| 70 | |
---|
| 71 | % Save old iterates and old objective function |
---|
| 72 | x0 = double(x); |
---|
| 73 | h0 = double(h); |
---|
| 74 | |
---|
| 75 | % Linearize |
---|
| 76 | Flin = linearize(F); |
---|
| 77 | |
---|
| 78 | % add a trust region |
---|
| 79 | switch options.bmilin.trust |
---|
| 80 | case 1 |
---|
| 81 | case 2 |
---|
| 82 | Flin = Flin + set(cone(x-x0,2*alpha*options.bmilin.alpha*norm(x0,2)+options.bmilin.beta)); |
---|
| 83 | case inf |
---|
| 84 | Flin = Flin + set(x-x0 < options.bmilin.alpha*norm(x0,'inf')+options.bmilin.beta); |
---|
| 85 | Flin = Flin + set(x-x0 >-options.bmilin.alpha*norm(x0,'inf')+options.bmilin.beta); |
---|
| 86 | otherwise |
---|
| 87 | end |
---|
| 88 | |
---|
| 89 | % Solve linearized problem |
---|
| 90 | sol = solvesdp(Flin,linearize(h),options); |
---|
| 91 | switch sol.problem |
---|
| 92 | case 0 |
---|
| 93 | % Optimal decision variables for linearized problem |
---|
| 94 | xnew = double(x); |
---|
| 95 | |
---|
| 96 | % Original problem is not guaranteed to be feasible |
---|
| 97 | % Simple line-search for feasible (and improving) solution |
---|
| 98 | alpha = 1; |
---|
| 99 | inner_iter = 0; |
---|
| 100 | p = checklmi(F); |
---|
| 101 | while ((min(p)<-1e-5) | (double(h)>h0*1.0001)) & (inner_iter < 15) |
---|
| 102 | alpha = alpha*0.8; |
---|
| 103 | setsdpvar(x,x0+alpha*(xnew-x0)); |
---|
| 104 | p = checkset(F); |
---|
| 105 | inner_iter = inner_iter + 1; |
---|
| 106 | end |
---|
| 107 | if inner_iter < 300 |
---|
| 108 | outer_iter = outer_iter + 1; |
---|
| 109 | if verbose > 0 |
---|
| 110 | disp(sprintf('#%d cost : %6.3f step : %2.3f',outer_iter,double(h),alpha)); |
---|
| 111 | end |
---|
| 112 | goon = (outer_iter < options.bmilin.maxiter); |
---|
| 113 | else |
---|
| 114 | problem = 4; |
---|
| 115 | goon = 0; |
---|
| 116 | end |
---|
| 117 | |
---|
| 118 | |
---|
| 119 | otherwise |
---|
| 120 | problem = 4; |
---|
| 121 | goon = 0; |
---|
| 122 | end |
---|
| 123 | |
---|
| 124 | end |
---|
| 125 | |
---|
| 126 | diagnostic.solvertime = 0; |
---|
| 127 | diagnostic.info = yalmiperror(problem,'BMILIN'); |
---|
| 128 | diagnostic.problem = problem; |
---|