<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 12pt;
font-family:Calibri
}
--></style></head>
<body class='hmmessage'><div dir='ltr'>So I finally got the modified version of the Hessian computation working. I tried it on a<br>problem with 2300 variables and 2040 nonlinear constraints using an Intel E8400. <br>The problem has a sparse Hessian with 37000 non-zeros of 5600000 possible.<br><br>Turns out that, except for the first call, the new version treating the Lagrange<br>multipliers (and ipopt's obj_factor) as variables is much faster. The table summarizes<br>the situation:<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; First call&nbsp; (repeat=0)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 10 subsequent calls<br>Old &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 47 sec&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 480 sec&nbsp; (repeat=0)<br>New&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 54 sec&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 15 sec&nbsp;&nbsp;&nbsp; (repeat=1)<br><br><br>Unfortunately Valgrind still has some complaints about the new code, but my intuition<br>is that the problem is not with ADOL-C and that a fix will not change the above results<br>significantly (the errors strangely show up in functions unrelated to the Hessian computation,<br>but are somehow anyway related to the new method because they only appear if I run<br>the new method more than once). Anyway, the code has thus far worked without crashes.<br><br><br>Thanks for all helpful comments!<br><br>Kind regards<br><br>Ingrid<br><br><br><div><div id="SkyDrivePlaceholder"></div><hr id="stopSpelling">From: ingridhallen@hotmail.com<br>To: kshitij@math.upb.de<br>Date: Fri, 3 May 2013 07:43:09 +0200<br>CC: adol-c@list.coin-or.org<br>Subject: Re: [ADOL-C] Evaluating Hessian of Lagrangian<br><br>

<style><!--
.ExternalClass .ecxhmmessage P {
padding:0px;
}

.ExternalClass body.ecxhmmessage {
font-size:12pt;
font-family:Calibri;
}

--></style>
<div dir="ltr">Hi,<br><br>Thanks for the quick reply! The problem turned out to be my function for evaluating<br>the Lagrangian. A bit simplified, the following is the original code:<br><br>adouble L = obj_factor*obj_fun(x);<br>for (unsigned int i=0; i&lt;nconstr; i++)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L += lambda[i]*constr[i];<br><br>This code worked fine with lambda as doubles, but when using lambda as adoubles,<br>i.e. as variables, additional non-zeros appeared in H_{xx}. However, when changing <br>the code to<br><br>adouble L = obj_factor*obj_fun(x);<br>for (unsigned int i=0; i&lt;nconstr; i++)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L = L + lambda[i]*constr[i];<br><br>everything worked fine, with all additional non-zeros ending up in columns&gt;dim(x). <br>Not sure why though, perhaps someone could explain?<br><br>Kind regards<br><br>Ingrid<br><br><br><br><br><br><br><div><div id="ecxSkyDrivePlaceholder"></div>&gt; Date: Thu, 2 May 2013 15:54:28 +0200<br>&gt; From: kshitij@math.upb.de<br>&gt; To: ingridhallen@hotmail.com<br>&gt; CC: awalther@math.uni-paderborn.de; adol-c@list.coin-or.org<br>&gt; Subject: Re: [ADOL-C] Evaluating Hessian of Lagrangian<br>&gt; <br>&gt; Hello,<br>&gt; <br>&gt; the sequence of rows or columns in the hessian is exactly the same as of<br>&gt; the execution of the &lt;&lt;= operators that define independents between<br>&gt; trace_on() and trace_off(). So as long as the &lt;&lt;= operator was executed<br>&gt; for all x variables before all lagrange multipliers, the H_{xl}<br>&gt; components should have column indices larger than dim(x).<br>&gt; <br>&gt; Sincerely<br>&gt; Kshitij Kulshrestha.<br>&gt; <br>&gt; As on 2013-05-02 15:28h, Ingrid Hallen did write:<br>&gt; &gt; Hi,<br>&gt; &gt; <br>&gt; &gt; I finally got time to start implementing the alternative method for<br>&gt; &gt; computing the Hessian of<br>&gt; &gt; the Lagrangian to do some benchmarking. However, I have come across the<br>&gt; &gt; following difficulty:<br>&gt; &gt; <br>&gt; &gt; Using also the Lagrange multipliers as variables yields an Hessian of<br>&gt; &gt; the Lagrangian in the<br>&gt; &gt; form of a block matrix:<br>&gt; &gt; <br>&gt; &gt; H = / H_{xx}         H_{xl} \<br>&gt; &gt;        \ H_{xl}                0    /<br>&gt; &gt; <br>&gt; &gt; Here H_{xx} is the Hessian wrt to the original variables x\inR^n that we<br>&gt; &gt; are interested in. After calling<br>&gt; &gt; sparse_hess(tag,n,repeat,x,&amp;nnz,&amp;rind,&amp;cind,&amp;values,&amp;options) I thought<br>&gt; &gt; that it should be<br>&gt; &gt; straightforward to identify the parts of rind, cind and values<br>&gt; &gt; pertaining to H_{xx}. For instance,<br>&gt; &gt; say we want to count the non-zeros in the first row of H_{xx}, nnz_xx,<br>&gt; &gt; using the following code:<br>&gt; &gt; <br>&gt; &gt; int k = 0<br>&gt; &gt; int nnz_xx = 0<br>&gt; &gt; while rind[k]==0<br>&gt; &gt;     if cind[k]&lt;n<br>&gt; &gt;           nnz_xx++;<br>&gt; &gt;     end<br>&gt; &gt;     k++;<br>&gt; &gt; end<br>&gt; &gt; <br>&gt; &gt; This of course only works provided the non-zeros of H_{xl} are found in<br>&gt; &gt; the columns&gt;n, but that<br>&gt; &gt; appears not to be the case.<br>&gt; &gt; <br>&gt; &gt; Am I missing something really simple here, or how can I extract H_{xx}?.<br>&gt; &gt; <br>&gt; &gt; Kind regards<br>&gt; &gt; Ingrid<br>&gt; &gt; <br>&gt; &gt; <br>&gt; &gt; <br>&gt; &gt; <br>&gt; &gt; ------------------------------------------------------------------------<br>&gt; &gt; From: ingridhallen@hotmail.com<br>&gt; &gt; To: awalther@math.uni-paderborn.de<br>&gt; &gt; Date: Thu, 11 Apr 2013 09:26:23 +0200<br>&gt; &gt; CC: adol-c@list.coin-or.org<br>&gt; &gt; Subject: Re: [ADOL-C] Evaluating Hessian of Lagrangian<br>&gt; &gt; <br>&gt; &gt; Thanks for your reply!<br>&gt; &gt; <br>&gt; &gt; I think I will do some benchmarking then, to see which<br>&gt; &gt; of the two approaches works best for my problem.<br>&gt; &gt; <br>&gt; &gt; The approach suggested by Norm is certainly interesting,<br>&gt; &gt; but I think I have to little experience with optimization<br>&gt; &gt; to implement it successfully. At least for the moment.<br>&gt; &gt; <br>&gt; &gt; Sincerely,<br>&gt; &gt; <br>&gt; &gt; Ingrid<br>&gt; &gt; <br>&gt; &gt; <br>&gt; &gt;&gt; Date: Wed, 10 Apr 2013 22:51:22 +0200<br>&gt; &gt;&gt; From: awalther@math.uni-paderborn.de<br>&gt; &gt;&gt; To: ingridhallen@hotmail.com<br>&gt; &gt;&gt; CC: normvcr@telus.net; adol-c@list.coin-or.org<br>&gt; &gt;&gt; Subject: Re: [ADOL-C] Evaluating Hessian of Lagrangian<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; Hi<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; sorry for entering the discussion so late but I was on travel<br>&gt; &gt;&gt; the last days and most of the time offline.<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; If you can exploit the minor size of the reduced Hessian<br>&gt; &gt;&gt; the approach proposed by Norm is certainly the best way to go<br>&gt; &gt;&gt; since it requires the least number of Hessian vector product<br>&gt; &gt;&gt; which determines the cost of the derivative calculation.<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; However, I am not sure whether Ipopt can really exploit this.<br>&gt; &gt;&gt; Regarding the other approaches discussed so far:<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; We made the experience that it really depends on the application<br>&gt; &gt;&gt; whether<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; * tracing the Lagrangian once with x and lambda as inputs<br>&gt; &gt;&gt; and evaluating only a part of the Hessian reusing the trace<br>&gt; &gt;&gt; in all iterations<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; or<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; * retracing the Lagrangian with x as adoubles and lambda as doubles<br>&gt; &gt;&gt; in each iteration and computing then the whole Hessian<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; performs better in terms of runtime. You could give both approaches<br>&gt; &gt;&gt; a try and see what works better for you. Both approaches have their<br>&gt; &gt;&gt; pros and cons with respect to efficiency.<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; Best regards<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; Andrea<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; --<br>&gt; &gt;&gt; Prof. Dr. Andrea Walther<br>&gt; &gt;&gt; Lehrstuhl fuer Mathematik und ihre Anwendungen<br>&gt; &gt;&gt; Institut fuer Mathematik<br>&gt; &gt;&gt; Universitaet Paderborn<br>&gt; &gt;&gt; Warburger Str. 100<br>&gt; &gt;&gt; 33098 Paderborn<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; Email: andrea.walther@uni-paderborn.de<br>&gt; &gt;&gt; Phone: ++49 5251 602721<br>&gt; &gt;&gt; ++49 5251 602724 (sekr.)<br>&gt; &gt;&gt; Fax: ++49 5251 603728<br>&gt; &gt;&gt;<br>&gt; &gt;&gt; **********<br>&gt; &gt;&gt;<br>&gt; &gt;&gt;<br>&gt; &gt;&gt;<br>&gt; &gt; <br>&gt; &gt; _______________________________________________ ADOL-C mailing list<br>&gt; &gt; ADOL-C@list.coin-or.org http://list.coin-or.org/mailman/listinfo/adol-c<br>&gt; &gt; <br>&gt; &gt; <br>&gt; &gt; _______________________________________________<br>&gt; &gt; ADOL-C mailing list<br>&gt; &gt; ADOL-C@list.coin-or.org<br>&gt; &gt; http://list.coin-or.org/mailman/listinfo/adol-c<br>&gt; &gt; <br>&gt; <br>&gt; -- <br>&gt; Dr. Kshitij Kulshreshtha<br>&gt; <br>&gt; Institut für Mathematik,<br>&gt; Universität Paderborn,<br>&gt; Warburger Straße 100,<br>&gt; 33098 Paderborn.<br>&gt; <br>&gt; Büro: A3.235<br>&gt; <br>&gt; Privatanschrift:<br>&gt; Arnikaweg 62<br>&gt; 33100 Paderborn.<br></div>                                               </div>
<br>_______________________________________________
ADOL-C mailing list
ADOL-C@list.coin-or.org
http://list.coin-or.org/mailman/listinfo/adol-c</div>                                               </div></body>
</html>