Convex optimization

The optimization problem have two components that are objective function $f_0:R^n\to R$ and the constraints. The objective function and constraints keep in check each other and make balance at saddle point i.e. optimal point. The dual (Lagrange) problem of the optimal problem also solve the optimization problem by making low boundary. The dual problem can be explained as a conjugate function $f^{\ast }=sup(x^{T}y-f(x\left)\right)$.

The purpose of approximation is finding optimal point $x^{\ast }$ i.e. $\nabla F\left(x^{\ast }\right)=0$. We need a step/search direction $\Delta x$ and step size $t$. Taylor approximation has polynomial arguments that is a step and parameters of derivatives at the start point. The first degree of Taylor approximation has one adding term from start point $(x_0,F(x_0\left)\right)$. The adding term $\nabla F\left(x\right)\Delta x$ is consistent with a parameter (gradient $\nabla F\left(x\right)$) and a argument (step $\Delta x$).

$$f\left(x\right)=\sum _{k=0}^{\infty }{c}_k{x}^k=c_0+c_{1}x+c_2{x}^2+\cdots .$$ This is an approximation that is a function of h and derivatives of $f\left(x\right)$ are elements of parameters. $f(x\pm h)=f\left(x\right)\pm h{f}^{\prime }\left(x\right)+\frac{h^2}{2}{f}^{\prime \prime }\left(x\right)\pm \frac{h^3}{6}{f}^{\prime \prime \prime }\left(x\right)+O\left(h^4\right)$ Let’s think about $\sin \left(x\right)$. $$f\left(x\right)=\sin \left(x\right)f\left(0\right)=0,f^{\prime }\left(x\right)=\cos \left(x\right)f^{\prime }\left(0\right)=1,f^{\prime \prime }\left(x\right)=-\sin \left(x\right)f^{\prime \prime }\left(0\right)=0$$ Thus, \[\begin{align*} \sin(x) &= 0 + \frac{1}{1!

This is summary of Boyd convex optimization. Steepest descent method is a convex optimization algorithm. The normalized steepest descent direction $x_{nsd}$ is a vector of unit ball of a norm that extends in the direction $-\nabla f\left(x\right)$. The inner product of $x_{nsd}$ and $-\nabla f\left(x\right)$ is maximized. The first order Taylor approximation of $f(x+v)=f\left(x\right)+\nabla f(x{)}^{T}v$ is most efficient when $v=x_{nsd}$. The $x_{nsd}$ is unnormalized into $x_{sd}$.

This is a summary of the Boyd convex optimization book. The strong convexity assumption can be useful to explain the iterative minimization algorithms like gradient descent, steepest descent, and Newton’s method. The smallest and largest eigen value of Hessian $m⪯{\nabla }^{2}f\left(x\right)⪯M$ with norm of gradient $\parallel \nabla f\left(x\right){\parallel }_2$ determine the boundary of optimal value $p^{\ast }$. The condition number of cond($C_{\alpha }$) $\le \frac{M}{m}$, where $C_{\alpha }$ is $\alpha$-sublevel.

There is a homology between a line segment and a convex set. It is helpful to understand the convex set. A line, a line segment, and one sideline has homology to an affine set, a convex set, and a cone. A line is $\{y|y={\theta }_1{x}_1+{\theta }_2{x}_2,{\theta }_1+{\theta }_2=1\}$ if ${\theta }_1,{\theta }_2\in R$, a line segment is if ${\theta }_1,{\theta }_2>0$ and an one side line if any ${\theta }_1,{\theta }_2<0$.