$\require{begingroup}\begingroup \DeclareMathOperator{\sign}{sign}$

I'm trying to solve the following optimization problem:

$$ \min_{x \in \mathbb{R}^n} \frac{1}{2} x^{\mathrm{T}} A x + b^{\mathrm{T}}x + \lVert Cx + d \rVert_2 $$

where $b \in \mathbb{R}^n$, $d \in \mathbb{R}^m$, $A \in \mathbb{R}^{n \times n}$, $C \in \mathbb{R}^{m \times n}$.

By applying the first order optimality conditions, I obtain that if $\lVert Cx + d \rVert > 0$, then $$ Ax + b + C^\mathrm{T} \frac{Cx + d}{\lVert Cx + d \rVert_2} = 0 $$ Otherwise, for the case of $\lVert Cx + d \rVert_2 = 0$, by taking the subgradient I obtain $$ Ax + b + C^\mathrm{T} g = 0 $$ where $g$ is any vector such that $\lVert g \rVert_2 \leq 1$.

I'm not sure how I should approach solving this problem. In the case where $n=m=1$, assuming that $\lvert Cx + d \rvert > 0$, then $$ \frac{Cx + d}{ \lVert Cx + d \rVert_2 } = \frac{Cx + d}{ \lvert Cx + d \rvert } = \sign(Cx + d) $$ Hence, $$ x = \begin{cases} -\frac{b + C}{A} & Cx + d > 0 \\ -\frac{b - C}{A} & Cx + d < 0 \\ \end{cases} $$ and this solution is applicable for $C(-\frac{b+C}{A}) + d > 0$ or $C(-\frac{b-C}{A}) + d < 0$. Otherwise, we apply $Cx + d = 0$ to obtain that $x = -\frac{d}{C}$. However, I'm not sure how to solve this for the case of $m, n > 1$. $\endgroup$

  • $\begingroup$ I'm not sure what you mean. If $\lVert Cx + d \rVert = 0$, then we know that $x = C^{-1} d$, otherwise $. However, I'm not sure how to determine whether this is indeed the case or not. $\endgroup$
    – oswinso
    Mar 20, 2021 at 6:10

1 Answer 1


Your minimization problem is best handled in another set of coordinates. Done right, one can avoid the square roots from the norm term.

Firstly, your work appears to tacitly assume that $A^{\mathsf{T}}=A$. I will assume $A$ is symmetric going forward, just for simplicity of notation. If not, then note that since the transpose is the identity on scalars, when we take the transpose of $x^{\mathsf{T}}Ax$, we obtain $$x^{\mathsf{T}}Ax=x^{\mathsf{T}}A^{\mathsf{T}}x$$ Adding $x^{\mathsf{T}}Ax$ to both sides and dividing by $2$ shows that $$x^{\mathsf{T}}Ax=x^{\mathsf{T}}\left(\frac{A+A^{\mathsf{T}}}{2}\right)x$$ Thus we can replace $A$ by its symmetric part.

Suppose $C$ is invertible. Let $y=Cx+d$, so that $x=C^{-1}y-C^{-1}d$ and let $P=(C^{-1})^{\mathsf{T}}AC^{-1}$. Note that $P$ is symmetric. You seek to minimize the expression $$f(y)=\frac{1}{2}y^{\mathsf{T}}Py-\frac{1}{2}y^{\mathsf{T}}Pd-\frac{1}{2}d^{\mathsf{T}}Py+b^{\mathsf{T}}y+\|y\|_2$$ in $y$, where I have dropped the constant terms $\frac{1}{2}d^{\mathsf{T}}Pd$ and $-b^{\mathsf{T}}C^{-1}d$. Rearranging a little, $$f(y)=\frac{1}{2}y^{\mathsf{T}}Py+\left(b^{\mathsf{T}}-d^{\mathsf{T}}P\right)y+\|y\|_2$$ To avoid writing that monstrosity inside the parentheses, I call it $\phi^{\mathsf{T}}=b^{\mathsf{T}}-d^{\mathsf{T}}P$.

Write $y=au$, where $u$ is a unit vector. We can now describe our problem as constrained minimization: we want to minimize $$f(au)=\frac{1}{2}a^2u^{\mathsf{T}}Pu+a\phi^{\mathsf{T}}u+a$$ subject to the constraint that $1=u^{\mathsf{T}}u$.

