-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathfindMin.jl
146 lines (118 loc) · 3.63 KB
/
findMin.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
include("misc.jl")
function findMin(funObj,w;maxIter=100,epsilon=1e-2,derivativeCheck=false,verbose=true)
# funObj: function that returns (objective,gradient)
# w: initial guess
# maxIter: maximum number of iterations
# epsilon: stop if the gradient gets below this
# derivativeCheck: whether to check against numerical gradient
# Evalluate the intial objective and gradient
(f,g) = funObj(w)
# Optionally check if gradient matches finite-differencing
if derivativeCheck
g2 = numGrad(funObj,w)
if maximum(abs.(g-g2)) > 1e-4
@show([g g2])
@printf("User and numerical derivatives differ\n")
sleep(1)
else
@printf("User and numerical derivatives agree\n")
end
end
# Initial step size and sufficient decrease parameter
gamma = 1e-4
alpha = 1
for i in 1:maxIter
# Try out the current step-size
wNew = w - alpha*g
(fNew,gNew) = funObj(wNew)
# Decrease the step-size if we increased the function
gg = dot(g,g)
while fNew > f - gamma*alpha*gg
if verbose
@printf("Backtracking\n")
end
# Fit a degree-2 polynomial to set step-size
alpha = alpha^2*gg/(2(fNew - f + alpha*gg))
# Try out the smaller step-size
wNew = w - alpha*g
(fNew,gNew) = funObj(wNew)
end
# Guess the step-size for the next iteration
y = gNew - g
alpha *= -dot(y,g)/dot(y,y)
# Sanity check on the step-size
if (!isfinitereal(alpha)) | (alpha < 1e-10) | (alpha > 1e10)
alpha = 1
end
# Accept the new parameters/function/gradient
w = wNew
f = fNew
g = gNew
# Print out some diagnostics
gradNorm = norm(g,Inf)
if verbose
@printf("%6d %15.5e %15.5e %15.5e\n",i,alpha,f,gradNorm)
end
# We want to stop if the gradient is really small
if gradNorm < epsilon
if verbose
@printf("Problem solved up to optimality tolerance\n")
end
return w
end
end
if verbose
@printf("Reached maximum number of iterations\n")
end
return w
end
function findMinL1(funObj,w,lambda;maxIter=100,epsilon=1e-2)
# funObj: function that returns (objective,gradient)
# w: initial guess
# lambda: value of L1-regularization parmaeter
# maxIter: maximum number of iterations
# epsilon: stop if the gradient gets below this
# Evalluate the intial objective and gradient
(f,g) = funObj(w)
# Initial step size and sufficient decrease parameter
gamma = 1e-4
alpha = 1
for i in 1:maxIter
# Gradient step on smoooth part
wNew = w - alpha*g
# Proximal step on non-smooth part
wNew = sign.(wNew).*max.(abs.(wNew) - lambda*alpha,0)
(fNew,gNew) = funObj(wNew)
# Decrease the step-size if we increased the function
gtd = dot(g,wNew-w)
while fNew + lambda*norm(wNew,1) > f + lambda*norm(w,1) - gamma*alpha*gtd
@printf("Backtracking\n")
alpha /= 2
# Try out the smaller step-size
wNew = w - alpha*g
wNew = sign.(wNew).*max.(abs.(wNew) - lambda*alpha,0)
(fNew,gNew) = funObj(wNew)
end
# Guess the step-size for the next iteration
y = gNew - g
alpha *= -dot(y,g)/dot(y,y)
# Sanity check on the step-size
if (!isfinitereal(alpha)) | (alpha < 1e-10) | (alpha > 1e10)
alpha = 1
end
# Accept the new parameters/function/gradient
w = wNew
f = fNew
g = gNew
# Print out some diagnostics
optCond = norm(w-sign.(w-g).*max.(abs.(w-g)-lambda,0),Inf)
@printf("%6d %15.5e %15.5e %15.5e\n",i,alpha,f+lambda*norm(w,1),optCond)
# We want to stop if the gradient is really small
if optCond < epsilon
@printf("Problem solved up to optimality tolerance\n")
return w
end
end
@printf("Reached maximum number of iterations\n")
return w
end