Skip to content

Fix line search for grad reconstruction method #13

@nelimee

Description

@nelimee

The sqt.fit.grad.line_search function does not work properly on some (most? all?) inputs as described in the docstring:

This method is currently not working correctly and systematically returns a value of 1e-5 that has been empirically determined as sufficiently small for the optimisation problems I had. This value might be too large for other optimisation problems.
Some observations on this method: it seems like the line search does not work because there are cases where the projection makes the actual descent direction in the opposite direction of the gradient. In other words, if d is the descent direction, obtained with the formula
d = proj(rho - gradient_step * gradient) - rho
then there are cases where <d , gradient> < 0, i.e. d does not follow the gradient anymore but goes backward. I suspect this is due to some conditions that are not fulfilled by the problem (convexity, continuity, condition on the projection, ...?), but I do not have any proof yet.
See https://sites.math.washington.edu/~burke/crs/408/notes/nlp/gpa.pdf

Fixing it would:

  1. improve performance of the grad reconstruction method,
  2. make the grad reconstruction method more robust, as a fixed step of 1e-5 does not provide us any guarantee of convergence.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingenhancementNew feature or requestnumericsIssue with numerical methodsreconstructionIssues related to the reconstruction of quantum states from observed frequencies

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions