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