How is the physical Lagrangian related to the constrained minimization Lagrangian? If we're minimizing an energy $V(q)$ subject to constraints $C(q) = 0$, the Lagrangian is
$$L = V(q) + \lambda C(q).$$
I have fairly solid intuition for this Lagrangian, namely that the energy gradient is normal to the constraint manifold iff we can annihilate the energy gradient using constraint derivative terms.  In contrast, I have extremely poor intuition for the Lagrangian in the Lagrangian formulation of dynamics:
$$L = T(q) - V(q),$$
where $T(q)$ is kinetic energy.
How are the two Lagrangians related?  In particular, can my intuition for the constrained minimization case be converted into intuition for the physical case?
 A: The difference is the role of time $t$, not the role of constraints$^1$ :


*

*With no time. Here one has an energy/potential function $S(q)$, where $q^i$ denote all variables (original variables, Lagrange multipliers, etc.). The stationary solutions obey
$$\frac{\partial S}{\partial q}~=~0.$$
There are no dynamics or kinematics.

*With time $t$. Here one has an action functional 
$$S[q]=\int \!dt~ L(q,\dot{q},t),$$
where $q^i(t)$ denote all variables (original variables, Lagrange multipliers, etc.). The stationary solutions obey Euler-Lagrange (EL) equations. Some of the EL eqs. may be dynamical, i.e. contain time derivatives. Typically, the Lagrangian $L$ would now contain kinetic energy terms.
--
$^1$ To keep the discussion simple, we will ignore field theoretic models. 
A: I'd like to add a bit of mathiness to what Qmechanic says.  In the first constrained optimization problem with $L(q) = V(q) + \lambda C(q)$, you are attempting to determine the minimum value attained by the function $L$ which is presumably a function on some subset of Euclidean space $\mathbb R^n$ (or perhaps a function on some neighborhood of a real, smooth manifold which pretty much amounts to the same thing).  So you want to determine the point $q = (q^1, \dots, q^n)$, where each $q^i$ is a real number, at which the function $L$ attains a minimum value.
In the case of physical Lagrangians, it is true that the Lagrangian is still the same type of function (a function on "configuration space" in this case which is locally just $\mathbb R^{2n}$), but we don't really care to determine a point in configuration space at which the Lagrangian attains a minimum value.  Instead, we consider parameterized paths $q(t)$ on configuration space and attempt to determine which paths minimize (actually we only really care to find critical paths which are not necessarily maxima or minima) the action functional $S[q]$ which is a function that takes a path on configuration space, and returns a real number.  As Qmechanic writes, the action functional that we use in classical mechanics is defined as
$$
  S[q] = \int dt\, L(q(t), \dot q(t), t)
$$
Note that the symbol $q$ which we are here using to label the argument of the action functional $S$ denotes a path as opposed to a point in configuration space (it's a rather common abuse of notation in physics to use $q$ to denote both points in configuration space and paths).  Notice that the Lagrangian is, in this case, simply an intermediate function with which we write the action functional.  In particular, we don't so much care to minimize the Lagrangian itself.
Cheers!
