de.labathome.trustconstr.QPSubproblem

public class QPSubproblem extends Object

Quadratic-programming subproblem helpers used inside the trust-region SQP / IP loops: the projected-CG inner solver, the equality-constrained KKT direct factorization, the modified-dogleg trust-region step, and the segment/box/sphere intersection routines that drive trust-region step acceptance.

Constructor Summary

Constructors

Constructor

Description

QPSubproblem()
Method Summary

Modifier and Type

Method

Description

static IntersectionResult

boxIntersections(double[] z, double[] d, double[] lb, double[] ub)

Find the intersection of a segment (or line) with the rectangular box lb ≤ x ≤ ub, where the segment is parameterised as x(t) = z + t*d.

static IntersectionResult

boxIntersections(double[] zIn, double[] dIn, double[] lbIn, double[] ubIn, boolean entireLine)

Find the intersection of a segment (or line) with the rectangular box lb ≤ x ≤ ub, where the segment is parameterised as x(t) = z + t*d.

static IntersectionResult

boxSphereIntersections(double[] z, double[] d, double[] lb, double[] ub, double trustRadius)

Convenience overload of boxSphereIntersections(double[], double[], double[], double[], double, boolean) with entireLine = false.

static IntersectionResult

boxSphereIntersections(double[] z, double[] d, double[] lb, double[] ub, double trustRadius, boolean entireLine)

Find the intersection of a segment (or line) with both a box lb ≤ x ≤ ub and a ball ||x|| ≤ trustRadius.

static IntersectionResult[]

boxSphereIntersectionsWithExtraInfo(double[] z, double[] d, double[] lb, double[] ub, double trustRadius)

Convenience overload of boxSphereIntersectionsWithExtraInfo(double[], double[], double[], double[], double, boolean) with entireLine = false.

static IntersectionResult[]

boxSphereIntersectionsWithExtraInfo(double[] z, double[] d, double[] lb, double[] ub, double trustRadius, boolean entireLine)

Find the intersection between segment (or line) and box/sphere constraints.

static Matrix[]

eqpKktFact(Matrix H, Matrix c, Matrix A, Matrix b)

Solve the equality-constrained quadratic program

static boolean

insideBoxBoundaries(double[] x, double[] lb, double[] ub)

Check whether lb ≤ x ≤ ub elementwise.

static Matrix

modifiedDogleg(Matrix A, Object Y, Matrix b, double trustRadius, double[] lb, double[] ub)

Approximately minimize 1/2 ||A x + b||^2 subject to ||x|| < Delta and lb ≤ x ≤ ub using a modified dogleg approach.

static CGInfo

projectedCG(LinearOperator H, Matrix c, Object Z, Object Y, Matrix b)

Solve the equality-constrained quadratic program

static CGInfo

projectedCG(LinearOperator H, Matrix c, Object Z, Object Y, Matrix b, double trustRadius, double[] lb, double[] ub, double tolerance)

Solve EQP problem with projected CG method.

static CGInfo

projectedCG(LinearOperator H, Matrix c, Object Z, Object Y, Matrix b, double trustRadius, double[] lb, double[] ub, double tolerance, long maxIterations, long maxInfeasibleIterations, boolean returnAll)

Solve the equality-constrained quadratic program

static double[]

reinforceBoxBoundaries(double[] x, double[] lb, double[] ub)

Return clipped value of x.

static IntersectionResult

sphereIntersections(double[] z, double[] d, double trustRadius)

Find the intersection between segment (or line) and spherical constraints.

static IntersectionResult

sphereIntersections(double[] z, double[] d, double trustRadius, boolean entireLine)

Find the intersection of a segment (or line) with the ball ||x|| ≤ trustRadius, where the segment is parameterised as x(t) = z + t*d.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- QPSubproblem
  
  public QPSubproblem()
