# How to convert Ridge regression into a constraint optimization problem? [duplicate]

I hope this question wasn't asked before, I was looking for an answer and didn't find one. I'm trying to understand the Ridge regression problem.

If I understand correctly, Ridge regression is trying to solve the following problem:

Given $$A \in \mathbb{R}^{n \times d}$$, $$b \in \mathbb{R}^n$$ and $$\lambda \in \mathbb{R}$$, find $$x \in \mathbb{R}^d$$ that minimizes:

$$(1)$$ $$arg\,min_{x \in \mathbb{R}^d}(||Ax-b||_2^2+\lambda^2||x||_2^2)$$

I'm trying to understand the meaning of $$\lambda$$. I thought that the above equation is identical to the following equation:

$$(2)$$ $$arg\,min_{x \in \mathbb{R}^d}||Ax-b||_2^2$$ s.t. $$||x||_2^2 \leq \lambda^2$$

But after solving both problems separately in matlab, I got different solutions for $$x$$.

I solved problem $$(1)$$ by this formula: $$x={(A^TA + \lambda^2 I)}^{-1}A^Tb$$.

I solved problem $$(2)$$ by using $$cvx$$ library in matlab that is able to solve convex optimization problems.

As I said, in both cases I got different $$x$$. Are the two problems supposed to be identical? and if not, what change (if possible) should I do to problem $$(2)$$ so it can be identical to problem $$(1)$$.

Thanks

$$\textbf{Edit:}$$

Whoever put the link How exactly to compute the ridge regression penalty parameter given the constraint? for me. Thank you!

It indeed worked in Matlab and I got the same solution for both cases. But I did not expect to get such a strange solution.

Just to make sure I understand since it really looks strange to me.

By the answer in the link, you can actually convert the second problem to this problem:

$$arg\,min_{x \in \mathbb{R}^d}||Ax-b||_2^2$$ s.t. $$||x||_2^2 \leq ||x'||_2^2$$

where $$x'={(A^TA + \lambda^2 I)}^{-1}A^Tb$$ is the solution to the first problem.

It looks too trivial/strange since it means that the constraint is actually equal constraint and not 'less than or equal' constraint (the first one is a non-convex problem and the second one is a convex problem).

It also means that you need to solve the first problem and actually find $$x$$ from the first problem in order to find the same $$x$$ again in the second problem. which makes no point on solving the second problem.

Does it guarantee that it always finds

$$arg\,min_{x \in \mathbb{R}^d}||Ax-b||_2^2$$ s.t. $$||x||_2^2 = ||x'||_2^2$$ (non-convex problem)

and not

$$arg\,min_{x \in \mathbb{R}^d}||Ax-b||_2^2$$ s.t. $$||x||_2^2 < ||x'||_2^2$$ (convex problem)

Thanks!

## marked as duplicate by whuber♦ regression StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Feb 12 at 18:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Probably there is some transformation between the two forms of $\lambda$ that makes the two problems come out the same. Are your two $x$ vectors at least proportional to each other? – steveo'america Feb 12 at 18:30
• That the two problems differ can be appreciated by contemplating what happens as $\lambda$ becomes very large or close to zero. – whuber Feb 12 at 18:36
• I just checked it and the two $x$ vectors are not proportional to each other. each coordinate of $x$ in the first solution is scaled by a different number to get the corresponding coordinate in the second $x$. – David Feb 12 at 18:37
• I edited my question due to the link above. thanks! – David Feb 12 at 21:26
• Re the edit: I suspect you might be interested in the ideas presented in my answer at stats.stackexchange.com/a/301561/919. It seems to be almost the same question, if I understand you correctly. – whuber Feb 12 at 21:43