Linearly Constrained Optimization
Mathwrist C++ API Series

Class GS_ActiveSet in header file gs_active_set.h is the common base class for general LC solvers. It combines line search method with active-set framework. The concrete Newton and Quasi-Newton solvers derived from GS_ActiveSet compute descent directions using modified Newton or Quasi-Newton method respectively.

Please refer to our linear programming API documentation for the details of ActiveSet base class.

Description:

1. 1.

   Set the max step length in line search method. After computing a descent direction $𝐩$, we use the line search method to determine an acceptable step length $\widehat{\alpha }$ along the direction $𝐩$. Users can set a max step length $\overline{\alpha }$ upper bound based on the domain knowledge about $\psi (𝐱)$ so that $\widehat{\alpha }\le \overline{\alpha }$.

2. 2.

   Return the max step length used in line search method.

Description:

Given an initial guess, compute the solution ${𝐱}^{*}$ of the general LC problem (1) and return $\psi ({𝐱}^{*})$. Parameter x holds initial guess on call and solution ${𝐱}^{*}$ on return.

Description:

This is the constructor to create a solver object using active-set and line search modified Newton methods to solve LC problem (1).

Parameter obj is a constant reference to the n-d objective function $\psi (𝐱)$. The solver class stores the reference as a data member. REQUIRED: The n-d function object referred by obj needs be alive in the lifecycle of the LC solver.

Parameter constr is a constant reference to the constraint specification object in LC problem formulation (1). The solver’s ActiveSet base class stores the reference as a data member. Please refer to our LP API documentation for the details of constraint specification. REQUIRED: The constraint object constr needs be alive in the lifecycle of the LC solver.

Parameter discrete controls whether the Hessian matrix $𝐇(𝐱)$ is approximated by a finite difference method or explicitly computed by the objective function $\psi (𝐱)$. When discrete is true, FunctionND::hess_fwd_diff_grad() is used to approximate $𝐇(𝐱)$. Otherwise, users need explicitly compute $𝐇(𝐱)$ in the implementation of FunctionND::eval() function.

Description:

This is the constructor to create a solver object using active-set and line search Quasi-Newton methods to solve LC problem (1). Parameters obj and constr are exactly same as the GS_ActiveSetNewton constructor.

Class GS_SimpleBound in header file gs_simple_bound.h is the common base class for box constrained optimization solvers. GS_SimpleBound inherits from IterativeMethod. Please refer to our “1-d and n-d Functions” API documentation for iteration and convergence control of IterativeMethod.

The GS_SimpleBound base class implements a simplified version of active-set framework that just handles simple bound operations. It also uses the line search method to compute an acceptable step length $\widehat{\alpha }$ along a descent direction $𝐩$. The concrete simple bound solvers GS_SimpleBoundNewton and GS_SimpleBoundQuasiNewton compute the direction $𝐩$ using modified Newton and Quasi-Newton methods respectively.

Description:

1. 1.

   Set the max step length in line search method. After computing a descent direction $𝐩$, we use the line search method to determine an acceptable step length $\widehat{\alpha }$ along the direction $𝐩$. Users can set a max step length $\overline{\alpha }$ upper bound based on the domain knowledge about $\psi (𝐱)$ so that $\widehat{\alpha }\le \overline{\alpha }$.

2. 2.

   Return the max step length used in line search method.

Description:

1. 1.

   Set the tolerance level ${ϵ}_s$ to determine if stationary condition is satisfied. At an iteration point ${𝐱}_k$, if or , we consider ${𝐱}_k$ is stationary wrt the current working set of constraints.

2. 2.

   Return the stationary tolerance control ${ϵ}_s$.

Description:

Given an initial guess, compute the solution ${𝐱}^{*}$ of the box constrained problem (2) and return $\psi ({𝐱}^{*})$. Parameter x holds initial guess on call and solution ${𝐱}^{*}$ on return.

Description:

This is the constructor to create a solver object that uses active-set and line search modified Newton methods to solve box constrained problem (2).

Parameter obj is a constant reference to the n-d objective function $\psi (𝐱)$. The solver class stores the reference as a data member. REQUIRED: The n-d function object referred by obj needs be alive in the lifecycle of the solver.

Parameter simple_bounds is a buffer of simple bounds in problem formulation (2). All simple bounds are copied to the solver’s GS_SimpleBound base class as data member. Please refer to our LP API documentation for the details of Bound specification. REQUIRED: The size of the simple bound buffer should be same as the dimension size of objective function $\psi (𝐱)$.

Parameter discrete controls whether the Hessian matrix $𝐇(𝐱)$ is approximated by a finite difference method or explicitly computed by the objective function $\psi (𝐱)$. When discrete is true, FunctionND::hess_fwd_diff_grad() is used to approximate $𝐇(𝐱)$. Otherwise, users need explicitly compute $𝐇(𝐱)$ in the implementation of FunctionND::eval() function.

Description:

This is the constructor to create a solver object that uses active-set and line search Quasi-Newton methods to solve box constrained problem (2). Parameters obj and constr are exactly same as the GS_SimpleBoundQuasiNewton constructor.