Method Details
- eqpKktFact
  
  public static Matrix[] eqpKktFact(Matrix H, Matrix c, Matrix A, Matrix b)
  Solve the equality-constrained quadratic program
  minimize q(x) = 1/2 x^T G x + x^T c subject to A x = b
  where G is the symmetric n x n Hessian, c, x are length-n vectors, and A is the m x n Jacobian of constraints (with m ≤ n).
  See Nocedal & Wright, Numerical Optimization, 2nd ed. (2006), chapter 16.1.
  Parameters:
  
  H - n x n Hessian matrix of the EQP problem
  
  c - length-n gradient of the quadratic objective function
  
  A - m x n Jacobian matrix of the equality constraints
  
  b - length-m right-hand side of the constraint equation, sign-flipped
  
  Returns:
  
  two-element array [x, lambda] containing the solution and Lagrange multipliers
- sphereIntersections
  
  public static IntersectionResult sphereIntersections(double[] z, double[] d, double trustRadius)
  
  Find the intersection between segment (or line) and spherical constraints.
  Find the intersection between the segment (or line) defined by the parametric equation x(t) = z + t*d and the ball ||x|| <= trust_radius.
  
  Parameters:
  
  z - length-n initial point
  
  d - length-n direction
  
  trustRadius - ball radius
  
  Returns:
  
  the t-interval over which the segment lies inside the ball, or intersect=false if it never enters
- sphereIntersections
  
  public static IntersectionResult sphereIntersections(double[] z, double[] d, double trustRadius, boolean entireLine)
  
  Find the intersection of a segment (or line) with the ball ||x|| ≤ trustRadius, where the segment is parameterised as x(t) = z + t*d.
  
  Parameters:
  
  z - length-n initial point
  
  d - length-n direction
  
  trustRadius - ball radius
  
  entireLine - if true, allow t to range over all of R; if false, restrict 0 ≤ t ≤ 1
  
  Returns:
  
  the t-interval over which the segment lies inside the ball, or intersect=false if it never enters
- boxIntersections
  
  public static IntersectionResult boxIntersections(double[] z, double[] d, double[] lb, double[] ub)
  
  Find the intersection of a segment (or line) with the rectangular box lb ≤ x ≤ ub, where the segment is parameterised as x(t) = z + t*d. Convenience overload that disables the "entire line" mode.
  
  Parameters:
  
  z - length-n initial point
  
  d - length-n direction
  
  lb - length-n lower bounds of the box
  
  ub - length-n upper bounds of the box
  
  Returns:
  
  (tA, tB, intersect) -- the t-interval over which the segment lies inside the box, or intersect=false.
- boxIntersections
  
  public static IntersectionResult boxIntersections(double[] zIn, double[] dIn, double[] lbIn, double[] ubIn, boolean entireLine)
  
  Find the intersection of a segment (or line) with the rectangular box lb ≤ x ≤ ub, where the segment is parameterised as x(t) = z + t*d.
  
  Parameters:
  
  zIn - length-n initial point
  
  dIn - length-n direction
  
  lbIn - length-n lower bounds of the box
  
  ubIn - length-n upper bounds of the box
  
  entireLine - if true, allow t to range over all of R; if false, restrict 0 ≤ t ≤ 1
  
  Returns:
  
  the t-interval over which the segment lies inside the box, or intersect=false if it never enters
- boxSphereIntersections
  
  public static IntersectionResult boxSphereIntersections(double[] z, double[] d, double[] lb, double[] ub, double trustRadius)
  
  Convenience overload of boxSphereIntersections(double[], double[], double[], double[], double, boolean) with entireLine = false.
  
  Parameters:
  
  z - initial point
  
  d - direction
  
  lb - box lower bounds
  
  ub - box upper bounds
  
  trustRadius - sphere radius
  
  Returns:
  
  the intersection t-interval
- boxSphereIntersections
  
  public static IntersectionResult boxSphereIntersections(double[] z, double[] d, double[] lb, double[] ub, double trustRadius, boolean entireLine)
  
  Find the intersection of a segment (or line) with both a box lb ≤ x ≤ ub and a ball ||x|| ≤ trustRadius.
  
  Parameters:
  
  z - initial point
  
  d - direction
  
  lb - box lower bounds
  
  ub - box upper bounds
  
  trustRadius - sphere radius
  
  entireLine - if true, allow t to range over all of R; if false, restrict to the segment
  
  Returns:
  
  the intersection t-interval
