Category: convex Optimization

Convex Optimization – Conic Combination A point of the form $alpha_1x_1+alpha_2x_2+….+alpha_nx_n$ with $alpha_1, alpha_2,…,alpha_ngeq 0$ is called conic combination of $x_1, x_2,…,x_n.$ If $x_i$ are in convex cone C, then every conic combination of $x_i$ is also in C. A set C is a convex cone if it contains all the conic combination of its elements. Conic Hull A conic hull is defined as a set of all conic combinations of a given set S and is denoted by coni(S). Thus, $conileft ( S right )=left { displaystylesumlimits_{i=1}^k lambda_ix_i:x_i in S,lambda_iin mathbb{R}, lambda_igeq 0,i=1,2,…right }$ The conic hull is a convex set. The origin always belong to the conic hull. Learning working make money

Convex Optimization – Polyhedral Set A set in $mathbb{R}^n$ is said to be polyhedral if it is the intersection of a finite number of closed half spaces, i.e., $S=left { x in mathbb{R}^n:p_{i}^{T}xleq alpha_i, i=1,2,….,n right }$ For example, $left { x in mathbb{R}^n:AX=b right }$ $left { x in mathbb{R}^n:AXleq b right }$ $left { x in mathbb{R}^n:AXgeq b right }$ Polyhedral Cone A set in $mathbb{R}^n$ is said to be polyhedral cone if it is the intersection of a finite number of half spaces that contain the origin, i.e., $S=left { x in mathbb{R}^n:p_{i}^{T}xleq 0, i=1, 2,… right }$ Polytope A polytope is a polyhedral set which is bounded. Remarks A polytope is a convex hull of a finite set of points. A polyhedral cone is generated by a finite set of vectors. A polyhedral set is a closed set. A polyhedral set is a convex set. Learning working make money

Fundamental Separation Theorem Let S be a non-empty closed, convex set in $mathbb{R}^n$ and $y notin S$. Then, there exists a non zero vector $p$ and scalar $beta$ such that $p^T y>beta$ and $p^T x Proof Since S is non empty closed convex set and $y notin S$ thus by closest point theorem, there exists a unique minimizing point $hat{x} in S$ such that $left ( x-hat{x} right )^Tleft ( y-hat{x} right )leq 0 forall x in S$ Let $p=left ( y-hat{x} right )neq 0$ and $beta=hat{x}^Tleft ( y-hat{x} right )=p^That{x}$. Then $left ( x-hat{x} right )^Tleft ( y-hat{x} right )leq 0$ $Rightarrow left ( y-hat{x} right )^Tleft ( x-hat{x} right )leq 0$ $Rightarrow left ( y-hat{x} right )^Txleq left ( y-hat{x} right )^T hat{x}=hat{x}^Tleft ( y-hat{x} right )$ i,e., $p^Tx leq beta$ Also, $p^Ty-beta=left ( y-hat{x} right )^Ty-hat{x}^T left ( y-hat{x} right )$ $=left ( y-hat{x} right )^T left ( y-x right )=left | y-hat{x} right |^{2}>0$ $Rightarrow p^Ty> beta$ This theorem results in separating hyperplanes. The hyperplanes based on the above theorem can be defined as follows − Let $S_1$ and $S_2$ are be non-empty subsets of $mathbb{R}$ and $H=left { X:A^TX=b right }$ be a hyperplane. The hyperplane H is said to separate $S_1$ and $S_2$ if $A^TX leq b forall X in S_1$ and $A_TX geq b forall X in S_2$ The hyperplane H is said to strictly separate $S_1$ and $S_2$ if $A^TX b forall X in S_2$ The hyperplane H is said to strongly separate $S_1$ and $S_2$ if $A^TX leq b forall X in S_1$ and $A_TX geq b+ varepsilon forall X in S_2$, where $varepsilon$ is a positive scalar. Learning working make money

