rezarezvan.com
Toggle menu
Blog Lecture Notes Research Thoughts

Part 13 - Feasible Descent Methods

TMA947 Date: October 8, 2025 9 min read

Introduction

In this part we will cover feasible descent methods for constrained optimization problems. More specifically, we will cover the general framework for feasible descent methods in a constrained setting. Further, we will cover three specific algorithms that fall under this framework, the Frank-Wolfe method, the Simplicial Decomposition method, and the Gradient Projection method.

Feasible Descent Methods

Explanation (Problem Setting)

Consider the constrained optimization problem,

min⁡ f(x)subject to x∈S\begin{align*} \min \ & f(\mathbf{x}) \newline \text{subject to} \ & \mathbf{x} \in S \newline \end{align*}

where SS is a non-empty, closed, and convex set. Further, let f∈C1f \in C^1 on S.

Recall (Optimality Condition for Constrained Problems)

All algorithms are essentially based on optimality conditions, since we need some signal to go by and these conditions also provide ideas on how we can formulate our algorithms.

Therefore, we recall the optimality condition for constrained problems.

Theorem 1 (Stationary Points in Constrained Problems)

Let ff and SS be defined as above. Then,

x⋆ is a local minimum   ⟹  ∇f(x⋆)T(x−x⋆)≥0, ∀x∈S\mathbf{x}^{\star} \text{ is a local minimum } \implies \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) \geq 0, \ \forall \mathbf{x} \in S

Furthermore, recall the more generalized theorem about stationary points in constrained problems.

Theorem 2 (Equivalent Statements of Stationary Points in Constrained Problems)

Let ff and SS be defined as above. Then, the following statements are equivalent,

{∇f(x⋆)T(x−x⋆)≥0, ∀x∈S−∇f(x⋆)∈NS(x⋆)≔{p∈Rn∣pT(x−x⋆)≤0, ∀x∈S}min⁡x∈S∇f(x⋆)T(x−x⋆)=0x⋆=projS(x⋆−∇f(x⋆)).\begin{cases} \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) \geq 0, \ \forall \mathbf{x} \in S \newline -\nabla f(\mathbf{x}^{\star}) \in N_S(\mathbf{x}^{\star}) \coloneqq \{\mathbf{p} \in \mathbb{R}^n \mid \mathbf{p}^T (\mathbf{x} - \mathbf{x}^{\star}) \leq 0, \ \forall \mathbf{x} \in S \} \newline \min_{\mathbf{x} \in S} \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) = 0 \newline \mathbf{x}^{\star} = \mathrm{proj}_S(\mathbf{x}^{\star} - \nabla f(\mathbf{x}^{\star})). \newline \end{cases}

where projS≔arg⁡min⁡y∈S ∥y−x∥\mathrm{proj}_S \coloneqq \underset{\mathbf{y} \in S}{\arg\min} \ \Vert \mathbf{y} - \mathbf{x} \Vert, i.e., we choose the point in SS that is closest to x\mathbf{x}.

Intuition (General Feasible Descent Method)

With these, we can now formulate a general feasible descent method.

Algorithm (General Feasible Descent Method)

Step 0: Initialize x0∈S\mathbf{x}_0 \in S, k=0k = 0 1How do we choose a (good) starting point? Use any a priori knowledge about the problem, or try to use some heuristic to find a feasible point!

Step 1: Find a direction pk\mathbf{p}_k such that there exists an αˉ>0\bar{\alpha} > 0, such that 2In the second condition, we do not include α=0\alpha = 0 since we want a strict decrease in the objective function, otherwise it would be possible to take α=0\alpha = 0 and not move at all!

