0
$\begingroup$

Suppose we are minimizing a function $f(x_1,...,x_n)$ under the conditions $g_1(x_1,...,x_n) = g_2(x_1,...,x_n) = 0$. Under what hypotheses is a solution to the Lagrangian multiplier equations automatically a global minimum?

My guess is that $f$ must be convex and that the Lagragian must be concave and that all solutions are regular points, but I'm not sure if that's right. If someone could confirm or deny, I'd appreciate it. Thanks.

$\endgroup$
1
$\begingroup$

For a convex optimization problem, the KKT conditions are sufficient for a point to be a global minimizer. And your optimization problem is convex when $f$ is convex and $g_1$ and $g_2$ are affine.

Consider the convex optimization problem \begin{align*} \text{minimize} & \quad f(x) \\ \text{subject to} & \quad Ax = b. \end{align*} Here $f:\mathbb R^n \to \mathbb R$ is convex and differentiable. Suppose that $x^\star$ and $\lambda^\star$ together satisfy the KKT conditions: \begin{align*} Ax^\star &= b \\ \nabla f(x^\star) + A^T \lambda^\star &= 0. \end{align*} The second equation tells us that $x^\star$ is a minimizer of the function \begin{equation*} L(x,\lambda^\star) = f(x) + \langle \lambda^\star, Ax - b \rangle. \end{equation*} Now suppose that $x$ is any vector that satisfies $Ax = b$. It follows that \begin{align*} f(x) &= f(x) + \langle \lambda^\star, Ax - b \rangle \\ &\geq \inf_x \, f(x) + \langle \lambda^\star, Ax - b \rangle \\ &= f(x^\star) + \langle \lambda^\star, A x^\star - b \rangle \\ &= f(x^\star). \end{align*} Thus, $x^\star$ is a global minimizer for this convex optimization problem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.