1
$\begingroup$

For quadratic programming, the trick can be implementing an constant. Example:

$$H = A^T Q A$$

$$Min: \frac{1}{2}x^THx + c^T x$$

Where $Q = \alpha I$

This gives more smooth optimal values. Just set $\alpha$ to a value like 0.85 and everything will be fine.

But how would I do that for linear programming?

$$Max: c^Tx$$ S.t $$Ax \le b \\ x \ge 0$$

I know that for ordinary least squares:

$$x = (A^TA)^{-1}A^Tb$$

Then we can add this feature and it will give us a regularized solution.

$$x = (A^TA + \alpha I)^{-1}A^Tb$$

But how should I write my objective function so it has the feature as well?

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Tikhonov_regularization maybe this is what you are looking for? $\endgroup$ – mathreadler Nov 23 at 19:14
  • $\begingroup$ Also please note that your "quadratic" is in fact just a linear least squares norm minimization. $\endgroup$ – mathreadler Nov 23 at 19:16
  • $\begingroup$ @mathreadler Not sure what you mean by that. But I like the url link you gave me. If I want to implement that on linear programming. How should I shape $c$ vector then? If I say that $c = A^T b$ and $Ax = b$ ? $\endgroup$ – Daniel Mårtensson Nov 23 at 19:19
  • $\begingroup$ expand $\frac 1 2 \| Q^{1/2}Ax \|_2^2$ and you will see it becomes precisely first term. $\endgroup$ – mathreadler Nov 23 at 19:20
  • $\begingroup$ Give that to $c$? $\endgroup$ – Daniel Mårtensson Nov 23 at 19:21
1
$\begingroup$

A typical linear least squares problem can be

$${\bf x_o} = \min_{\bf x}\left\{\|{\bf Ax-b}\|_2^2\right\}$$ with added Tikhonov regularization:

$${\bf x_o} = \min_{\bf x}\left\{\|{\bf Ax-b}\|_2^2 + \lambda \|{\bf I x}\|_2^2\right\}$$

which after expansion and differentiation setting $= 0$ vector et.c. reduces to

$${\bf x_o} = ({\bf A}^T{\bf A}+\lambda {\bf I})^{-1}({\bf A}^T{\bf b})$$

so the regularization is added to the ${\bf A}^T{\bf A}$ matrix in the left hand side, not multiplied somewhere in the middle of it.

so this $\bf A$ we have is in fact ${\bf Q}^{1/2}{\bf A}$ above so it will expand to:

$${\bf x_o} = ({\bf A}^T{\bf Q}^{T/2}{\bf Q}^{1/2}{\bf A}+\lambda {\bf I})^{-1}({\bf A}^T{\bf b})$$

Now assuming ${\bf Q}^{T/2}{\bf Q}^{1/2} = {\bf Q}$, well otherwise ${\bf Q}^{1/2}$ above would not even be defined.

$${\bf x_o} = ({\bf A}^T{\bf QA}+\lambda {\bf I})^{-1}({\bf A}^T{\bf b})$$

$\endgroup$
  • $\begingroup$ How can I implement that on the objective function? $\endgroup$ – Daniel Mårtensson Nov 23 at 19:35
  • $\begingroup$ But that's ordinary least square? $\endgroup$ – Daniel Mårtensson Nov 23 at 19:44
  • $\begingroup$ I need to use the simplex method for maximization. $\endgroup$ – Daniel Mårtensson Nov 23 at 19:45
  • $\begingroup$ Your question says nothing about any extra condition. $\endgroup$ – mathreadler Nov 23 at 19:45
  • $\begingroup$ Updated my question. $\endgroup$ – Daniel Mårtensson Nov 23 at 19:57
0
$\begingroup$

Here is the answer!

Let's say that you have the system $Ax = b$. OK! Then you want to find $x$ with regularization.

Use ordinary least square:

$$x = (A^TA + \alpha I)^{-1}A^Tb$$

If you want the same result, but using linear programming.

$$max : c^T x$$ With S.t to: $$Ax \le b \\ x \ge 0$$

Then you need to replace the constraints and the objective function to:

$$max : (A^TA + \alpha I)^Tb x$$ With S.t to: $$(A^TA + \alpha I)x \le A^Tb \\ x \ge 0$$

GNU Octave example:

>> A = [3 1; 4 6];
>> b = [3; 6];
>> a = 0.01; % Alpha is small
>> x = inv(A'*A + a*eye(2))*A'*b % Ordinary least square
x =

   0.85612
   0.42920

>> x = glpk((A'*A + a*eye(2))'*b, A'*A + a*eye(2), A'*b, [], [], repmat("U", 1, 2), repmat("C", 1, 2), -1) % LP
x =

   0.85612
   0.42920

>>
$\endgroup$
  • $\begingroup$ so the regularized problem does not depend on $c$? $\endgroup$ – LinAlg Nov 24 at 16:51
  • $\begingroup$ @LinAlg Well, I tried to use different values on $c$ but it did not result the same as ordinary least squares. So I think that $c$ should have that shape/value. Looks good for me. $\endgroup$ – Daniel Mårtensson Nov 24 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.