Convex Optimization

Part 1: Warm-up, minimization problem and gradient descent

The first part is about using the Gradient descent method to solve a minimization problem

We find the optimal step (leading to the fewest iterations) for which the method converges

When the step size is too small the algorithm needs more iterations to converge. When it is too large the algorithm does not converge

The error compared to numpy linalg solve decreases as the number of iteration increases. It increases as the dimension of the problem increases.

Part 2: Penalization

In this part we explore two penalization methods. We consider a path between an origin and an endpoint and we try to find the shortest path according to constraints

Let $\gamma$ be the path (collection of points in a square of length 1), $\mathcal{H}(\gamma) = \frac{1}{2} \int_{0}^{1} [x'(t)^2 y'(t)^2]dt$ be the function to minimize, $D = {(x,y) \in \mathbb{R}^{2}, (x-a)^{2} (y-b)^{2} < r^{2}}$ the constraint.

We define penalization functions such that we avoid the obstacle(s). We discretize every function and implement them.

External penalization

The penalization function is $\mathcal{R}(\gamma) = \frac{1}{2} \int_{0}^{1} max(0,r^{2} -(x-a)^{2} - (y-b)^{2})^2 dt$

The goal is to minimize $\mathcal{H}_{\epsilon} = \mathcal{H}(\gamma) \frac{1}{\epsilon}\mathcal{R}(\gamma)$

As $\epsilon$ becomes smaller, the penalization becomes larger and the constraint is respected.

Internal penalization

The penalization function is $\mathcal{L}(\gamma) = \frac{1}{2}\int_{0}^{1} log(r^{2} -(x-a)^{2} - (y-b)^{2}) dt$

The goal is to minimize $\mathcal{G}_{\alpha} = \mathcal{H}(\gamma) - \alpha\mathcal{L}(\gamma)$

The algorithm goes through the obstacle until $\alpha$ is large enough.

Comparison

There seems to be a threshold phenomenon with the second penalization method where it will pass through the obstacle until penalization parameter is large enough to respect the constraint

The first penalization method is an external penalization method because the minimiser of $\mathcal{R}$ does not necessarily verify the constraints, only in an approximate manner. And the penalization fonction is 0 only in the admissible set of points. Whereas, the second method is an internal penalization method. The minimizer of $\mathcal{L}$ verifies the constraints and the penalization works when we approach the constraints, not just when we violate it.

Developments

We observe the behavior when we add obstacles