Optimization for constrained problem

Question

I'm reading about Lagrange multipliers from a Pattern recognition book appendix and on one point the following is stated:

---

$\begin{align} &\color{gray}{\verb+C.4+}\,\,\,\,\,\color{#08F}{\textbf{Optimization for Constrained Problems}}\\ &\color{gray}{\verb+C.4.1+}\,\,\,\,\,\text{Equality Constraints} \end{align}$

We will first focus on linear equality constraints and then generalize to the nonlinear case. Although the philosophy for both cases is the same, it is easier to grasp the basics when linear constraints are involved . Thus the problem is cast as $$\text{minimize}\,\,\,\, J(\theta)\\\text{subject to}\,\,\,\,A\theta=b$$ where $A$ is an $m\times l$ matrix and $b$, $\theta$ are $m\times1$ and $l\times 1$ vectors, respectively. It is assumed that the cost function $J(\theta)$ is twice continuously differentiable and it is, in general, a nonlinear function. Furthermore, we assume that the rows of $a$ are linearly independent, hence $A$ has full row rank. This assumption is known as the regularity assumption.

Let $\theta_*$ be a local minimizer of $J(\theta)$ over the set $\{\theta:\,A\theta=b\}$. Then it is not difficult to show (e.g.,[Nash 96]) that, at this points, the gradient of $J(\theta)$ is given by $$\color{red}{\boxed{\color{black}{\displaystyle \frac{\partial}{\partial\theta}(J(\theta))|_{\theta=\theta_*}=A^T\lambda}}} \tag{C.24}$$ where $\displaystyle \lambda\equiv[\lambda_1,\cdots,\lambda_m]^T$. Taking into account that $$\color{red}{\boxed{\color{black}{\displaystyle \frac{\partial}{\partial\theta}(A\theta)=A^T}}} \tag{C.25}$$ Eq. $\text{(C.24)}$ states that, at a constrained minimum , the gradient of the cost function is a linear combination of the gradients of the constraints. This is quite natural.

---

Could perhaps someone show me easy-to-read proof of why the points in the red rectangles are true, since it's not difficult to show as the text suggests ;)

Thank you for any help :)

Answer 1

I believe the author begins with the Lagrange multiplier formulation

$$J(\theta)-\lambda(A\theta-b)$$

of the constrainted optimization problem. Then he computes the gradient w.r.t the components $\theta_i$ of $\theta$ at the local minimizer, arriving at the expression (in compact form)

$$\nabla J(\theta)-\lambda\nabla(A\theta)=\nabla J(\theta)-\lambda A^t=0,$$

where we used the second relation in the red box.

Both relations in the boxes are checked using components, and writing the scalar product

$$\lambda A\theta :=\langle \lambda, A\theta\rangle$$

explicitly.

Answer 2

The second point can be shown as

$$ \frac{\partial}{\partial \theta}_i (A\theta)_j = \frac{\partial}{\partial \theta}_i (\sum_kA_{jk}\theta_k) = (A)_{ji} $$

Thus,

$$ \frac{\partial}{\partial \theta} (A\theta) = A^T $$

Note that we are taking the gradient, not the derivative $D$ (which is the gradient transposed, technically).

The first part can be shown my setting the gradient of the relaxed, unconstrained objective (the Lagrangian) $$J(\theta) + \lambda^T(b - A\theta)$$

equal to zero.