[Coin-ipopt] Filter foiling Least-Absolute-Deviations (LAD) models?

[Frank J. Iannarilli]

Hi All,


I've been putz'ing for weeks on an NLP model, which employs a 
Least-Absolute-Deviations (LAD) idiom.  I'm concerned that the IPOPT filter 
method (and perhaps filter mechanisms in general?) may hamper the ready 
solution of LAD formulations.  So I ask you if you agree with my point, 
and/or might offer any remediating suggestions (model re-formulation, IPOPT 
tuning/tweaks).


The NLP model attempts to wrap an "overlay" polyhedral mesh around the 
outside (the convex hull) of an inner "cage" mesh.  Furthermore, I want the 
resulting overlay *edges* (distances between vertex pairs) to not differ 
from pre-defined desired lengths by more than "stretch".

The "stretch" variable measures the maximum absolute deviation, that I wish 
to minimize; ideally, it will optimize to near-zero. This is the source of 
the LAD idiom to be employed.  The primal variables of interest are the 
overlay vertex coordinates v_i=(x_i,y_i,z_i), and absolute deviation 
"stretch", so the NLP is formulated as so:


===================================================================
Minimize:  sum_m(laceEdgeLength_m) + k*stretch
s.t.:

(LAD-a)  -stretch <=
         overlayDesiredEdgeLength_n - overlayActualEdgeLength_n
               <= stretch;

(LAD-b) stretch >= 0; := bigNumber ## initialize stretch to be large

(a) alias:  overlayActualEdgeLength_n := (v_n[i]-v_n[j]).(v_n[i]-v_n[j]);
      (x).(y) is inner product of x,y vectors

(b) alias: laceEdgeLength_m := (v_m-r_m).(v_m-r_m);
       r_m are fixed (constant) vectors (anchor points for "laces")

(c) laceEdgeLength_m < upperBound_laceEdgeLength_m;
       (keeps overlay mesh from "wandering aimlessly" in solution space)

(d) overlay vertices to stay outside cage-mesh convex hull (expressed as 
set of linear constraints, involving some auxiliary separating plane 
variables; details omitted for brevity).
===================================================================


In diagnostic printout, I can see that IPOPT is NOT monotonically 
decreasing the "stretch" variable. In fact, given the filter logic, this is 
understandable.  The solver can alternately reduce stretch (thereby 
reducing the primal objective function), then increase stretch (thereby 
reducing the LAD constraint violation).


By increasing the weight "k" on stretch (in the objective function), IPOPT 
eventually returns a nice solution.  However, for well-smaller or larger k 
values, IPOPT returns solutions where "stretch" is objectionably too large. 
I'm not understanding how/why stretch gets "stuck" in this manner.


I can live with such iterative tuning, for each problem instance, but I'd 
rather not, and more importantly, I fear that others who attempt employing 
LAD formulations may be pre-maturely frustrated.


BTW, my problem scaling seems well-posed (all my variables are centered and 
typically of unit scale).  I'm using IPOPT 3.1.0.  Earlier, in place of the 
LAD constraint, I employed fixed-edge-length equality constraints, to wit:

    overlayDesiredEdgeLength_n == overlayActualEdgeLength_n

but this seemed to make the problem nearly unsolvable (i.e., 
hundreds-thousands of iterations, success only with finely-tuned lace 
constraints).


Thanks in advance, and kudos to Andreas for his recent work on the build 
infrastructure!

Regards,



Frank J. Iannarilli, franki at aerodyne.com
Aerodyne Research, Inc., 45 Manning Rd., Billerica, MA 01821 USA
www.aerodyne.com/cosr/cosr.html