Secant Update Penalized Powell-Symmetric-Broyden

One of the frequently used families of methods for the resolution of non-linear optimization problems are quasi-Newton methods. These methods differ from each other, among other things, by the way in which the estimation of the Hessian is built by imposing some properties to the created matrix. A simple example is Broyden’s method where the satisfaction of the last secant equation is imposed, which is called Secant Update property. In order to create a more accurate estimate of the Hessian, one can try to maximize the use of available information. In addition to the Secant Update property, other information that can be used is the symmetry of the Hessian matrix or the previous steps on the optimization path (by satisfying multiple secant equations). The Powell-Symmetric-Broyden method (PSB) combines, for example, the secant update property, and the symmetry of the Hessian. On the other hand, Schnabel proved that it is impossible to combine this symmetry with the satisfaction of multiple secant equations.Developed originally in order to solve noisy problems, the Penalized PSB (pPSB) offers a way around the impossibility mentioned above by creating a symmetric Hessian and penalizing the non-satisfaction of multiple secant equations by using weight factors. In our study, we add to pPSB the secant update property. This gives us the Secant Update Penalized PSB (SUpPSB): the created estimate of the Hessian is symmetric, satisfies the last secant equation and penalizes the non-satisfaction of previous secant equations.While it is possible to approach the SUpPSB by using a very high first weight coefficient in pPSB, this new formula that we propose behaves differently. By avoiding a great difference in order of magnitude between the first coefficient and the following ones, it reduces the risk of rounding errors on those last ones during the calculation. The formula also avoids matrix inversions, which makes it easier to compute. Next to that, SUpPSB has been tested with multiple unconstrained optimization problems (More, Garbow Hillstrom). As shown on Fig. 1, the performance profiles for the best performing weight coefficient combination show that SUpPSB performs globally better compared to pPSB.