Sign in Subscribe

AS (Active Set)

Last updated on 

The Active Set (AS) method is a widely used optimization technique for solving nonlinear programming (NLP) problems with box constraints. It is an iterative algorithm that generates a sequence of feasible points that converges to a local minimum of the objective function. In this article, we will explain the AS method in detail, including its mathematical formulation, convergence properties, and implementation.

Mathematical Formulation of Active Set Method

Consider the following nonlinear programming problem with box constraints:

\begin{aligned} & \underset{\boldsymbol{x}\in\mathbb{R}^n}{\text{minimize}} & & f(\boldsymbol{x}) \ & \text{subject to} & & \boldsymbol{l} \leq \boldsymbol{x} \leq \boldsymbol{u}, \end{aligned}

where $\boldsymbol{x}\in\mathbb{R}^n$ is the decision variable, $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is the objective function, and $\boldsymbol{l}\in\mathbb{R}^n$ and $\boldsymbol{u}\in\mathbb{R}^n$ are the lower and upper bounds on the decision variable, respectively. The Active Set method is based on the following idea: at each iteration, we maintain a set of active constraints that are binding at the current solution, and we solve a quadratic subproblem to update the solution within the active set.

Let $\boldsymbol{x}^$ be the optimal solution of the above problem, and let $S\subseteq{1,\ldots,n}$ be the set of indices of the active constraints at $\boldsymbol{x}^$. Then, the KKT conditions for the problem can be expressed as follows:

\begin{aligned} \nabla f(\boldsymbol{x}^) + \boldsymbol{\mu}_S &= 0, \ \boldsymbol{\mu}_i &= 0, \quad \forall i\notin S, \ \boldsymbol{l}_i \leq x^_i &\leq \boldsymbol{u}_i, \quad \forall i, \ \boldsymbol{\mu}_i (\boldsymbol{x}^_i - \boldsymbol{l}_i) &= 0, \quad \forall i, \ \boldsymbol{\mu}_i (\boldsymbol{u}_i - \boldsymbol{x}^_i) &= 0, \quad \forall i, \end{aligned}

where $\boldsymbol{\mu}\in\mathbb{R}^n$ is the Lagrange multiplier vector. The first equation is the optimality condition, which states that the gradient of the objective function at $\boldsymbol{x}^$ is equal to the negative of the weighted sum of the gradients of the active constraints at $\boldsymbol{x}^$, where the weights are the corresponding Lagrange multipliers. The second equation states that the Lagrange multipliers for the inactive constraints are zero. The third equation is the box constraint, which states that each decision variable is within its lower and upper bounds. The fourth and fifth equations are the complementary slackness conditions, which state that the Lagrange multipliers for the box constraints are zero if the corresponding variable is at its bound, and positive otherwise.

The Active Set method starts with an initial feasible point $\boldsymbol{x}^{(0)}$, which is typically chosen randomly or using some heuristics. At each iteration $k$, we solve a quadratic subproblem within the active set $S^{(k)}$, which is obtained from the KKT conditions as follows:

\begin{aligned} & \underset{\boldsymbol{x}\in\mathbb{R}^n}{\text{minimize}} & & \frac{1}{2} \boldsymbol{x}^T \boldsymbol{H}^{(k)} \boldsymbol{x} + \boldsymbol{g}^{(k)T} \boldsymbol{x} \ & \text{subject to} & & \boldsymbol{l}_i \leq x_i \leq \boldsymbol{u}_i, \quad i\in S^{(k)}, \end{aligned}

where $\boldsymbol{H}^{(k)}$ is the Hessian matrix of the objective function at the current point, and $\boldsymbol{g}^{(k)}$ is the gradient vector of the objective function at the current point. The subproblem is a quadratic programming (QP) problem with box constraints, which can be solved efficiently using standard QP solvers such as the active-set or interior-point methods. If the subproblem has a unique solution, then we update the current solution by setting $\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}+\Delta\boldsymbol{x}^{(k)}$, where $\Delta\boldsymbol{x}^{(k)}$ is the solution to the subproblem. Otherwise, we add or remove some constraints to the active set and repeat the process.

To add a constraint to the active set, we choose the constraint that violates the complementary slackness condition the most, i.e., the one with the largest positive Lagrange multiplier. To remove a constraint from the active set, we choose the one that has the smallest positive Lagrange multiplier and set its multiplier to zero. If all Lagrange multipliers are non-positive, then we stop the algorithm and declare the current solution as the optimal solution.