Convex Optimization – Convex Set Let $Ssubseteq mathbb{R}^n$ A set S is said to be convex if the line segment joining any two points of the set S also belongs to the S, i.e., if $x_1,x_2 in S$, then $lambda x_1+left ( 1-lambda right )x_2 in S$ where $lambda inleft ( 0,1 right )$. Note − The union of two convex sets may or may not be convex. The intersection of two convex sets is always convex. Proof Let $S_1$ and $S_2$ be two convex set. Let $S_3=S_1 cap S_2$ Let $x_1,x_2 in S_3$ Since $S_3=S_1 cap S_2$ thus $x_1,x_2 in S_1$and $x_1,x_2 in S_2$ Since $S_i$ is convex set, $forall$ $i in 1,2,$ Thus $lambda x_1+left ( 1-lambda right )x_2 in S_i$ where $lambda in left ( 0,1 right )$ Therfore, $lambda x_1+left ( 1-lambda right )x_2 in S_1cap S_2$ $Rightarrow lambda x_1+left ( 1-lambda right )x_2 in S_3$ Hence, $S_3$ is a convex set. Weighted average of the form $displaystylesumlimits_{i=1}^k lambda_ix_i$,where $displaystylesumlimits_{i=1}^k lambda_i=1$ and $lambda_igeq 0,forall i in left [ 1,k right ]$ is called conic combination of $x_1,x_2,….x_k.$ Weighted average of the form $displaystylesumlimits_{i=1}^k lambda_ix_i$, where $displaystylesumlimits_{i=1}^k lambda_i=1$ is called affine combination of $x_1,x_2,….x_k.$ Weighted average of the form $displaystylesumlimits_{i=1}^k lambda_ix_i$ is called linear combination of $x_1,x_2,….x_k.$ Examples Step 1 − Prove that the set $S=left { x in mathbb{R}^n:Cxleq alpha right }$ is a convex set. Solution Let $x_1$ and $x_2 in S$ $Rightarrow Cx_1leq alpha$ and $:and :Cx_2leq alpha$ To show:$::y=left ( lambda x_1+left ( 1-lambda right )x_2 right )in S :forall :lambda inleft ( 0,1 right )$ $Cy=Cleft ( lambda x_1+left ( 1-lambda right )x_2 right )=lambda Cx_1+left ( 1-lambda right )Cx_2$ $Rightarrow Cyleq lambda alpha+left ( 1-lambda right )alpha$ $Rightarrow Cyleq alpha$ $Rightarrow yin S$ Therefore, $S$ is a convex set. Step 2 − Prove that the set $S=left { left ( x_1,x_2 right )in mathbb{R}^2:x_{1}^{2}leq 8x_2 right }$ is a convex set. Solution Let $x,y in S$ Let $x=left ( x_1,x_2 right )$ and $y=left ( y_1,y_2 right )$ $Rightarrow x_{1}^{2}leq 8x_2$ and $y_{1}^{2}leq 8y_2$ To show − $lambda x+left ( 1-lambda right )yin SRightarrow lambda left ( x_1,x_2 right )+left (1-lambda right )left ( y_1,y_2 right ) in SRightarrow left [ lambda x_1+left ( 1- lambda)y_2] in Sright ) right ]$ $Now, left [lambda x_1+left ( 1-lambda right )y_1 right ]^{2}=lambda ^2x_{1}^{2}+left ( 1-lambda right )^2y_{1}^{2}+2 lambdaleft ( 1-lambda right )x_1y_1$ But $2x_1y_1leq x_{1}^{2}+y_{1}^{2}$ Therefore, $left [ lambda x_1 +left ( 1-lambda right )y_1right ]^{2}leq lambda ^2x_{1}^{2}+left ( 1- lambda right )^2y_{1}^{2}+2 lambdaleft ( 1- lambda right )left ( x_{1}^{2}+y_{1}^{2} right )$ $Rightarrow left [ lambda x_1+left ( 1-lambda right )y_1 right ]^{2}leq lambda x_{1}^{2}+left ( 1- lambda right )y_{1}^{2}$ $Rightarrow left [ lambda x_1+left ( 1-lambda right )y_1 right ]^{2}leq 8lambda x_2+8left ( 1- lambda right )y_2$ $Rightarrow left [ lambda x_1+left ( 1-lambda right )y_1 right ]^{2}leq 8left [lambda x_2+left ( 1- lambda right )y_2 right ]$ $Rightarrow lambda x+left ( 1- lambda right )y in S$ Step 3 − Show that a set $S in mathbb{R}^n$ is convex if and only if for each integer k, every convex combination of any k points of $S$ is in $S$. Solution Let $S$ be a convex set. then, to show; $c_1x_1+c_2x_2+…..+c_kx_k in S, displaystylesumlimits_{1}^k c_i=1,c_igeq 0, forall i in 1,2,….,k$ Proof by induction For $k=1,x_1 in S, c_1=1 Rightarrow c_1x_1 in S$ For $k=2,x_1,x_2 in S, c_1+c_2=1$ and Since S is a convex set $Rightarrow c_1x_1+c_2x_2 in S.$ Let the convex combination of m points of S is in S i.e., $c_1x_1+c_2x_2+…+c_mx_m in S,displaystylesumlimits_{1}^m c_i=1 ,c_i geq 0, forall i in 1,2,…,m$ Now, Let $x_1,x_2….,x_m,x_{m+1} in S$ Let $x=mu_1x_1+mu_2x_2+…+mu_mx_m+mu_{m+1}x_{m+1}$ Let $x=left ( mu_1+mu_2+…+mu_m right )frac{mu_1x_1+mu_2x_2+mu_mx_m}{mu_1+mu_2+………+mu_m}+mu_{m+1}x_{m+1}$ Let $y=frac{mu_1x_1+mu_2x_2+…+mu_mx_m}{mu_1+mu_2+………+mu_m}$ $Rightarrow x=left ( mu_1+mu_2+…+mu_m right )y+mu_{m+1}x_{m+1}$ Now $y in S$ because the sum of the coefficients is 1. $Rightarrow x in S$ since S is a convex set and $y,x_{m+1} in S$ Hence proved by induction. Learning working make money

Convex Optimization Tutorial Job Search This tutorial will introduce various concepts involved in non-linear optimization. Linear programming problems are very easy to solve but most of the real world applications involve non-linear boundaries. So, the scope of linear programming is very limited. Hence, it is an attempt to introduce the topics like convex functions and sets and its variants, which can be used to solve the most of the worldly problems. Audience This tutorial is suited for the students who are interested in solving various optimization problems. These concepts are widely used in bioengineering, electrical engineering, machine learning, statistics, economics, finance, scientific computing and computational mathematics and many more. Prerequisites The prerequisites for this course is introduction to linear algebra like introduction to the concepts like matrices, eigenvectors, symmetric matrices; basic calculus and introduction to the optimization like introduction to the concepts of linear programming. Learning working make money