- boxSphereIntersectionsWithExtraInfo
  
  public static IntersectionResult[] boxSphereIntersectionsWithExtraInfo(double[] z, double[] d, double[] lb, double[] ub, double trustRadius)
  
  Convenience overload of boxSphereIntersectionsWithExtraInfo(double[], double[], double[], double[], double, boolean) with entireLine = false.
  
  Parameters:
  
  z - initial point
  
  d - direction
  
  lb - box lower bounds
  
  ub - box upper bounds
  
  trustRadius - sphere radius
  
  Returns:
  
  three-element array {boxSphere, sphere, box} of IntersectionResult
- boxSphereIntersectionsWithExtraInfo
  
  public static IntersectionResult[] boxSphereIntersectionsWithExtraInfo(double[] z, double[] d, double[] lb, double[] ub, double trustRadius, boolean entireLine)
  
  Find the intersection between segment (or line) and box/sphere constraints.
  Find the intersection between the segment (or line) defined by the parametric equation x(t) = z + t*d, the rectangular box lb <= x <= ub and the ball ||x|| <= trust_radius.
  
  Parameters:
  
  z - [n] initial point
  
  d - [n] direction
  
  lb - [n] lower bounds to each one of the components of x, used to delimit the rectangular box
  
  ub - [n] upper bounds to each one of the components of x, used to delimit the rectangular box
  
  trustRadius - ball radius
  
  entireLine - When true, the function returns the intersection between the line x(t) = z + t*d (t can assume any value) and the constraints. When false, the function returns the intersection between the segment x(t) = z + t*d, 0 <= t <= 1 and the constraints.
  
  Returns:
  
  [3] The first element is the combined intersection result. The second element is the intersection result from sphereIntersections. The third element is the intersection result from boxIntersections.
- reinforceBoxBoundaries
  
  public static double[] reinforceBoxBoundaries(double[] x, double[] lb, double[] ub)
  
  Return clipped value of x.
  
  Parameters:
  
  x - [n] position vector to force into bounds
  
  lb - [n] lower bounds
  
  ub - [n] upper bounds
  
  Returns:
  
  coerced copy of x such that lb ≤ x ≤ ub for all entries
- insideBoxBoundaries
  
  public static boolean insideBoxBoundaries(double[] x, double[] lb, double[] ub)
  
  Check whether lb ≤ x ≤ ub elementwise.
  
  Parameters:
  
  x - length-n position to test
  
  lb - length-n lower bounds
  
  ub - length-n upper bounds
  
  Returns:
  
  true iff every entry satisfies lb[i] ≤ x[i] ≤ ub[i]
- modifiedDogleg
  
  public static Matrix modifiedDogleg(Matrix A, Object Y, Matrix b, double trustRadius, double[] lb, double[] ub)
  
  Approximately minimize 1/2 ||A x + b||^2 subject to ||x|| < Delta and lb ≤ x ≤ ub using a modified dogleg approach. Implementation based on Byrd-Hribar-Nocedal (1999), pp.885-886.
  
  Parameters:
  
  A - m x n matrix in the minimization problem (m < n expected)
  
  Y - Matrix or LinearOperator that applies the projection Q = A^T (A A^T)^-^1; for any input x, y = Q x is the minimum-norm solution of A y = x
  
  b - length-m vector in the minimization problem
  
  trustRadius - trust radius Delta (sphere boundary)
  
  lb - length-n lower bounds; Double.NEGATIVE_INFINITY disables the bound for that component. Algorithm assumes lb ≤ 0
  
  ub - length-n upper bounds; Double.POSITIVE_INFINITY disables the bound for that component. Algorithm assumes ub ≥ 0
  
  Returns:
  
  length-n solution vector
