Solve equations by solving convex optimization

Question

I have the following equations to solve simultaneously ($y$ is the vector to be solved) \begin{cases} (A^\top A+\lambda D)y=A^\top b \\ y_1^2=y_2^2+y_3^2+y_4^2 \\ y_1 \geq 0, \end{cases} where $(A^\top A+\lambda D) \in \mathbb{R}^{4 \times 4}$ is singular whose rank may be $1$, $2$ or $3$, and $y=[y_1~y_2~y_3~y_4]^\top$ is to be solved.

Suppose that the equations alwayse have a solution. Since $(A^\top A+\lambda D)$ is singular, there may be infinite solutions.

I wonder if I can convert the problem into a convex optimization, and by solving the corresponding convex optimiation we can obtain the unique solution. Or anyone can offer an efficient method to obtain a unique solution.

Thanks for your insightful comments.

Answer 1

You have to use the bordered system to solve for $y$. Since $A^TA+\lambda D$ is singular, $0$ is an eigenvalue; namely, there a nonzero eigenvector $q$ such that $$ (A^TA+\lambda D)q=0. $$ Similarly $(A^TA+\lambda D)^T=A^TA+\lambda D^T$ has an eigenvalue $0$; amely, there a nonzero eigenvector $p$ such that $$ (A^TA+\lambda D^T)p=0 $$ or $$ p^T(A^TA+\lambda D)=0. $$ So the solvablity of the singularity is $$ p^TA^Tb=0 $$ under which, the bordered system $$ \bigg[\begin{matrix}A^TA+\lambda D&q\\p^T&0\end{matrix}\bigg]\binom{w}{u}=\binom{A^tb}{0} $$ has a unique solution.

Answer 2

The other answer is great if you just want some unique solution to just the linear equation. Still, convex optimisation would provide an attractive option because it can handle constraints, and because it makes it relatively easy and intuitive to control what kind of solution will be selected.

The main pitfall, if you want to use convex optimization, is that the set $\mathcal S = \{y \in \mathbb R^4: y_1^2 = y_2^2 + y_3^2 + y_4^2, y_1 \geq 0 \}$ is not convex*. So we can already conclude that the problem, as it stands now, is not solvable by convex optimisation.

However, if you relax the equality into an inequality, you define the modified set $\mathcal { \tilde S } = \{y \in \mathbb R^4: y_1^2 \geq y_2^2 + y_3^2 + y_4^2, y_1 \geq 0 \}$ which is convex. Indeed, the first equation

\begin{equation} y_1^2 \geq y_2^2 + y_3^2 + y_4^2 \end{equation}

can be rewritten as

\begin{equation} y_1 \geq \sqrt{y_2^2 + y_3^2 + y_4^2} = \big\lVert [\mathbf 0_{3\times1} \ \mathbf I_3 ] y \big\rVert_2 \end{equation}

because both sides are nonnegative. This is exactly the definition of a second-order cone, a well known class of convex sets. To obtain for example the form required by cvxpy, define:

\begin{align} A_1 &= [\mathbf 0_{3\times1} \ \mathbf I_3 ] \\ b_1 &= \mathbf 0_{3\times1} \\ c_1^\top &= [1, 0, 0, 0] \\ d_1 &= 0 \\ m &= 1 \end{align}

The linear part of your equation can be directly specified in cvxpy or any similar software, as can the inequality constraint $y_1 \geq 0$ (however, the latter is already implied by $y_1 \geq \sqrt{ \cdots }$, as the square root is always nonnegative).

You can now specify a linear cost function to select a suitable solution. In fact, at least in cvxpy, you can also define other convex cost functions, such as the euclidean distance to some point, which will be reformulated to standard SOCP form (epigraph reformulation).

Don't forget that you have now changed the problem and your solution may not satisfy the constraint with equality. You will have to play around with different cost functions and/or additional constraints, and check after solving if your point satisfies the constraint with equality.

Maybe you even manage to prove that this modified problem gives a solution to the orignal problem. To find out more, search for "convex relaxation", which is the term for what we've done by changing the equality to an inequality.

* To see that, take $a = (1, 1, 0, 0)$ and $b = (1, 0, 1, 0)$, which both are members of $\mathcal S$. Convexity of $\mathcal S$ would imply that $\gamma a + (1-\gamma) b \in \mathcal S \ \ (\forall \gamma \in [0, 1])$, and thus $1 = \gamma^2 + (1-\gamma)^2 = \gamma^2 + 1 - 2 \gamma + \gamma^2$ which is not satisfied for $\gamma \in (0, 1)$.