Nonlinear Programming
Mathwrist C++ API Series

(October 5, 2023)

Abstract

This document details the C++ programming interface of nonlinear programming (NLP) features in Mathwrist’s Numerical Programming Library (NPL). Please refer to our NLP white paper for technical overview.

1 Introduction

Let $\psi(\mathbf{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a general smooth function with gradient $\mathbf{g}(\mathbf{x})$ and Hessian $\mathbf{H}(\mathbf{x})$ . In a very general setup, nonlinear programming (NLP) solves the following optimization problem,

	$\displaystyle\min_{x\in\mathbb{R}^{n}}\psi(\mathbf{x}),\mbox{ s.t. }$		(1)
			(2)
	$\displaystyle\mathbf{c}_{l}\leq c(\mathbf{x})\leq\mathbf{c}_{u}$		(3)
	$\displaystyle\mathbf{b}_{l}\leq\mathbf{A}\mathbf{x}\leq\mathbf{b}_{u}$		(4)
	$\displaystyle\mathbf{x}_{l}\leq\mathbf{x}\leq\mathbf{x}_{u}$		(5)

In the constraint part, $\mathbf{b}_{l}\leq\mathbf{A}\mathbf{x}\leq\mathbf{b}_{u}$ is referred as general linear constraints. $\mathbf{l}\leq\mathbf{x}\leq\mathbf{u}$ is referred as simple bound constraints. $\mathbf{c}_{l}\leq c(\mathbf{x})\leq\mathbf{c}_{u}$ is a list of nonlinear constraints. The nonlinear constraint function $c(\mathbf{x})$ is assumed to be at least twice differentiable.

Class NonlinearProg in header file “non_linear_prog.h” is the base class to solve NLP problems. This is in analogy to the LinearProg base class for linear programming (LP) problems.

1.1 NLP Specification

A NLP problem is represented by the nested struct NonlinearProg::Problem inside NonlinearProg class.

1 struct Problem

2 {

3 const FunctionND& f_x;

4 const VtrValueFunctionND& c_x;

5 LinearProg::Constraints lc;

6 ftl::Buffer<Bound> bounds_nonlinear;

8 Problem(const FunctionND& fx, const VtrValueFunctionND& cx);

9 };

Description:

1.

Line 3, struct member f_x holds a constant reference to the NLP objective fuction $\psi(\mathbf{x})$ . REQUIRED: The actual object referred by f_x needs be alive during the life cycle of solving the NLP problem.
2.

Line 4, struct member c_x holds a constant reference to the nonlinear constraint functions $c(\mathbf{x})$ . REQUIRED: The actual object referred by c_x needs be alive during the life cycle of solve the NLP problem.
3.

Line 5, struct member lc stores the general linear constraints and simple bound constraints. Please refer to our LP API for the details of linear constraint specification.
4.

Line 6, struct member bounds_nonlinear stores the lower and upper bounds $(\mathbf{c}_{l},\mathbf{c}_{u})$ for the nonlinear constraints $c(\mathbf{x})$ .

REQUIRED: The size of bounds_nonlinear should be same as the size of nonlinear constraint function $c(\mathbf{x})$ .
5.

Line 8 is the constructor of NLP problems. Parameter fx is a constant reference to the NLP objective function $\psi(\mathbf{x})$ that is to be stored in struct data member f_x. Parameter cx is a constant reference to the NLP nonlinear constraint function $c(\mathbf{x})$ that is to be stored in struct data member c_x.

1.2 Constructor

1 protected:

2 NonlinearProg(const Problem& nlp);

Description:

The constructor saves a constant reference of the given NLP problem specification as a class data member. REQUIRED: The object passed as reference by parameter nlp needs be alive during the lifecycle of the NLP solver.

1.3 Destructor

1 virtual ~NonlinearProg() {}

Description:

Virtual destructor to properly free resouces from derived classes.

1.4 NLP Problem

1 const Problem& problem() const;

Description:

Return a constant reference to the NLP problem specification stored in NonlinearProg base class.

1.5 Solver Operator

1 virtual double operator() (Matrix& x) = 0;

Description:

It is the public interface of solving a NLP problem to be implemented by derived NLP solvers. Parameter x holds the initial guess on call and holds the solution $\mathbf{x}^{*}$ on return. The function returns objective function value $\psi(\mathbf{x}^{*})$ . REQUIRED: x is a $n\times 1$ vector.

2 SQP Active Set

1 class SQP_ActiveSet : public NonlinearProg,public IterativeMethod

SQP_ActiveSet class in header sqp_active_set.h inherits from NonlinearProg and IterativeMethod base classes and solves a NLP problem using sequential quadratic programming (SQP) method.

The SQP method consists of major iterations and minor iterations. At each major iteration, it solves a sub quadratic programming (QP) problem with minor iterations. For the control of max number of major iterations and convergence, please refer to the “Iterative Methods” section in our “1-d and n-d Functions” API documentation. For the details of solving a quadratic programming problem, please refer to our “Quadratic Programming” white paper and API series.

2.1 Constructor

1 explicit SQP_ActiveSet(const NonlinearProg::Problem& prob);

Description:

Create a SQP active-set solver with a given NLP problem specification. REQUIRED: The object passed as reference from parameter prob needs be kept alive during the lifecycle of the NLP active-set solver.

2.2 Destructor

1 ~SQP_ActiveSet();

Description:

Free all resources used by the solver.

2.3 Solver Operator

1 double operator() (Matrix& x);

Description:

This function implements the public interface of the NonlinearProg base class. On call, parameter x holds the initial guess. On return it holds the solution $\mathbf{x}^{*}$ found by the solver. This function also returns $\psi(\mathbf{x}^{*})$ . REQUIRED: x is a $n\times 1$ vector.

2.4 Elastic Programming Control

1 void set_elastic_penalty(double p);

2 double elastic_penalty() const;

3 void set_max_elastic_penalty(double p);

4 double max_elastic_penalty() const;

Description:

At each major iteration of the SQP method, we linearize all nonlinear constraints $c(\mathbf{x})$ . If the algorithm fails to find a feasible point wrt the linearization of $c(\mathbf{x})$ , it then enters elastic programming (EP) mode and treats the linearized constraints as elastic constraints.

The algorithm uses an initial EP penalty when it enters EP mode and gradually increases the penalty factor to the maximum penalty level if it keeps running in EP mode. As soon as a feasible point is found at a new major iteration, the algorithm quits from the EP mode.

1.

Set the initial penalty factor for violated elastic constraints.
2.

Return the initial penalty factor for violated elastic constraints.
3.

Set the upper limit that elastic penalty factors can be increased to.
4.

Return the upper limit of elastic penalty factors.

2.5 Sup QP Control

At each major iteration of the SQP method, we solve a sub QP problem using a customized QP active-set method. The following control functions are relevant to this sub QP solver.

2.5.1 Minor Iterations

1 void set_qp_max_iter(size_t max_iter);

2 size_t qp_max_iter() const;

Description:

1.

Set the max number of minor iterations allowed to solve a sub QP problem.
2.

Return the max number of minor iterations allowed to solve a sub QP problem.

2.5.2 Convergence Tolerance

1 void set_qp_converge_tolerance(double eps);

2 double qp_converge_tolerance() const;

Description:

1.

Set the convergence tolerance to test Lagrange multiplier conditions in sub QP problems.
2.

Return the convergence tolerance used to test Lagrange multiplier conditions in sub QP problems.

2.5.3 Stationary Tolerance

1 void set_qp_stationary_tolerance(double eps);

2 double qp_stationary_tolerance() const;

Description:

1.

Set the stationary tolerance to test stationary conditions in sub QP problems.
2.

Return the stationary tolerance used to test stationary conditions in sub QP problems.

2.5.4 Crash Start Radius

1 void set_crash_start_radius(double r);

2 double crash_start_radius() const;

Description:

1.

Set the “Crash start” radius to solve a sub QP at major iterations.
2.

Return the “Crash start” radius used by the solver.

2.6 Line Search Control

At each major iteration and after the termination of a sub QP problem, the algorithm obtains a primal-dual step change $(\mathbf{d},\xi)$ to the sub QP optimal point. It then uses a line search method to compute an acceptable step length $\alpha$ to move along $(\mathbf{d},\xi)$ by a merit function.

1 void set_max_step(double dx);

2 double max_step() const;

3 void set_step_length_tolerance(double eps);

4 double step_length_tolerance() const;

Description:

1.

Set the max line search step length $\bar{\alpha}=\frac{\Delta x}{|\mathbf{d}|_{\infty}}$ , where $\Delta x$ is passed from parameter dx. The line search method ensures the actually step length $\alpha<\bar{\alpha}$ .
2.

Return the max amount of change $\Delta x$ in the line search.
3.

Set the convergence tolerance of step length in line search. Step length interval $(\alpha_{l},\alpha_{u})$ is considered converged when $\alpha_{l}$ numerically equals to $\alpha_{u}$ at this tolerance level.
4.

Return the step length convergence tolerance being used.

Nonlinear Programming Mathwrist C++ API Series

Abstract

1 Introduction

1.1 NLP Specification

1.2 Constructor

1.3 Destructor

1.4 NLP Problem

1.5 Solver Operator

2 SQP Active Set

2.1 Constructor

2.2 Destructor

2.3 Solver Operator

2.4 Elastic Programming Control

2.5 Sup QP Control

2.5.1 Minor Iterations

2.5.2 Convergence Tolerance

2.5.3 Stationary Tolerance

2.5.4 Crash Start Radius

2.6 Line Search Control

Nonlinear Programming
Mathwrist C++ API Series