1
$\begingroup$

Short version. How to choose the initial values for the Lagrange multipliers in the Lagrange-Newton equality-constraint minimization method?

Introduction. The problem to solve is

\begin{equation} \min_{\mathbf x \in \mathbb R^n} f(\mathbf x) \quad \text{subject to} \quad h(\mathbf x) = \mathbf 0, \end{equation}

where $f: \mathbb R^n \to \mathbb R$ and $h: \mathbb R^n \to \mathbb R^m$ are twice continuously differentiable functions.

I implemented the local Lagrange-Newton method, which aims at finding a solution $(\mathbf x, \pmb \mu) \in \mathbb{R}^{n+m}$ of the KKT equations

\begin{align} \nabla f(\mathbf x) + \nabla h(\mathbf x)\pmb \mu &= \mathbf 0,\\ h(\mathbf x)&= \mathbf 0, \end{align}

where $\nabla h(\mathbf x) = (\nabla h_1(\mathbf x), \ldots, \nabla h_m(\mathbf x)) \in \mathbb{R}^{n \times m}$ is the Jacobi matrix of $h$ and $\pmb \mu \in \mathbb{R}^m$ is the vector of Lagrange multipliers.

I need initial values $\mathbf x_0$ and $\pmb \mu_0$ in order to use Newton's method to iteratively solve the KKT equations. Based on my application, I have a reasonable value for $\mathbf x_0$.

Question 1 What are good general strategies for selecting $\pmb \mu_0$?

Question 2 How about using $\mathbf x_0$ to compute $\pmb \mu_0$ as the least-squares solution of the first KKT equation: \begin{equation} \pmb \mu_0 = \text{arg}\min_{\pmb \mu \in \mathbb{R}^m} \|\nabla f(\mathbf x_0) + \nabla h(\mathbf x_0)\pmb \mu\|^2. \end{equation}

For some values for $\mathbf x_0$, the least-squares solution $\pmb \mu_0$ makes the method to diverge, whereas setting $\pmb \mu_0$ to a random vector in $[-1, 1]^m$ leads to convergence to the right solution. Any thoughts on that?

Question 3 Is it beneficial to have $\mathbf x_0$ to fulfill the constraints? Or is the distance to the solution $(\mathbf x, \pmb \mu)$ more important?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.