# Finding minimum of penalty-approximated quadratic problem

Find the minimum of the following quadratic function

$$f_{\alpha}(x) := \frac{1}{2} x^T H x + c^T x + \frac{\alpha}{2}(b^Tx)^2$$

where matrix $$H$$ is symmetric and positive definite, and $$\alpha \geq 0$$.

I try to set gradient to zero and get

$$Hx+c+\alpha(b^Tx)b = 0$$

Now I have troubles to get $$x$$, because it is in the matrix multiplication and in the scalar product. Here some help would be useful.

The whole thing is actually a penalty approximation of the restricted problem to minimize

$$\text{minimize} \quad f(x)=\frac{1}{2}x^THx+c^Tx \quad \text{ subject to } x^T c = 0$$

I may show that the sequence of minima of $$f_{\alpha}(x)$$ converges to the minimum $$f(x)$$ with growing $$\alpha$$.

• Yes, α≥0 this is is required by the algorithm – Nikolskyy May 19 at 16:21
• Since $b^Tx$ is a scalar, it can right-multiply vector $b$ instead. Hence, $$Hx + c + \alpha (b^Tx) b = Hx + c + \alpha b b^T x = (H + \alpha b b^T) x + c = 0$$ where matrix $H + \alpha b b^T$ is clearly symmetric and positive definite. Keep in mind that there is seldom a good reason to invert a matrix. Linear systems are solved using Gaussian elimination. – Rodrigo de Azevedo May 19 at 16:28

$$\frac 12(b^T x)^2 = \frac 12(x^T b)(b^T x)\Rightarrow \partial_x\frac 12(b^T x)^2 = b(b^T x)$$
$$\left(H+\alpha b b^T\right)x + c = 0\Rightarrow x = -\left(H+\alpha bb^T\right)^{-1}c$$