Linearly Constrained Optimization
Mathwrist C++ API Series
Abstract
This document details the C++ programming interface of linearly constrained (LC) optimization features in Mathwrist’s Numerical Programming Library (NPL). Please refer to our LC white paper for technical overview.
1 Introduction
Let be a general smooth function with gradient and Hessian . In other words, is at least twice continuously differentiable. Linearly constrained optimization solves the following minimization problem subject to a set of general linear constraints and simple bound constraints,
(1) |
In header file ”gs_active_set.h”, we provide two general LC solver classes
-
•
GS_ActiveSetNewton
-
•
GS_ActiveSetQuasiNewton
that embde line search methods within the active-set framework to solve problem (1).
A special case of linearly constrained optimization is when there are only simple bound constraints imposed on , also known as box constrained optimization,
(2) |
For efficiency consideration, this special case is separately treated in header file ”gs_simple_bound.h” by the following two solver classes.
-
•
GS_SimpleBoundNewton
-
•
GS_SimpleBoundQuasiNewton
2 Active-set Solvers
2.1 Inheritance Hierarchy
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.
2.2 Step Length Control
Description:
-
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 along the direction . Users can set a max step length upper bound based on the domain knowledge about so that .
-
2.
Return the max step length used in line search method.
2.3 Solver Operator
Description:
Given an initial guess, compute the solution of the general LC problem (1) and return . Parameter x holds initial guess on call and solution on return.
2.4 Newton Method
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 . 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 . 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.
2.5 Quasi-Newton Method
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.
3 Simple Bound Solvers
3.1 Inheritance Hierarchy
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 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.
3.2 Step Length Control
Description:
-
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 along the direction . Users can set a max step length upper bound based on the domain knowledge about so that .
-
2.
Return the max step length used in line search method.
3.3 Stationary Tolerance Control
Description:
-
1.
Set the tolerance level to determine if stationary condition is satisfied. At an iteration point , if or , we consider is stationary wrt the current working set of constraints.
-
2.
Return the stationary tolerance control .
3.4 Solver Operator
Description:
Given an initial guess, compute the solution of the box constrained problem (2) and return . Parameter x holds initial guess on call and solution on return.
3.5 Newton Method
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 . 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 .
Parameter discrete controls whether the Hessian matrix is approximated by a finite difference method or explicitly computed by the objective function . 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.
3.6 Quasi-Newton Method
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.