<div dir="ltr"><span style="font-family:arial,sans-serif;font-size:13px">To see where those 15 seconds are spent, look at the wall time in the advanced timing statistics: 14.946 out of 15.734 seconds are spent in function evaluations. This seems normal for the quasi newton method if you have only a few constraints.</span><div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">Why does the optimization terminate early?</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 13, 2014 at 1:24 PM, Ipopt User <span dir="ltr"><<a href="mailto:ipoptuser@gmail.com" target="_blank">ipoptuser@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">To see where those 15 seconds are spent, look at the wall time in the advanced timing statistics: 14.946 out of 15.734 seconds are spent in function evaluations. This seems normal for the quasi newton method if you have only a few constraints.<div><br></div><div>Why does the optimization terminate early?</div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 13, 2014 at 12:45 PM, John Schulman <span dir="ltr"><<a href="mailto:john.d.schulman@gmail.com" target="_blank">john.d.schulman@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>I haven't had much luck yet setting the initial Lagrange multipliers.</div><div>One hack that helps a bit is to redefine the objective function so that it has value +inf when the constraint violation is greater than some threshold.</div><div>Of course, this severely impedes the progress of the optimizer and causes it to emit a lot of warnings.</div><div>But maybe rescaling or reshaping the objective function is the way to go here.</div><div><br></div><div>Yup, the problem 50000 dimensional, and there's no banded-diagonal structure or anything. I think the main bottleneck should be function and gradient evaluations, not the linear algebra. I looked at the timing stats and something is a bit off. The optimization takes about 15 seconds but the stats only account for about 1 second. Maybe because I'm using fork-based parallelism (via python multiprocessing) to compute the gradients? Anyway, if it's indeed true that linear algebra is taking .5 seconds or so, then that's insignificant.</div><div><br></div><div><br></div><div><br></div><div><div>Number of objective function evaluations = 70</div><div>Number of objective gradient evaluations = 51</div><div>Number of equality constraint evaluations = 0</div><div>Number of inequality constraint evaluations = 70</div><div>Number of equality constraint Jacobian evaluations = 0</div><div>Number of inequality constraint Jacobian evaluations = 51</div><div>Number of Lagrangian Hessian evaluations = 0</div><div>Total CPU secs in IPOPT (w/o function evaluations) = 0.591</div><div>Total CPU secs in NLP function evaluations = 0.439</div><div><br></div><div><br></div><div>Timing Statistics:</div><div><br></div><div>OverallAlgorithm....................: 1.030 (sys: 0.064 wall: 15.734)</div><div> PrintProblemStatistics.............: 0.000 (sys: 0.000 wall: 0.000)</div><div> InitializeIterates.................: 0.008 (sys: 0.001 wall: 0.222)</div><div> UpdateHessian......................: 0.051 (sys: 0.002 wall: 0.055)</div><div> OutputIteration....................: 0.001 (sys: 0.001 wall: 0.002)</div><div> UpdateBarrierParameter.............: 0.353 (sys: 0.022 wall: 0.378)</div><div> ComputeSearchDirection.............: 0.133 (sys: 0.005 wall: 0.137)</div><div> ComputeAcceptableTrialPoint........: 0.176 (sys: 0.017 wall: 7.201)</div><div> AcceptTrialPoint...................: 0.004 (sys: 0.000 wall: 0.004)</div><div> CheckConvergence...................: 0.304 (sys: 0.015 wall: 7.735)</div><div>PDSystemSolverTotal.................: 0.436 (sys: 0.020 wall: 0.458)</div><div> PDSystemSolverSolveOnce............: 0.403 (sys: 0.019 wall: 0.422)</div><div> ComputeResiduals...................: 0.026 (sys: 0.001 wall: 0.027)</div><div> StdAugSystemSolverMultiSolve.......: 0.187 (sys: 0.009 wall: 0.197)</div><div> LinearSystemScaling................: 0.000 (sys: 0.000 wall: 0.000)</div><div> LinearSystemSymbolicFactorization..: 0.000 (sys: 0.000 wall: 0.001)</div><div> LinearSystemFactorization..........: 0.030 (sys: 0.000 wall: 0.031)</div><div> LinearSystemBackSolve..............: 0.133 (sys: 0.000 wall: 0.133)</div><div> LinearSystemStructureConverter.....: 0.000 (sys: 0.000 wall: 0.000)</div><div> LinearSystemStructureConverterInit: 0.000 (sys: 0.000 wall: 0.000)</div><div>QualityFunctionSearch...............: 0.049 (sys: 0.005 wall: 0.054)</div><div>TryCorrector........................: 0.000 (sys: 0.000 wall: 0.000)</div><div>Task1...............................: 0.014 (sys: 0.002 wall: 0.017)</div><div>Task2...............................: 0.028 (sys: 0.000 wall: 0.028)</div><div>Task3...............................: 0.002 (sys: 0.000 wall: 0.003)</div><div>Task4...............................: 0.000 (sys: 0.000 wall: 0.000)</div><div>Task5...............................: 0.002 (sys: 0.000 wall: 0.003)</div><div>Function Evaluations................: 0.439 (sys: 0.031 wall: 14.946)</div><div> Objective function.................: 0.069 (sys: 0.007 wall: 3.589)</div><div> Objective function gradient........: 0.149 (sys: 0.008 wall: 3.946)</div><div> Equality constraints...............: 0.000 (sys: 0.000 wall: 0.000)</div><div> Inequality constraints.............: 0.077 (sys: 0.009 wall: 3.686)</div><div> Equality constraint Jacobian.......: 0.000 (sys: 0.000 wall: 0.000)</div><div> Inequality constraint Jacobian.....: 0.145 (sys: 0.007 wall: 3.725)</div><div> Lagrangian Hessian.................: 0.000 (sys: 0.000 wall: 0.000)</div></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 13, 2014 at 12:02 AM, Tony Kelman <span dir="ltr"><<a href="mailto:kelman@berkeley.edu" target="_blank">kelman@berkeley.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">
<div dir="ltr">
<div style="FONT-SIZE:12pt;FONT-FAMILY:'Calibri';COLOR:#000000">
<div>Yikes, you should’ve said you have a dense Hessian, that’s bad news. You
really have 50000 x 50000 all-to-all nonlinear interaction terms? I hope you’re
using OpenBLAS or MKL. Depending on the results of print_timing_statistics, also
a good idea to experiment with as many different linear solvers as you can
get.</div>
<div> </div>
<div style="FONT-SIZE:small;TEXT-DECORATION:none;FONT-FAMILY:"Calibri";FONT-WEIGHT:normal;COLOR:#000000;FONT-STYLE:normal;DISPLAY:inline">
<div style="FONT:10pt tahoma">
<div> </div>
<div style="BACKGROUND:#f5f5f5">
<div><b>From:</b> <a title="john.d.schulman@gmail.com" href="mailto:john.d.schulman@gmail.com" target="_blank">John Schulman</a> </div>
<div><b>Sent:</b> Wednesday, November 12, 2014 10:47 PM</div>
<div><b>To:</b> <a title="kelman@berkeley.edu" href="mailto:kelman@berkeley.edu" target="_blank">Tony Kelman</a> </div>
<div><b>Cc:</b> <a title="ipopt@list.coin-or.org" href="mailto:ipopt@list.coin-or.org" target="_blank">ipopt@list.coin-or.org</a> </div><div><div>
<div><b>Subject:</b> Re: [Ipopt] Low # iters, ensuring that solution remains
feasible</div></div></div></div></div>
<div> </div></div><div><div>
<div style="FONT-SIZE:small;TEXT-DECORATION:none;FONT-FAMILY:"Calibri";FONT-WEIGHT:normal;COLOR:#000000;FONT-STYLE:normal;DISPLAY:inline">
<div dir="ltr">Hi Tony,
<div> </div>
<div>Funny to get a reply from someone so close by after launching a message out
to the colossal internet.</div>
<div> </div>
<div>I wasn't warm-starting at all--that's a great suggestion. Hopefully the
Lagrange multipliers won't change too much between iterations. Otherwise, there
may be some problem-specific ways to guess a reasonable Lagrange multiplier
here.</div>
<div> </div>
<div>Regarding speed & algorithm choice, BFGS seems like the right fit here,
and in this problem it's not really practical to compute the hessian (which is
dense).</div>
<div>But I'll be sure to check out print_timing_statistics -- I'm new to Ipopt
and haven't found these handy tools yet.</div>
<div> </div>
<div>John</div>
<div> </div>
<div class="gmail_extra">
<div> </div>
<div class="gmail_quote">On Wed, Nov 12, 2014 at 10:19 PM, Tony Kelman <span dir="ltr"><<a href="mailto:kelman@berkeley.edu" target="_blank">kelman@berkeley.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT:1ex;MARGIN:0px 0px 0px 0.8ex;BORDER-LEFT:#ccc 1px solid">
<div dir="ltr">
<div dir="ltr">
<div style="FONT-SIZE:12pt;FONT-FAMILY:'Calibri';COLOR:#000000">
<div>Hi John, good to see groups next door also using Ipopt.</div>
<div> </div>
<div>Generally speaking this is a pretty hard thing to do with an
interior-point method. Are you warm-starting the dual variables as well, or
just the primal? That may help, but it depends how closely related the
subproblems are. I’d also avoid doing quasi-newton hessian approximations if
you have a speed-critical application, you’ll get better convergence in most
cases if you are using a modeling tool that can provide exact Hessians. Have
you looked at the breakdown of computation time from
print_timing_statistics?</div>
<div> </div>
<div>-Tony</div>
<div> </div>
<div style="FONT-SIZE:small;TEXT-DECORATION:none;FONT-FAMILY:"Calibri";FONT-WEIGHT:normal;COLOR:#000000;FONT-STYLE:normal;DISPLAY:inline">
<div style="FONT:10pt tahoma">
<div><font size="3" face="Calibri"></font> </div>
<div style="BACKGROUND:#f5f5f5">
<div><b>From:</b> <a title="john.d.schulman@gmail.com" href="mailto:john.d.schulman@gmail.com" target="_blank">John Schulman</a> </div>
<div><b>Sent:</b> Wednesday, November 12, 2014 10:14 PM</div>
<div><b>To:</b> <a title="ipopt@list.coin-or.org" href="mailto:ipopt@list.coin-or.org" target="_blank">ipopt@list.coin-or.org</a>
</div>
<div><b>Subject:</b> Re: [Ipopt] Low # iters, ensuring that solution remains
feasible</div></div></div>
<div> </div></div>
<div style="FONT-SIZE:small;TEXT-DECORATION:none;FONT-FAMILY:"Calibri";FONT-WEIGHT:normal;COLOR:#000000;FONT-STYLE:normal;DISPLAY:inline">
<div>
<div>
<div dir="ltr">Oops, "wildly feasible" in the first paragraph should be "wildly
infeasible"</div>
<div class="gmail_extra">
<div> </div>
<div class="gmail_quote">On Wed, Nov 12, 2014 at 10:06 PM, John Schulman <span dir="ltr"><<a href="mailto:john.d.schulman@gmail.com" target="_blank">john.d.schulman@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT:1ex;MARGIN:0px 0px 0px 0.8ex;BORDER-LEFT:#ccc 1px solid">
<div dir="ltr">
<div>Short: </div>
<div> </div>
<div>I am calling Ipopt repeatedly to solve a series of subproblems.</div>
<div>For each subproblem, Ipopt is initialized with a feasible solution, and
max_iter is set to 50 or so. </div>
<div>The optimization terminates early, and often this intermediate solution
is wildly feasible.</div>
<div>I'm wondering if there are any settings that will ensure that the
result is nearly feasible.</div>
<div> </div>
<div>Longer:</div>
<div> </div>I am using Ipopt to solve a series of subproblems of the
form
<div>minimize f(x), subject to g(x) < delta,</div>
<div>Here g is a distance function of sorts, measuring Distance(x_0,x),
where x_0 is the initialization.</div>
<div>So the the initial point x_0 is feasible.</div>
<div>x has dimension 50000 or so, so I am using hessian_approximation with
limited memory.</div>
<div>
<div> </div>
<div>I need to keep to a low number of iterations, say 50 or 100, so the
overall computation time remains reasonable.</div></div>
<div>It's not essential at all that the solution generated is optimal; I
just want to improve the objective as much as possible while remaining
feasible.</div>
<div> </div>
<div>I tried fiddling with the barrier parameters but didn't have any
luck.</div>
<div>Any suggestions?<br>Thanks in advance for your time.</div><span><font color="#888888">
<div> </div>
<div>John</div>
<div><font color="#000000"></font> </div>
<div> </div>
<div> </div>
<div> </div></font></span></div></blockquote></div>
<div> </div></div></div></div>
<hr>
_______________________________________________<br>Ipopt mailing list<br><a href="mailto:Ipopt@list.coin-or.org" target="_blank">Ipopt@list.coin-or.org</a><br><a href="http://list.coin-or.org/mailman/listinfo/ipopt" target="_blank">http://list.coin-or.org/mailman/listinfo/ipopt</a><br></div></div></div></div></blockquote></div>
<div> </div></div></div></div></div></div></div></div></div>
</blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
Ipopt mailing list<br>
<a href="mailto:Ipopt@list.coin-or.org" target="_blank">Ipopt@list.coin-or.org</a><br>
<a href="http://list.coin-or.org/mailman/listinfo/ipopt" target="_blank">http://list.coin-or.org/mailman/listinfo/ipopt</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>