The motivating problem is the familiar
$$\begin{align} \text{maximize} \quad & F(x_1, \cdots,x_n) \\ \text{subject to} \quad & G_i(x_1, \cdots,x_n) = c_i,\quad i=\{1, \cdots,m\} \end{align}$$
$F: \mathbb{R}^n\to \mathbb{R}$ is maximized (or minimized) subject to the $m$ constraints $G_i: \mathbb{R}^n\to \mathbb{R} = c_i$.
For $n=2$ and $n=3$ where there is only $m=1$ constraint, the authors of this online textbook have a nice way of performing the method of Lagrange multipliers that "automatically" eliminates the value of the Lagrange multiplier itself. The general idea is to find $x_1,\cdots, x_n$ such that $\nabla F(\vec x)$ and $\nabla G(\vec x)$ are parallel, then apply the constraint $G(x_1,\cdots, x_n) = c$ to these $x_j$.
When $n=2$ and $m=1$, they assert that the determinant of the $2\times 2$ matrix whose columns are $\nabla F$ and $\nabla G$ is zero:
$$\det \begin{bmatrix} \frac{\partial F}{\partial x_1} & \frac{\partial G}{\partial x_1}\\ \frac{\partial F}{\partial x_2} & \frac{\partial G}{\partial x_2}\\ \end{bmatrix} = \det \begin{matrix}\Biggl[ \nabla F(\vec x) & \nabla G(\vec x)\Biggr]\end{matrix} = 0 \tag{1}\label{eq1}$$
This determinant and $G(\vec x) = 0$ amount to two equations in two unknowns, and solving for $x_1$ and $x_2$ is straightforward.
When $n=3$ and $m=1$, they assert that the cross product is zero:
$$\nabla F(\vec x) \times \nabla G(\vec x) = \vec 0 \tag{2}\label{eq2}$$
This system lets us eliminate one of the $x_j$, and again we have two equations in two unknowns when we apply $G(\vec x) =0$.
I would like to generalize this approach to problems with additional constraints and/or in higher dimensions.
For $n=2$ and arbitrary $m$, we can set $m$ determinants equal to zero:
$$\det \begin{matrix}\Biggl[ \nabla F(\vec x) & \nabla G_i(\vec x)\Biggr]\end{matrix} = 0, \quad i=\{1, \cdots,m\} \tag{3}\label{eq3}$$
For $n=3$ and arbitrary $m$, we can set $m$ cross products equal to zero:
$$\nabla F(\vec x) \times \nabla G_i(\vec x) = \vec 0, \quad i=\{1, \cdots,m\} \tag{4}\label{eq4}$$
The challenge comes with larger values of $n$. I notice that matrix in $\eqref{eq1}$ is square whenever $m = n-1$. Can I use the same "determinant trick" in any such case? That is, are these conditions sufficient for finding critical points?
$$\det \begin{bmatrix} \vert&\vert&&\vert\\ \nabla F(\vec x) & \nabla G_1(\vec x) & \cdots & \nabla G_{n-1}(\vec x)\\ \vert&\vert&&\vert\\ \end{bmatrix} = 0 \\ \text{and} \\ G_i(x_1, \cdots,x_n) = c_i,\quad c=\{1, \cdots,n-1\} \tag{5}\label{eq5}$$
My intuition says no, because the matrix on the left will be singular if just one of the $\nabla G_i$ is parallel to $\nabla F$, or if one of the $\nabla G_i$ is a linear combination of the others.
- Is my intuition correct, that the determinant in $\eqref{eq5}$ ensures optimality only for $n=2, m=1$?
I notice that in going from $\eqref{eq1}$ to $\eqref{eq2}$ (and $\eqref{eq3}$ to $\eqref{eq4}$), switching from a determinant to a cross product turns the right hand side from a scalar $0$ to a vector $\vec 0$ in $\mathbb{R}^n$.
- Is there a generalization of the cross product that I can use to test whether two vectors $\vec a, \vec b \in R^n$ of any size $n$ are parallel?
- As in $\eqref{eq1}$ and $\eqref{eq2}$, is there a way to write the first-order optimality conditions for Lagrange optimization without including the $\lambda_i$ variables for arbitrary $n$ and $m$?
Edit: Reading further in this section, the same authors also apply the determinant trick to the $n=3,m=2$ case. Where $G(\vec x) = H(\vec x) = 0$ are constraints (which, taken together, describe a curve in $\mathbb{R}^3$), the condition is
$$\det \begin{matrix}\Biggl[ \nabla F(\vec x) & \nabla G(\vec x) & \nabla H(\vec x)\Biggr]\end{matrix} = 0$$
from which we eliminate one of the three variables and solve for the other two using $G(\vec x) = 0$ and $H(\vec x) = 0$.
I think this rests on the unstated assumption that $\nabla G(\vec x) \times \nabla H(\vec x) \neq \vec 0$. Indeed, if $\nabla G(\vec x) \times \nabla H(\vec x)$ is zero, then either those two surfaces are the same, and the constraints are redundant, or $G(\vec x) $ and $H(\vec x)$ are separated by a constant, and the problem is infeasible.
But have the authors addressed the possibility that $\nabla H$ is some other linear combination of $\nabla F$ and $\nabla G$? Then the matrix would be singular for all $\vec x$.