{xk+αpk∈S, ∀α∈[0,αˉ]f(xk+αpk)<f(xk), ∀α∈(0,αˉ]\begin{cases} \mathbf{x}_k + \alpha \mathbf{p}_k \in S, \ \forall \alpha \in [0, \bar{\alpha}] \newline f(\mathbf{x}_k + \alpha \mathbf{p}_k) < f(\mathbf{x}_k), \ \forall \alpha \in (0, \bar{\alpha}] \newline \end{cases}

Step 2: Determine a step length αk\alpha_k such that,

{xk+αkpk∈Sf(xk+αkpk)<f(xk)\begin{cases} \mathbf{x}_k + \alpha_k \mathbf{p}_k \in S \newline f(\mathbf{x}_k + \alpha_k \mathbf{p}_k) < f(\mathbf{x}_k) \newline \end{cases}

Step 3: Update our current iterate,

xk+1=xk+αkpk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k

Step 4: If termination criteria is fulfilled, STOP; Else, go to (1) with k←k+1k \leftarrow k + 1.

Note (Remarks on the General Feasible Descent Method)

As we can see, this is quite similar to the unconstrained setting! One key difference is that, search directions are often computed as pk=yk−xk\mathbf{p}_k = \mathbf{y}_k - \mathbf{x}_k, where yk\mathbf{y}_k solves some other optimization problem (we will see examples of this later).

Further, line search is also similar to the unconstrained setting, but, in this setting, we need to ensure that the new iterate stays feasible. However, finding feasible descent directions can be difficult for some sets SS.

Frank-Wolfe Method

Intuition (Frank-Wolfe Method)

Let SS be a polyhedron, from the third optimality condition, i.e.,

x⋆ is a local minimum   ⟹  min⁡x∈S∇f(x⋆)T(x−x⋆)=0\mathbf{x}^{\star} \text{ is a local minimum } \implies \min_{\mathbf{x} \in S} \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) = 0

thus, conversely 3Why <0< 0? We know that the trivial minimizer is x=xk\mathbf{x} = \mathbf{x}_k, which gives 00. Thus, if the minimum is less than 00, it means that there exists some x∈S\mathbf{x} \in S that decreases the objective function, i.e., xk\mathbf{x}_k is not a local minimum!,

min⁡x∈S∇f(xk)T(x−xk)<0  ⟹  xk is not a local minimum\min_{\mathbf{x} \in S} \nabla f(\mathbf{x}_k)^T (\mathbf{x} - \mathbf{x}_k) < 0 \implies \mathbf{x}_k \text{ is not a local minimum}

This gives us an idea how to find feasible descent directions, by solving the linear optimization problem.

At xk∈S\mathbf{x}_k \in S, if min⁡x∈S∇f(xk)T(x−xk)<0\min_{\mathbf{x} \in S} \nabla f(\mathbf{x}_k)^T (\mathbf{x} - \mathbf{x}_k) < 0, find,

yk∈arg⁡min⁡x∈S ∇f(xk)T(x−xk)\mathbf{y}_k \in \underset{\mathbf{x} \in S}{\arg\min} \ \nabla f(\mathbf{x}_k)^T (\mathbf{x} - \mathbf{x}_k)

and set pk=yk−xk\mathbf{p}_k = \mathbf{y}_k - \mathbf{x}_k. Then, pk\mathbf{p}_k is a feasible descent direction.

Note

The yk\mathbf{y}_k problem is an LP, i.e., the cost is linear in x\mathbf{x} and the constraints are linear inequalities (since SS is a polyhedron). Thus, if one uses the simplex method, yk\mathbf{y}_k will always be an extreme point of SS. Which means the direction pk\mathbf{p}_k always points towards an extreme point of SS.

Algorithm (Frank-Wolfe Method)

Step 0: Initialize x0∈S\mathbf{x}_0 \in S, k=0k = 0

Step 1: Find,

yk∈arg⁡min⁡x∈S ∇f(xk)T(x−xk)\mathbf{y}_k \in \underset{\mathbf{x} \in S}{\arg\min} \ \nabla f(\mathbf{x}_k)^T (\mathbf{x} - \mathbf{x}_k)

and set pk=yk−xk\mathbf{p}_k = \mathbf{y}_k - \mathbf{x}_k.

Step 2: Compute step length αk∈[0,1]\alpha_k \in [0, 1] 4Why is it bounded in between 0 and 1? Since yk∈S\mathbf{y}_k \in S and SS is convex, any convex combination of xk\mathbf{x}_k and yk\mathbf{y}_k is also in SS, i.e., xk+αk(yk−xk)=(1−αk)xk+αkyk∈S\mathbf{x}_k + \alpha_k (\mathbf{y}_k - \mathbf{x}_k) = (1 - \alpha_k) \mathbf{x}_k + \alpha_k \mathbf{y}_k \in S. using, e.g., Armijo step length rule.

Step 3: Update,

xk+1=xk+αkpk=(1−αk)xk+αkyk\begin{align*} \mathbf{x}_{k+1} & = \mathbf{x}_k + \alpha_k \mathbf{p}_k \newline & = (1 - \alpha_k) \mathbf{x}_k + \alpha_k \mathbf{y}_k \newline \end{align*}

Step 4: If ∇f(xk)T(yk−xk)\nabla f(\mathbf{x}_k)^T (\mathbf{y}_k - \mathbf{x}_k) is close to zero or αk\alpha_k is close to zero, STOP; Else, go to (1) with k←k+1k \leftarrow k + 1.

Theorem 3 (Convergence of Frank-Wolfe Method)

Let SS be a non-empty and bounded polyhedron. Further, let f∈C1f \in C^1 on SS.

If the Armijo step length rule is used, then the sequence {xk}\{\mathbf{x}_k\} generated by the Frank-Wolfe method has bounded limit points and all limit points are stationary points of the problem.

Simplicial Decomposition Method

Intuition (Simplicial Decomposition Method)

As we have seen, the Frank-Wolfe method finds the next iterate between our current iterate and an extreme point of SS.

The Simplicial Decomposition method is similar, but instead of only considering the current iterate and one extreme point, we consider the convex hull of multiple extreme points. Thus, we can find the next iterate in a larger set, which can potentially give us a better descent direction. Further, we can also remove extreme points that are not useful anymore.

Algorithm ((Easy Version) Simplicial Decomposition Method)

Step 0: Initialize x0∈S\mathbf{x}_0 \in S, k=0k = 0.

Step 1: Find,

yk∈arg⁡min⁡x∈S ∇f(xk)T(x−xk)\mathbf{y}_k \in \underset{\mathbf{x} \in S}{\arg\min} \ \nabla f(\mathbf{x}_k)^T (\mathbf{x} - \mathbf{x}_k)

Step 2: Find,

(μk,vk)∈arg⁡min⁡ f(μxk+∑i=1kviyi)subject to μ+∑i=1kvi=1μ,vi≥0,\begin{align*} (\mu_k, \mathbf{v}_k) \in & \arg\min \ f(\mu \mathbf{x}_k + \sum_{i=1}^{k} v_i \mathbf{y}_i) \newline \text{subject to} \ & \mu + \sum_{i=1}^{k} v_i = 1 \newline & \mu, v_i \geq 0, \end{align*}

Step 3: Update,

xk+1=μkxk+∑i=1kvk(i)yi\mathbf{x}_{k+1} = \mu_k \mathbf{x}_k + \sum_{i=1}^{k} v^{(i)}_k \mathbf{y}_i
Note (Remarks on the Simplicial Decomposition Method)

The Simplicial Decomposition method is better, in the sense of convergence, than the Frank-Wolfe method, since it considers a larger set to find the next iterate. However, it can be difficult to solve for (μk,vk)(\mu_k, \mathbf{v}_k), since the number of variables increases with kk.

Gradient Projection Method

Intuition (Gradient Projection Method)

The Gradient Projection method is based on the fourth optimality condition, i.e.,

x⋆ is a local minimum   ⟹  x⋆=projS(x⋆−∇f(x⋆))x⋆=projS(x⋆−α∇f(x⋆))\begin{align*} \mathbf{x}^{\star} \text{ is a local minimum } & \implies \mathbf{x}^{\star} = \mathrm{proj}_S(\mathbf{x}^{\star} - \nabla f(\mathbf{x}^{\star})) \newline \mathbf{x}^{\star} = \mathrm{proj}_S(\mathbf{x}^{\star} - \alpha \nabla f(\mathbf{x}^{\star})) \end{align*}

Thus, conversely,

p≔projS(xk−α∇f(xk))−xk≠0  ⟹  xk is not a local minimum\mathbf{p} \coloneqq \mathrm{proj}_S(\mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)) - \mathbf{x}_k \neq 0 \implies \mathbf{x}_k \text{ is not a local minimum}

