0
$\begingroup$

I'm solving underconstrained $Ax=b$ with additional constraint that entries of $x$ are non-negative.

This can be done with QuadraticOptimization by

  1. putting $||Ax-b||^2$ in the objective term
  2. putting $Ax=b$ in the constraint term
  3. both in the objective and in the constraint term

Choosing 1. gives more smooth solution, and a better guess of truth, than any solution involving constraints. Any idea why? Is it possible to encode this bias explicitly?

enter image description here

Background: Hausdorff moment problem: part 2, numeric stability post

(*Recover PDF of ArcSinDistribution[] at n points from m moments*)
{n, m} = {100, 20};
xvals = .5 (Cos[(Range[n] - .5) Pi/n] + 1); (*Chebychev spacing*)
yvals = PDF[ArcSinDistribution[], #] & /@ xvals;
dec[yvals_] := {xvals, yvals}\[Transpose]
originalPlot = 
  ListLinePlot[dec@yvals, PlotLabel -> "Original Problem", 
   ImageSize -> 300, Ticks -> None];

(*Form linear system Ax=b*)
{ii, zeros} = {IdentityMatrix[n], ConstantArray[0, n]};
A = Table[
    ChebyshevT[k, 2 p - 1], {p, xvals}, {k, 0, m - 1}]\[Transpose]; 
b = A . yvals;

(*Three ways of solving Ax=b with x>0 constraint*)
sol1 = {"||Ax-b||^2", 
   QuadraticOptimization[{Transpose[A] . A, -Transpose[A] . b}, {ii, 
     zeros}, {}]};
sol2 = {"Ax=b", QuadraticOptimization[0, {ii, zeros}, {A, -b}]};
sol3 = {"both", 
   QuadraticOptimization[{Transpose[A] . A, -Transpose[A] . b}, {ii, 
     zeros}, {A, -b}]};
{solNames, sols} = {sol1, sol2, sol3}\[Transpose];

solutionsPlot = ListPlot[dec /@ sols, Joined -> {True, False, True},
   PlotLabel -> "Solutions", Filling -> {2 -> Axis}, 
   PlotLegends -> solNames, ImageSize -> 300, Ticks -> None];
Grid[{{originalPlot, solutionsPlot}}]

nf[val_] := NumberForm[val, {3, 3}];
TableForm[{nf[Norm[A . # - b]], nf@Norm[# - yvals]} & /@ sols, 
 TableHeadings -> {solNames, {"train error", "test error"}}]
Improve this question
$\endgroup$
17
  • $\begingroup$ You say that 1 is better than 2 and 3. But the error of 1 is definitely bigger than 2 and 3, by factor of $10^8$! This means that in cases 2 and 3, QuadraticOptimization takes your linear constraint VERY seriously, and searches the best fit within the restricted, much smaller parameter subspace than the case 1 where there is no linear constraints. $\endgroup$ Commented Jun 21 at 8:15
  • $\begingroup$ I do not understand your sol2. You have 0 as the first argument in QuadraticOptimization[0, ...]. But what should then be minimized when the quadratic objective is constant and zero for any possible x? It has no sense to me. $\endgroup$ Commented Jun 21 at 8:30
  • $\begingroup$ Also the errors are relative to the constraints A.x-b==0 so there is no surprise that sol2 and sol3 have smaller error because the sol1 did not contained that constraint. But if you compute the error relative to originalPlot that sol1 has the smallest error. $\endgroup$ Commented Jun 21 at 8:53
  • 1
    $\begingroup$ Can you explain why you assume that quadratic objective 1/2 x . q . x + c . x (where {q,c}=={Transpose[A] . A, -Transpose[A] . b}) is same as ||Ax-b||^2? $\endgroup$ Commented Jun 21 at 9:17
  • $\begingroup$ @azerbajdzan because you can drop the constant term, here's the derivation $\endgroup$ Commented Jun 21 at 15:20

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.