Package de.labathome.trustconstr

Class BarrierSubproblem

java.lang.Object
de.labathome.trustconstr.BarrierSubproblem
public class BarrierSubproblem extends Object
Barrier optimization problem: 
 minimize fun(x) - barrier_parameter*sum(log(s))
 subject to: constr_eq(x)     = 0
           constr_ineq(x) + s = 0

  • Constructor Details

    • BarrierSubproblem

      public BarrierSubproblem(Matrix x0, Matrix s0, ToDoubleBiFunction<Matrix,Object> fun, BiFunction<Matrix,Object,Matrix> grad, LagrangeHessian lagrHess, long nVars, long nIneq, long nEq, Constraint constr, Jacobian jac, double barrierParameter, double tolerance, boolean[] enforceFeasibility, GlobalStoppingCriteria globalStopCriteria, double xtol, double fun0, Matrix grad0, Matrix constrIneq0, Matrix jacIneq0, Matrix constrEq0, Matrix jacEq0)
      Construct the barrier subproblem at a starting iterate.
      Parameters:
      x0 - starting point in the variable space (nVars x 1)
      s0 - starting slacks (nIneq x 1); must be strictly positive
      fun - objective (x, args) -> f(x)
      grad - gradient (x, args) -> gradf(x)
      lagrHess - Hessian-of-Lagrangian (x, v) -> grad^2L(x, v)
      nVars - number of decision variables
      nIneq - number of canonical inequality rows
      nEq - number of canonical equality rows
      constr - combined-constraint evaluator
      jac - combined-constraint Jacobian evaluator
      barrierParameter - initial log-barrier coefficient
      tolerance - initial inner-loop tolerance
      enforceFeasibility - per-canonical-ineq strict-feasibility flag; may be null
      globalStopCriteria - outer-loop termination predicate
      xtol - trust-region radius termination threshold
      fun0 - fun(x0)
      grad0 - grad(x0)
      constrIneq0 - constr_ineq(x0) (nIneq x 1)
      jacIneq0 - inequality Jacobian at x0 (nIneq x n)
      constrEq0 - constr_eq(x0) (nEq x 1)
      jacEq0 - equality Jacobian at x0 (nEq x n)

  • Method Details

    • update

      public void update(double barrierParameter, double tolerance)
      Refresh the barrier coefficient and inner-loop tolerance for the next outer iteration.
      Parameters:
      barrierParameter - new log-barrier coefficient
      tolerance - new inner-loop tolerance

    • getSlack

      public Matrix getSlack(Matrix z)
      Slice off the nIneq x 1 slack block from an augmented iterate z = [x; s].
      Parameters:
      z - augmented iterate
      Returns:
      slack subvector s

    • getVariables

      public Matrix getVariables(Matrix z)
      Slice off the nVars x 1 variable block from an augmented iterate z = [x; s].
      Parameters:
      z - augmented iterate
      Returns:
      variable subvector x

    • funAndConstr

      public FunctionAndConstraint funAndConstr(Matrix z)
      Evaluate the barrier function and the augmented constraints at a given augmented iterate z = [x; s]: 
         function(z)    = fun(x) - barrier_parameter * sum(log(s))
   constraints(z) = [   constr_eq(x)     ]
                    [ constr_ineq(x) + s ]
      Parameters:
      z - augmented iterate [x; s] ((nVars + nIneq) x 1)
      Returns:
      barrier objective value and augmented constraint vector

    • getScaling

      public Matrix getScaling(Matrix z)
      Returns the diagonal scaling matrix diag([1...1, s]) that decouples the variable rows from the slack rows in the trust-region step. Identity on the variable rows; the current slack values on the slack rows.
      Parameters:
      z - augmented iterate [x; s]
      Returns:
      (nVars + nIneq) x (nVars + nIneq) diagonal scaling

    • gradAndJac

      public GradientAndJacobian gradAndJac(Matrix z)
      Returns the scaled gradient and Jacobian for the augmented system: 
         gradient = [             grad(x)             ]
              [ -barrier_parameter*ones(n_ineq) ]
   jacobian = [  jac_eq(x)  0 ]
              [ jac_ineq(x) S ]
      Both rescaled by the diagonal returned from getScaling(Matrix).
      Parameters:
      z - augmented iterate [x; s]
      Returns:
      barrier-augmented gradient and Jacobian

    • lagrHessX

      public LinearOperator lagrHessX(Matrix z, Matrix v)
      Lagrangian Hessian with respect to x (the Hx block).
      Parameters:
      z - augmented iterate [x; s]
      v - full Lagrange-multiplier vector (equality + inequality)
      Returns:
      Hx as a LinearOperator

    • lagrHessS

      public Matrix lagrHessS(Matrix z, Matrix v)
      Scaled Lagrangian Hessian with respect to the slacks s, i.e. the S Hs S block. Uses the primal-dual formulation for entries with positive v_ineq and the primal formulation otherwise.
      Parameters:
      z - augmented iterate [x; s]
      v - full Lagrange-multiplier vector (equality then inequality)
      Returns:
      nIneq x 1 diagonal of the S Hs S block

    • lagrangianHessian

      public LinearOperator lagrangianHessian(Matrix z, Matrix v)
      Full augmented Lagrangian Hessian, block-diagonal: 
         [ Hx    0     ]
   [  0  S Hs S  ]
      Parameters:
      z - augmented iterate [x; s]
      v - full Lagrange-multiplier vector (equality + inequality)
      Returns:
      LinearOperator applying the augmented Hessian

    • stoppingCriteria

      public boolean stoppingCriteria(State state, Matrix z, boolean lastIterationFailed, double optimality, double constrViolation, double trustRadius, double penalty, CGInfo cgInfo)
      Stopping criterion for the barrier subproblem; mirrors formula (2.3) from Byrd-Hribar-Nocedal (1999), p.879.
      Parameters:
      state - outer-loop state
      z - augmented iterate [x; s]
      lastIterationFailed - whether the previous step was rejected
      optimality - KKT optimality measure at z
      constrViolation - infinity-norm of the constraint residual
      trustRadius - current trust-region radius
      penalty - current merit-function penalty
      cgInfo - info from the projected-CG inner solve
      Returns:
      true if the inner barrier loop should terminate