arXiv Analytics

Sign in

Search ResultsShowing 1-6 of 6

Sort by
  1. arXiv:2401.09609 (Published 2024-01-17)

    The cosine measure relative to a subspace

    Charles Audet, Warren Hare, Gabriel Jarry-Bolduc

    The cosine measure was introduced in 2003 to quantify the richness of a finite positive spanning sets of directions in the context of derivative-free directional methods. A positive spanning set is a set of vectors whose nonnegative linear combinations span the whole space. The present work extends the definition of cosine measure. In particular, the paper studies cosine measures relative to a subspace, and proposes a deterministic algorithm to compute it. The paper also studies the situation in which the set of vectors is infinite. The extended definition of the cosine measure might be useful for subspace decomposition methods.

  2. arXiv:2306.06383 (Published 2023-06-10)

    Using orthogonally structured positive bases for constructing positive $k$-spanning sets with cosine measure guarantees

    Warren Hare, Gabriel Jarry-Bolduc, Sébastien Kerleau, Clément W. Royer

    Positive spanning sets span a given vector space by nonnegative linear combinations of their elements. These have attracted significant attention in recent years, owing to their extensive use in derivative-free optimization. In this setting, the quality of a positive spanning set is assessed through its cosine measure, a geometric quantity that expresses how well such a set covers the space of interest. In this paper, we investigate the construction of positive $k$-spanning sets with geometrical guarantees. Our results build on a recently identified type of positive spanning sets called orthogonally structured positive bases. We first describe how to identify such sets and compute their cosine measure efficiently. We then focus our study on positive $k$-spanning sets, for which we provide a complete description, as well as a new notion of cosine measure that accounts for the resilient nature of such sets. By combining our results, we are able to use orthogonally structured positive bases to create positive $k$-spanning sets with guarantees on the value of their cosine measures.

  3. arXiv:2112.08411 (Published 2021-12-15)

    Error Analysis of Surrogate Models Constructed through Operations on Sub-models

    Yiwen Chen, Gabriel Jarry-Bolduc, Warren Hare

    Model-based methods are popular in derivative-free optimization (DFO). In most of them, a single model function is built to approximate the objective function. This is generally based on the assumption that the objective function is one blackbox. However, some real-life and theoretical problems show that the objective function may consist of several blackboxes. In those problems, the information provided by each blackbox may not be equal. In this situation, one could build multiple sub-models that are then combined to become a final model. In this paper, we analyze the relation between the accuracy of those sub-models and the model constructed through their operations. We develop a broad framework that can be used as a theoretical tool in model error analysis and future research in DFO algorithms design.

  4. arXiv:2104.11821 (Published 2021-04-23)

    Approximating the diagonal of a Hessian: which sample set of points should be used

    Gabriel Jarry-Bolduc

    An explicit formula to approximate the diagonal entries of the Hessian is introduced. When the derivative-free technique called \emph{generalized centered simplex gradient} is used to approximate the gradient, then the formula can be computed for only one additional function evaluation. An error bound is introduced and provides information on the form of the sample set of points that should be used to approximate the diagonal of a Hessian. If the sample set of points is built in a specific manner, it is shown that the technique is $\mathcal{O}(\Delta_S^2)$ accurate approximation of the diagonal entries of the Hessian where $\Delta_S$ is the radius of the sample set.

  5. arXiv:2011.02584 (Published 2020-11-04)

    Hessian approximations

    Warren Hare, Gabriel Jarry-Bolduc, Chayne Planiden

    This work introduces the nested-set Hessian approximation, a second-order approximation method that can be used in any derivative-free optimization routine that requires such information. It is built on the foundation of the generalized simplex gradient and proved to have an error bound that is on the order of the maximal radius of the two sets used in its construction. We show that when the points used in the computation of the nested-set Hessian have a favourable structure, (n+1)(n+2)/2 function evaluations are sufficient to approximate the Hessian. However, the nested-set Hessian also allows for evaluation sets with more points without negating the error analysis. Two calculus-based approximation techniques of the Hessian are developed and some advantages of the same are demonstrated.

  6. arXiv:2004.03507 (Published 2020-04-07)

    A deterministic algorithm to compute the cosine measure of a finite positive spanning set

    Warren Hare, Gabriel Jarry-Bolduc

    Originally developed in 1954, positive bases and positive spanning sets have been found to be a valuable concept in derivative-free optimization (DFO). The quality of a positive basis (or positive spanning set) can be quantified via the {\em cosine measure} and convergence properties of certain DFO algorithms are intimately linked to the value of this measure. However, it is unclear how to compute the cosine measure for a positive basis from the definition. In this paper, a deterministic algorithm to compute the cosine measure of any positive basis or finite positive spanning set is provided. The algorithm is proven to return the exact value of the cosine measure in finite time.