Time complexity of constrained local optimization
- To: mathgroup at smc.vnet.net
- Subject: [mg84882] Time complexity of constrained local optimization
- From: Yaroslav Bulatov <yaroslavvb at gmail.com>
- Date: Thu, 17 Jan 2008 07:04:05 -0500 (EST)
Documentation says that FindMinimum needs first and second derivatives
for constrained local optimization. Does it mean the runtime scales as
O(n^2) where n is the number of variables?
I'm trying to solve a constrained optimization problem, and
FindMinimum starts to take more than a minute for more than 20
variables, is that typical?
I used StepMonitor combined with Dynamic, and see that actual
iterations take a small fraction of time. For 20 variable problem, it
does something for 30 seconds, then the the actual iterations took 2
seconds, what is it doing for the first 30 seconds?
The actual problem is below. It tries to find the maximum entropy
distribution over n bins in the interval {-1,1} with mean 0 and
specified variance and skewness constraints.
getdist[n_, var_, skew_] := Module[{},
(* define entropy, make sure it's well defined for 0 entries *)
h[x_] = -Piecewise[{{x Log[x], x > 0}}, 0];
SetAttributes[h, Listable];
ent[x_] := Total[h[x]];
(* setup moment constraints *)
vals = Table[i, {i, 1/n, 1, 1/n}];
vals = Reverse[-vals]~Join~vals;
cons = {vals^0, vals^1, vals^2, vals^3} // N;
(* get a parametrization for the subspace satisfying moment
constraints *)
ns = Orthogonalize[NullSpace[cons]] // Transpose;
vars = Table[Subscript[x, i], {i, 1, Dimensions[ns] // Last}];
sol = LinearSolve[cons, {1, 0, var, skew}];
(* find a point satisfying positivity constraints *)
realsol =
LinearProgramming[ConstantArray[1, Length[vars]],
ns, -sol, -Infinity] // Chop;
distr = (ns.vars + sol);
poscons = And @@ (# >= 0 & /@ distr);
obj = ent[distr];
(* maximize entropy subject to positivity constraints *)
distsol =
distr /. (FindMaximum[{obj, poscons}, Thread[{vars, realsol}]] //
Last)
]
(* test *)
dd = getdist[10, .4, .23];
ListPlot[dd, Filling -> Axis, PlotRange -> {{-1.1, 1.1}, {0, .3}},
DataRange -> {-1, 1}, PlotStyle -> PointSize[Medium]]