This gives us a way to find feasible descent directions, by projecting the gradient step onto the feasible set.

Algorithm (Gradient Projection Method)

Step 0: Initialize x0∈S\mathbf{x}_0 \in S, k=0k = 0

Step 1: Try to update,

xk+1=projS(xk−αk∇f(xk))\mathbf{x}_{k+1} = \mathrm{proj}_S(\mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k))

where αk\alpha_k is selected by the Armijo step length rule, i.e.,

f(projS(xk−αk∇f(xk)))<f(xk)−μαk∇f(xk)Tpkf(\mathrm{proj}_S(\mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k))) < f(\mathbf{x}_k) - \mu \alpha_k \nabla f(\mathbf{x}_k)^T \mathbf{p}_k

where pk=projS(xk−αk∇f(xk))−xk\mathbf{p}_k = \mathrm{proj}_S(\mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)) - \mathbf{x}_k.

Step 2: If pk\mathbf{p}_k is close to zero or αk\alpha_k is close to zero, STOP; Else, go to (1) with k←k+1k \leftarrow k + 1.

Note (Remarks on the Gradient Projection Method)

To compute projX(x)\mathrm{proj}_X(\mathbf{x}), we must solve,

min⁡y∈S ∥y−x∥\underset{\mathbf{y} \in S}{\min} \ \Vert \mathbf{y} - \mathbf{x} \Vert