- projectedCG
  
  public static CGInfo projectedCG(LinearOperator H, Matrix c, Object Z, Object Y, Matrix b)
  Solve the equality-constrained quadratic program
  minimize 1/2 x^T H x + x^T c subject to A x + b = 0
  with the projected conjugate-gradient method. Convenience overload with no trust-region or box constraints.
  Parameters:
  
  H - operator that computes H v on a length-n vector
  
  c - length-n gradient of the quadratic objective
  
  Z - Matrix or LinearOperator that projects x into the null space of A
  
  Y - Matrix or LinearOperator that, given b, returns the minimum-norm solution of A x + b = 0
  
  b - length-m right-hand side of the constraint equation
  
  Returns:
  
  solution vector and additional CG info
- projectedCG
  
  public static CGInfo projectedCG(LinearOperator H, Matrix c, Object Z, Object Y, Matrix b, double trustRadius, double[] lb, double[] ub, double tolerance)
  
  Solve EQP problem with projected CG method.
  Solve equality-constrained quadratic programming problem min 1/2 x^T H x + x^t c subject to A x + b = 0 and, possibly, to trust region constraints ||x|| < trust_radius and box constraints lb <= x <= ub.
  Without spherical or box constraints and with enough iterations, the method returns the exact optimum. With those constraints active, the returned value is only an inexpensive approximation.
  
  Parameters:
  
  H - operator that computes H v on a length-n vector
  
  c - length-n gradient of the quadratic objective
  
  Z - Matrix or LinearOperator that projects x into the null space of A
  
  Y - Matrix or LinearOperator that, given b, returns the minimum-norm solution of A x + b = 0
  
  b - length-m right-hand side of the constraint equation
  
  trustRadius - trust-region radius; Double.POSITIVE_INFINITY disables the trust-region constraint
  
  lb - length-n lower bounds; Double.NEGATIVE_INFINITY disables the bound for that component
  
  ub - length-n upper bounds; Double.POSITIVE_INFINITY disables the bound for that component
  
  tolerance - termination tolerance for the projected residual
  
  Returns:
  
  solution vector and additional CG info
- projectedCG
  
  public static CGInfo projectedCG(LinearOperator H, Matrix c, Object Z, Object Y, Matrix b, double trustRadius, double[] lb, double[] ub, double tolerance, long maxIterations, long maxInfeasibleIterations, boolean returnAll)
  Solve the equality-constrained quadratic program
  minimize 1/2 x^T H x + x^T c subject to A x + b = 0 and (optionally) ||x|| < trustRadius, lb ≤ x ≤ ub
  with the projected conjugate-gradient method (Algorithm 6.2 of Gould-Hribar-Nocedal, 2001).
  Without spherical or box constraints and with enough iterations, the method returns the exact optimum. With those constraints active, the returned value is only an inexpensive approximation.
  Parameters:
  
  H - operator that computes H v
  
  c - length-n gradient of the quadratic objective
  
  Z - Matrix or LinearOperator projecting into null(A)
  
  Y - Matrix or LinearOperator for the minimum-norm solution of A x + b = 0
  
  b - length-m right-hand side of the constraint equation
  
  trustRadius - trust-region radius; Double.POSITIVE_INFINITY disables the trust-region constraint
  
  lb - length-n lower bounds (use -inf to disable per dim)
  
  ub - length-n upper bounds (use +inf to disable per dim)
  
  tolerance - termination tolerance for the projected residual
  
  maxIterations - max CG iterations; -1 for the default n - m
  
  maxInfeasibleIterations - max iterations spent infeasible w.r.t. box constraints; -1 for the default n - m
  
  returnAll - if true, the result includes the iterate trajectory
  
  Returns:
  
  solution vector and additional CG info

Class QPSubproblem

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Details

QPSubproblem

Method Details

eqpKktFact

sphereIntersections

sphereIntersections

boxIntersections

boxIntersections

boxSphereIntersections

boxSphereIntersections

boxSphereIntersectionsWithExtraInfo

boxSphereIntersectionsWithExtraInfo

reinforceBoxBoundaries

insideBoxBoundaries

modifiedDogleg

projectedCG

projectedCG

projectedCG