# How to solve nonlinear optimization with constraints that have singular jacobian

I'm solving a nonlinear constrained optimization with constraint of following form:

$$\mathbf{A}^T\mathbf{A}-\mathbf{I}=\mathbf{0}, \mathbf{B}^T\mathbf{B}-\mathbf{I}=\mathbf{0}$$

where $\mathbf{A}$ and $\mathbf{B}$ are matrices that I'm solving for. Usually the initial guess of $\mathbf{A}$ and $\mathbf{B}$ are diagonal matrices with entries of 1 or -1.

I flatted the entries of $\mathbf{A}$ and $\mathbf{B}$ in column order into a vector as the variable $\mathbf{x}$ to solve for. I tried NLopt and Opt++ to solve my problem, both of them failed. While debugging I found that the gradient of constraint is a singular matrix. $\mathbf{A}$ and $\mathbf{B}$ are not necessarilly square matrices, thus neither is gradient of constraint.

My question is: is there any algorithm to solve this nonlinear constrained optimization, which does not require gradient of the constraint?

=======Edit=========

The objective function is:

$$\textrm{off}(\mathbf{A^T\Lambda_XA})+\textrm{off}(\mathbf{B^T\Lambda_YB})+\mu\left\|\mathbf{F^T\Phi{}A}-\mathbf{G^T\Psi{}B}\right\|_{\mathbf{F}}^2$$

where off() means sum of the squared off-diagonal elements, $\Lambda_X$ and $\Lambda_Y$ are diagonal matrices, $\mathbf{F}$ and $\mathbf{G}$, $\mathbf{\Phi}$ and $\mathbf{\Psi}$ are all known matrices.

• Can you say what your objective function is? I assume that $A,B$ are matrices with more rows than columns, right? Jan 24, 2014 at 14:31
• Yes, $\mathbf{A}$ and $\mathbf{B}$ are matrices with more rows than columns.@WolfgangBangerth , I've updated the question with objective function. Jan 24, 2014 at 15:02
• Aw, so your objective function is quartic in the entries of the matrices you are seeking? Jan 25, 2014 at 2:15
• Yes,@WolfgangBangerth. The problem now seems to be that the gradient of constraints is singular matrix. I know little about optimization algorithms, usually I use solvers provided by open-source packages. I wonder is there any algorithm that could solve this problem. Jan 25, 2014 at 4:55
• Ah, redundant constraints. Yes, that would violate the constraint qualification and make things difficult for implementations. Jan 26, 2014 at 19:58