The solution always exists for a non-empty, closed, and convex set SS, but is not necessarily easy to compute.

However, projection can be (relatively) easy in some cases. Consider,

X={x∈Rn∣x≥0}X = \{\mathbf{x} \in \mathbb{R}^n \mid \mathbf{x} \geq 0\}

then,

projX(x)=[max⁡{0,xi}]i=1n=[(xi)+]i=1n\begin{align*} \mathrm{proj}_X(\mathbf{x}) & = \left[\max\{0, x_i\}\right]_{i=1}^n \newline & = \left[(x_i)_+\right]_{i=1}^n \newline \end{align*}

where (⋅)+(\cdot)_+ is the positive part function, i.e., (s)+=max⁡{0,s}(s)_+ = \max\{0, s\}

Further, consider,

X={x∈Rn∣∑i=1nxi=1, xi≥0}X = \{\mathbf{x} \in \mathbb{R}^n \mid \sum_{i=1}^n x_i = 1, \ x_i \geq 0 \}

then,

projX(x)=[(xi−λ)+]i=1n\mathrm{proj}_X(\mathbf{x}) = \left[(x_i - \lambda)_+\right]_{i=1}^n

where λ\lambda is chosen such that,

∑i=1n(xi−λ)+=1\sum_{i=1}^n (x_i - \lambda)_+ = 1
Theorem 4 (Convergence of Gradient Projection Method)

Let SS be a non-empty, closed, and convex set and f∈C1f \in C^1 on SS.

If the Armijo step length rule is used, then the sequence {xk}\{\mathbf{x}_k\} generated by the Gradient Projection method has bounded limit points and all limit points are stationary points of the problem.