Convergence Properties of Active Set Method

The Active Set method has some desirable convergence properties, which we summarize below:

  • Local Convergence: If the objective function is continuous and the constraints are continuously differentiable, then the Active Set method generates a sequence of feasible points that converges to a local minimum of the objective function.
  • Superlinear Convergence: If the objective function is twice continuously differentiable and the constraints are continuously differentiable, then the Active Set method has superlinear convergence, i.e., the rate of convergence is faster than linear.
  • Global Convergence: If the objective function is convex and the constraints are convex, then the Active Set method generates a sequence of feasible points that converges to a global minimum of the objective function.

However, the Active Set method also has some limitations and challenges, which we discuss below:

  • Non-Smoothness: The Active Set method may encounter difficulties when the objective function or the constraints are non-smooth or discontinuous, as the KKT conditions may not be well-defined or may have multiple solutions.
  • Initialization: The Active Set method is sensitive to the choice of the initial feasible point, as it may converge to different local minima depending on the starting point.
  • Constraint Management: The Active Set method requires efficient management of the active set, as adding or removing constraints may increase the size of the QP subproblem and reduce the computational efficiency.

Implementation of Active Set Method

The Active Set method can be implemented using a variety of programming languages and optimization solvers, depending on the specific problem requirements and computational resources. Here, we outline a simple MATLAB implementation of the Active Set method for a sample NLP problem.javascriptCopy codefunction [x, fval, exitflag, output] = active_set(f, x0, lb, ub, options) % Active Set method for nonlinear programming with box constraints % f: objective function (function handle) % x0

: initial feasible point (column vector) % lb: lower bounds on variables (column vector) % ub: upper bounds on variables (column vector) % options: optimization options (structure)

% Default options if nargin < 5 options = optimoptions('quadprog', 'Algorithm', 'active-set'); end

% Initialize active set S = find(x0 > lb & x0 < ub); lambda = zeros(size(S));

% Loop until convergence while true % Compute objective function and gradient at current point [fval, grad] = f(x0);scssCopy code% Compute Hessian matrix at current point H = hessian(f, x0, grad); % Solve QP subproblem with active set constraints [dx, ~, exitflag] = quadprog(H, grad, [], [], [], [], lb(S), ub(S), [], options); % Update active set and Lagrange multipliers lambda(S) = max(0, lambda(S) + dx.*(dx > -lambda(S))./(ub(S) - x0(S) + (dx > 0)) - dx.*(dx > lambda(S))./(x0(S) - lb(S) + (dx < 0))); S = find(lambda > 0); % Update solution and check convergence x = x0 + dx; if norm(dx) < options.TolX || norm(lambda.*(x - lb(S)).*(ub(S) - x)) < options.TolCon    exitflag = 1; output.message = 'Optimization terminated successfully'; break; end % Check for infeasibility if isempty(S) exitflag = -2; output.message = 'No feasible solution found'; break; end % Update current point x0 = x;

end

% Pack output output.iterations = 1; output.funcCount = 2; output.algorithm = 'Active Set Method'; output.constrviolation = norm(lambda.(x - lb(S)).(ub(S) - x)); output.grad = grad; output.hessian = H; output.active_set = S; endtypescriptCopy codeIn this implementation, the input arguments are the objective function `f`, the initial feasible point `x0`, the lower bounds `lb`, the upper bounds `ub`, and the optimization options `options`. The default options use the MATLAB `quadprog` function with the active-set algorithm. The output arguments are the optimal solution `x`, the optimal objective value `fval`, the exit flag `exitflag`, and the optimization output `output`, which contains information about the optimization process, such as the number of iterations, function evaluations, and active constraints. The Active Set method is a powerful optimization algorithm for solving nonlinear programming problems with box constraints. It provides a computationally efficient and robust approach for generating feasible and optimal solutions to a wide range of engineering, economic, and scientific applications. However, the method also has some limitations and challenges, which require careful consideration and management to achieve reliable and accurate results.

Advantages and disadvantages of Active Set method:

