CVXPY implimentation은 알아서 하시면 되구요.~

pip install CVXPY~

Review of Least Squares

import cvxpy as cp
# optimization variable
x1 = cp.Variable()
x2 = cp.Variable()
# constraints
constraints = [x1-x2<=3, x1+x2==10]
# objective function
obj_min = cp.Minimize((x1-3*x2)**2)
# set up a problem
prob = cp.Problem(obj_min, constraints)
# solve the problem
Ans = prob.solve()
print(prob)
print("\\n")
print("status: ",prob.status)
print("optimal value ",prob.value)
print("optimal var ", x1.value, x2.value)

Ax-b=0 을 만족시키는 x벡터가 존재한다고 하자.

그 벡터의 위치를 기준으로 d차원 공간에서 서서히 퍼져나가면서 Ax-b 가 양의 방향성 혹은 음의 방향성을 가지고 크기가 커지게 될 것이다. 그 녀석의 유클리드 norm을 취하면 각 벡터 컴포넌트들의 제곱을 취해 무조건 양수의 형태를 띄게 되고 중심부에서 멀어질 수록 값이 커지는 형태의 field가 형성 될 것이다.

그 중에 중심부를 찾는 Objective function은 다음과 같다.(위 그림의 남색에 다가가는 느낌)

$$ \min_{x} ||Ax-b||^2\\

$$

이 formula의 가장 큰 장점은 closed-form solution을 가지고 있다는 것이다.

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

We clained that this tis the solution.

Objective function is convex for sure, and stationary point is the optimal solution.

$$ \nabla||Ax^-b||^2=0\\ \nabla||Ax^-b||^2=\nabla(Ax-b)^T(Ax-b)\\ =\nabla(x^TA^TAx-x^TA^Tb-b^TAx+b^Tb)\\ =[(A^TA)^T+(A^TA)]x-A^Tb-b^TA\\ =2(A^TA)x-2A^Tb=0\\ $$

$$ (\because \nabla x^TBx = (B^T+B)x) $$