MultiGridBarrier 0.9.0

MultiGridBarrier is a Julia module for solving nonlinear convex optimization problems in function spaces, such as p-Laplace problems. When regularity conditions are satisfied, the solvers are quasi-optimal.

The MultiGridBarrier module features finite element and spectral discretizations in 1d and 2d.

Finite elements

After installing MultiGridBarrier with the Julia package manager, in a Jupyter notebook, one solves a 1d p-Laplace problem as follows:

using MultiGridBarrier
fem1d_solve(L=5,p=1.0,verbose=false);

A 2d p-Laplace problem:

fem2d_solve(L=3,p=1.0,verbose=false);

Spectral elements

Solve a 1d p-Laplace problem using spectral methods as follows:

spectral1d_solve(n=40,p=1.0,verbose=false);

A 2d p-Laplace problem:

spectral2d_solve(n=5,p=1.5,verbose=false);

Solving $\infty$-Laplacians

For $p \geq 1$ and domain $\Omega$, the solution $u$ of the $p$-Laplace problem is the minimizer of $J(u) = \|\nabla u\|_{L^p(\Omega)}^p + \int_{\Omega} fu,$ where $u$ is in a suitable space of function satisfying, e.g. Dirichlet conditions, and $f$ is a forcing. This definition must be modified for the $\infty$-Laplace problem. Here we show how to minimize: $J(u) = \|\nabla u\|_{L^\infty(\Omega)}^p + \int_{\Omega} fu.$ We put $p=1$ for simplicity.

fem1d_solve(L=5,p=1.0,state_variables=[:u :dirichlet; :s :uniform],verbose=false);

Parabolic problems

A time-dependent problem:

parabolic_solve(h=0.1,L=3,printer=anim->anim.save("parabolic.mp4"),verbose=false);

Module reference

MultiGridBarrier.MultiGridBarrier — Module

module MultiGridBarrier

Module MultiGridBarrier solves convex optimization problems in function spaces, for example, solving p-Laplace problems. We recommend to start with the functions fem1d_solve(), fem2d_solve(), spectral1d_solve(), spectral2d_solve(). These functions are sufficient to solve p-Laplace problems in 1d or 2d, using finite or spectral elements.

For more general use, the user will need to familiarize themselves with the basic ideas of convex optimization.

Overview of convex optimization in function spaces by MultiGrid Barrier method.

The general idea is to build a multigrid hierarchy, represented by an AMG object, and barrier for a convex set, represented by a Barrier object, and then solve a convex optimization problem using the amgb() solver.

To generate the multigrid hierarchy represented by the AMG object, use either fem1d(), fem2d(), spectral1d() or spectral2d() functions. These constructors will assemble suitable AMG objects for either FEM or spectral discretizations, in 1d or 2d. One should think of these four constructors as being specialized in constructing some specific function spaces. A user can use the amg() constructor directly if custom function spaces are required, but this is more difficult.

We now describe the barrier function.

Assume that $\Omega \subset \mathbb{R}^d$ is some open set. Consider the example of the p-Laplace problem on $\Omega$. Let $f(x)$ be a "forcing" (a function) on $\Omega$, and $1 \leq p < \infty$. One wishes to solve the minimization problem

\[\begin{equation} \inf_u \int_{\Omega} fu + \|\nabla u\|_2^p \, dx. \tag{1} \end{equation}\]

Generally speaking, $u$ will range in some function space, e.g. a space of differentiable functions satisfying homogeneous Dirichlet conditions. Under some conditions, minimizing (1) is equivalent to solving the p-Laplace PDE:

\[\nabla \cdot (\|\nabla u\|_2^{p-2}\nabla u) = {1 \over p} f.\]

We introduce the "slack function" $s(x)$ and replace (1) with the following equivalent problem:

\[\begin{equation} \inf_{s(x) \geq \|\nabla u(x)\|_2^p} \int_{\Omega} fu + s \, dx. \tag{2} \end{equation}\]

Define the convex set $\mathcal{Q} = \{ (u(x),q(x),s(x)) \; : \; s(x) \geq \|q(x)\|_2^p \}$, and

\[z = \begin{bmatrix} u \\ s \end{bmatrix}, \qquad c^T = [f,0,1], \qquad Dz = \begin{bmatrix} u \\ \nabla u \\ s \end{bmatrix}.\]

Then, (2) can be rewritten as

\[\begin{equation} \inf_{Dz \in \mathcal{Q}} \int_{\Omega} c^T(x)Dz(x) \, dx. \tag{3} \end{equation}\]

Recall that a barrier for $\mathcal{Q}$ is a convex function $\mathcal{F}$ on $\mathcal{Q}$ such that $\mathcal{F} < \infty$ in the interior of $\mathcal{Q}$ and $\mathcal{F} = \infty$ on the boundary of $\mathcal{Q}$. A barrier for the p-Laplace problem is:

\[\mathcal{F}(u,q,s) = \int_{\Omega} -\log(s^{2 \over p} - \|q\|_2^2) - 2\log s \, dx = \int_{\Omega} F(Dz(x)) \, dx.\]

The central path $z^*(t)$ minimizes, for each fixed $t>0$, the quantity

\[\int_{\Omega} tc^TDz + F(Dz) \, dx.\]

As $t \to \infty$, $z^*(t)$ forms a minimizing sequence (or filter) for (3). We think of the function $c(x)$ as the "functional" that we seek to minimize.

The Convex{T} type describes various convex sets (denoted $Q$ above) by way of functions barrier(), cobarrier() and slack(). barrier is indeed a barrier for $Q$, cobarrier() is a barrier for a related feasibility problems, and slack() is used in solving the feasibility problem. Convex{T} objects can be created using the various convex_...() constructors, e.g. convex_Euclidian_power() for the p-Laplace problem.

Once one has AMG and Convex objects, and a suitable "functional" c, one uses the amgb() function to solve the optimization problem by the MultiGrid Barrier method, a variant of the barrier method (or interior point method) that is quasi-optimal for sufficiently regular problems.

`dim`	1	2
`f`	`(x)->T[0.5,0.0,1.0]`	`(x)->T[0.5,0.0,0.0,1.0]`
`g`	`(x)->T[x[1],2]`	`(x)->T[x[1]^2+x[2]^2,100.0]`
`D`	`[:u :id`	`[:u :id`
	`:u :dx`	`:u :dx`
	`:s :id]`	`:u :dy`
		`:s :id]`