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