Applying Lagrange multipliers, an extremum occurs when: \begin{gather*} au^{\mathsf{T}}Pu+\phi^{\mathsf{T}}u+1=0\quad\quad(\partial_a) \\ a^2(Pu)^{\mathsf{T}}+a\phi^{\mathsf{T}}=2\lambda u^{\mathsf{T}}\quad\quad(\nabla_u) \\ 1=u^{\mathsf{T}}u\quad\quad(\text{constraint}) \end{gather*} Suppose we examine ($\nabla_u$) in the $u$ direction: then $$2\lambda=2\lambda u^{\mathsf{T}}u=a^2u^{\mathsf{T}}Pu+a\phi^{\mathsf{T}}u=-a$$ where the first equality comes from substituting (constraint) and the last from substituting ($\partial_a$).

Eliminating $\lambda$ and canceling a common factor of $a$, we now find $$aPu+\phi=-u$$ This is an eigenvalue problem, which I leave to you.

If $C$ is not invertible, then we can use the same tricks as above, but the algebra is more complicated. I will only sketch these cases. We can't say that $x=C^{-1}y-C^{-1}d$, but we can say that there is some linear transformation $T$ and (nonlinear!) function $v$ such that $x=Ty-Td+v(y)$ and $v(y)\in\ker{(C)}$ for all $y\in d+\text{im}{(C)}$. (This follows from the first isomorphism theorem of vector spaces, or, more prosaically, the definitions of image and kernel plus some algebra.)

To describe how to handle this, I would recommend changing basis to write $C$ as a block matrix: either $C=\begin{bmatrix}I_n&0\end{bmatrix}$ or $C=\left[\begin{smallmatrix}I_n\\0\end{smallmatrix}\right]$. (Note that this will change your values of $A$ and $b$.)

In the former case, where $C$ is surjective, we can choose a pseudoinverse to make $v$ linear. Consider $x$ as two separate vectors $(au-d,z)$ adjoined. Then $Cx+d=au$, and so your problem is to minimize $a+(\text{a polynomial in $a$, $u$, and $z$})$ subject to $1=u^{\mathsf{T}}u$.

In the latter case, $C$ is only injective. This is the hardest scenario. We can write $Cx+d$ as two vectors adjoined, but this does not help us make progress on eliminating the square roots. Instead, I would interpret your optimization problem as a highly-constrained one. To wit, let $\pi_1=\begin{bmatrix}I_n&0\end{bmatrix}$ be the projection $\mathbb{R}^m\to\mathbb{R}^n$ and $\pi_2$ the complementary projection, so that $\pi_1C=I_n$ and $\pi_2C=0$. Then you want to minimize $$a^2u^{\mathsf{T}}\pi_1^{\mathsf{T}}A\pi_1u+ab^{\mathsf{T}}\pi_1u+a$$ subject to the constraints $a\pi_2u=\pi_2d$ and $1=u^{\mathsf{T}}u$. (Note that this requires $m-n+1$ many Lagrange multipliers!)

  • $\begingroup$ I think there's a typo when you substitute $x$ for $y$ that doesn't change the correctness of your answer. $b^{\mathrm{T}} x = b^{\mathrm{T}} \Big(C^{-1} y - C^{-1} d \Big)$, but you've got $b^{\mathrm{T}} x = b^{\mathrm{T}} y$ written in your answer. $\endgroup$
    – oswinso
    Mar 20, 2021 at 17:18
  • $\begingroup$ Also, in the case that $C^{-1}$ is invertible, you say that the equation $aPu + \phi = -u$ is an eigenvalue problem. However, isn't this only the case when $\phi = 0$? If $\phi$ is nonzero, then how would you solve this? $\endgroup$
    – oswinso
    Mar 20, 2021 at 17:35
  • $\begingroup$ @oswinso: Yes, if $\phi\neq0$, then only the homogenous part is an eigenvalue problem. If $a^{-1}$ isn't an eigenvalue of $P$, then $-\phi=(aP+I_n)u$, which uniquely determines $u$ (and likely isn't a unit vector). For the other (finitely-many) $a$, the same formula plus any element of the corresponding eigenspace will be a satisfactory $u$...so find all eigenvectors that make the sum a unit vector. $\endgroup$ Mar 22, 2021 at 8:58
  • $\begingroup$ Also, typo now fixed. $\endgroup$ Mar 22, 2021 at 9:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .