en>Improbable keeler: /* Poisson point process */

2014-01-15T19:52:14Z

Poisson point process

New page

'''LINCOA''' ('''LIN'''early '''C'''onstrained '''O'''ptimization '''A'''lgorithm) is a [[numerical analysis|numerical]] [[optimization (mathematics)|optimization]] [[algorithm]] by [[Michael J. D. Powell]]. It is also the name of [[Michael J. D. Powell|Powell]]'s [[Fortran#FORTRAN 77|Fortran 77]] implementation of the algorithm.

LINCOA solves linearly [[constrained optimization]] problems without using [[derivatives]] of the [[Optimization problem|objective function]], which makes it a [[derivative-free optimization|derivative-free]] algorithm. The algorithm solves the problem using a [[trust region]] method that forms [[quadratic]] models by [[interpolation]]. One new point is computed on each iteration, usually by solving a [[trust region]] subproblem subject to the linear constraints, or alternatively, by choosing a point to replace an [[interpolation]] point that may be too far away for reliability. In the second case, the new point may not satisfy the linear constraints.

The same as [[NEWUOA]], LINCOA constructs the [[quadratic]] models by the least [[Frobenius norm]] updating <ref>{{cite journal|last=Powell|first=M. J. D. |title=Least Frobenius norm updating of quadratic models that satisfy interpolation conditions |journal=Mathematical Programming |publisher= Springer |year=2004 |volume=100 |pages=183–215|doi=10.1007/s10107-003-0490-7}}</ref> technique. A model function is determined by interpolating the [[Optimization problem|objective function]] at <math> m </math> (an integer between <math> n+2 </math> and <math> (n+1)(n+2)/2 </math>) points; the remaining freedom, if any, is taken up by minimizing the [[Frobenius norm]] of the change to the model's [[Hessian]] (with respect to the last iteration).

LINCOA [[software]] was released on December 6, 2013.<ref name="depository">{{cite web|url=http://mat.uc.pt/~zhang/software.html |title=A depository of Powell's software |publisher= |date= |accessdate=2014-01-18}}</ref> In the [[Comment (computer programming)|comment]] of the [[source code]],<ref name="code">{{cite web|url=http://mat.uc.pt/~zhang/software/lincoa.zip |title=Source code of LINCOA software |publisher= |date= |accessdate=2014-01-18}}</ref> it is said that LINCOA is not suitable for very large numbers of variables (which is typically true for algorithms not using derivatives), but "a few calculations with 1000 variables, however, have been run successfully overnight, and the performance of LINCOA is satisfactory usually for small numbers of variables."<ref name="code" /> It is also pointed out that the author's typical choices of <math> m </math> are <math> n+6 </math> and <math> 2n+1 </math>, the latter "being recommended for a start", and "larger values tend to be highly inefficent when the number of variables is substantial, due to the amount of work and extra difficulty of adjusting more points."<ref name="code" />

[[Michael J. D. Powell|Powell]] has not published any paper or report on LINCOA (as of January 18, 2014).

==See also==
*[[COBYLA]]
*[[NEWUOA]]

==References==
{{Reflist}}

==External links==
*[http://mat.uc.pt/~zhang/software.html Source code of LINCOA software]
*[https://github.com/cureos/csnumerics C# implementation of LINCOA]

{{optimization algorithms}}

[[Category:Optimization algorithms and methods]]

Nearest neighbour distribution - Revision history

en>Improbable keeler: /* Poisson point process */