The Active Set method has several advantages and disadvantages that are important to consider when selecting an optimization algorithm for a particular application. Some of the advantages of the Active Set method are:

  1. Efficiency: The Active Set method is computationally efficient and can handle large-scale optimization problems with many constraints. It uses an iterative approach to update the active set of constraints and solve the quadratic programming subproblems, which reduces the computational complexity and memory requirements compared to other methods.
  2. Robustness: The Active Set method is robust and can handle a wide range of nonlinear functions, nonconvex constraints, and non-smooth objectives. It is also less sensitive to the choice of initial feasible point and the accuracy of the gradient and Hessian approximations.
  3. Feasibility: The Active Set method is designed to generate feasible solutions by enforcing the box constraints and maintaining the active set of constraints. This ensures that the solution is physically meaningful and satisfies the problem specifications.
  4. Interpretable results: The Active Set method provides a clear and interpretable solution, which can be easily visualized and understood. The active set of constraints indicates which constraints are active or inactive at the optimal solution, and the Lagrange multipliers provide information about the sensitivity of the solution to changes in the constraints.

Despite its advantages, the Active Set method also has some limitations and challenges that should be taken into account:

  1. Complexity: The Active Set method can become computationally complex and time-consuming when dealing with a large number of constraints or when the constraints are highly nonlinear or nonconvex. The method requires solving a quadratic programming subproblem at each iteration, which can be expensive for large-scale problems.
  2. Convergence: The Active Set method may not converge to the optimal solution or may converge to a local minimum instead of a global minimum. The convergence behavior of the method depends on the choice of initial feasible point, the accuracy of the gradient and Hessian approximations, and the scaling of the problem variables.
  3. Sensitivity: The Active Set method can be sensitive to the choice of optimization options, such as the tolerance values, the maximum number of iterations, and the choice of subproblem solver. These options can significantly affect the convergence behavior and the quality of the solution.
  4. Implementation: The Active Set method requires careful implementation and tuning to ensure numerical stability and accuracy. The algorithm involves solving systems of linear equations and inverting matrices, which can introduce rounding errors and numerical instability.

Applications of Active Set method:

The Active Set method has been widely used in various engineering, economic, and scientific applications, including:

  1. Structural optimization: The Active Set method can be used to optimize the design of structures, such as trusses, beams, and frames, subject to geometric and material constraints. The method can optimize the shape, size, and orientation of the structure to minimize weight, stress, or deflection.
  2. Process optimization: The Active Set method can be used to optimize the operation of chemical, mechanical, and electrical processes, subject to process constraints, such as mass balance, energy balance, and equipment limitations. The method can optimize the process parameters, such as flow rates, temperatures, and pressures, to maximize efficiency or minimize cost.
  3. Portfolio optimization: The Active Set method can be used to optimize the allocation of financial assets, such as stocks, bonds, and options, subject to risk and return constraints. The method can optimize the portfolio weights and asset allocation to maximize return or minimize risk.
  4. Machine learning: The Active Set method can be used in machine learning applications, such as support vector machines and kernel methods, to optimize the hyperparameters and decision boundaries, subject to regularization and classification constraints. The method can optimize the regularization parameter and kernel function to improve the prediction accuracy and
  5. Control systems: The Active Set method can be used in control systems engineering to optimize the control parameters, such as gain, frequency, and phase, subject to stability and performance constraints. The method can optimize the control law to ensure stability and meet the desired response specifications.
  6. Robotics: The Active Set method can be used in robotics to optimize the motion planning and control of robotic systems, subject to kinematic and dynamic constraints. The method can optimize the joint angles and velocities to minimize energy consumption or maximize manipulability.
  7. Image processing: The Active Set method can be used in image processing applications, such as image segmentation and registration, to optimize the segmentation boundaries and registration parameters, subject to similarity and smoothness constraints. The method can optimize the cost function to improve the accuracy and robustness of the image processing algorithms.

Conclusion:

In conclusion, the Active Set method is a powerful optimization algorithm that can handle nonlinear and nonconvex optimization problems with box constraints. The method uses an iterative approach to update the active set of constraints and solve the quadratic programming subproblems, which reduces the computational complexity and memory requirements. The Active Set method has several advantages, such as efficiency, robustness, feasibility, and interpretable results, which make it suitable for a wide range of applications in engineering, economics, and science. However, the method also has some limitations and challenges, such as complexity, convergence, sensitivity, and implementation, which should be considered when selecting an optimization algorithm for a particular problem. Overall, the Active Set method is a valuable tool for solving optimization problems and has numerous applications in various fields.