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; |
---|