Category: convex Optimization

Quasiconvex and Quasiconcave functions Let $f:S rightarrow mathbb{R}$ where $S subset mathbb{R}^n$ is a non-empty convex set. The function f is said to be quasiconvex if for each $x_1,x_2 in S$, we have $fleft ( lambda x_1+left ( 1-lambda right )x_2 right )leq maxleft { fleft ( x_1 right ),fleft ( x_2 right ) right },lambda in left ( 0, 1 right )$ For example, $fleft ( x right )=x^{3}$ Let $f:Srightarrow R $ where $Ssubset mathbb{R}^n$ is a non-empty convex set. The function f is said to be quasiconvex if for each $x_1, x_2 in S$, we have $fleft ( lambda x_1+left ( 1-lambda right )x_2 right )geq minleft { fleft ( x_1 right ),fleft ( x_2 right ) right }, lambda in left ( 0, 1 right )$ Remarks Every convex function is quasiconvex but the converse is not true. A function which is both quasiconvex and quasiconcave is called quasimonotone. Theorem Let $f:Srightarrow mathbb{R}$ and S is a non empty convex set in $mathbb{R}^n$. The function f is quasiconvex if and only if $S_{alpha} =left ( x in S:fleft ( x right )leq alpha right }$ is convex for each real number alpha$ Proof Let f is quasiconvex on S. Let $x_1,x_2 in S_{alpha}$ therefore $x_1,x_2 in S$ and $max left { fleft ( x_1 right ),fleft ( x_2 right ) right }leq alpha$ Let $lambda in left (0, 1 right )$ and let $x=lambda x_1+left ( 1-lambda right )x_2leq max left { fleft ( x_1 right ),fleft ( x_2 right ) right }Rightarrow x in S$ Thus, $fleft ( lambda x_1+left ( 1-lambda right )x_2 right )leq maxleft { fleft ( x_1 right ), fleft ( x_2 right ) right }leq alpha$ Therefore, $S_{alpha}$ is convex. Converse Let $S_{alpha}$ is convex for each $alpha$ $x_1,x_2 in S, lambda in left ( 0,1right )$ $x=lambda x_1+left ( 1-lambda right )x_2$ Let $x=lambda x_1+left ( 1-lambda right )x_2$ For $x_1, x_2 in S_{alpha}, alpha= max left { fleft ( x_1 right ), fleft ( x_2 right ) right }$ $Rightarrow lambda x_1+left (1-lambda right )x_2 in S_{alpha}$ $Rightarrow f left (lambda x_1+left (1-lambda right )x_2 right )leq alpha$ Hence proved. Theorem Let $f:Srightarrow mathbb{R}$ and S is a non empty convex set in $mathbb{R}^n$. The function f is quasiconcave if and only if $S_{alpha} =left { x in S:fleft ( x right )geq alpha right }$ is convex for each real number $alpha$. Theorem Let $f:Srightarrow mathbb{R}$ and S is a non empty convex set in $mathbb{R}^n$. The function f is quasimonotone if and only if $S_{alpha} =left { x in S:fleft ( x right )= alpha right }$ is convex for each real number $alpha$. Learning working make money

Convex Optimization – Fritz-John Conditions Necessary Conditions Theorem Consider the problem − $min fleft ( x right )$ such that $x in X$ where X is an open set in $mathbb{R}^n$ and let $g_i left ( x right ) leq 0, forall i =1,2,….m$. Let $f:X rightarrow mathbb{R}$ and $g_i:X rightarrow mathbb{R}$ Let $hat{x}$ be a feasible solution and let f and $g_i, i in I$ are differentiable at $hat{x}$ and $g_i, i in J$ are continuous at $hat{x}$. If $hat{x}$ solves the above problem locally, then there exists $u_0, u_i in mathbb{R}, i in I$ such that $u_0 bigtriangledown fleft ( hat{x} right )+displaystylesumlimits_{iin I} u_i bigtriangledown g_i left ( hat{x} right )$=0 where $u_0,u_i geq 0,i in I$ and $left ( u_0, u_I right ) neq left ( 0,0 right )$ Furthermore, if $g_i,i in J$ are also differentiable at $hat{x}$, then above conditions can be written as − $u_0 bigtriangledown fleft ( hat{x}right )+displaystylesumlimits_{i=1}^m u_i bigtriangledown g_ileft ( hat{x} right )=0$ $u_ig_ileft (hat{x} right )$=0 $u_0,u_i geq 0, forall i=1,2,….,m$ $left (u_0,u right ) neq left ( 0,0 right ), u=left ( u_1,u_2,s,u_m right ) in mathbb{R}^m$ Remarks $u_i$ are called Lagrangian multipliers. The condition that $hat{x}$ be feasible to the given problem is called primal feasible condition. The requirement $u_0 bigtriangledown fleft (hat{x} right )+displaystylesumlimits_{i=1}^m u-i bigtriangledown g_ileft ( x right )=0$ is called dual feasibility condition. The condition $u_ig_ileft ( hat{x} right )=0, i=1, 2, …m$ is called complimentary slackness condition. This condition requires $u_i=0, i in J$ Together the primal feasible condition, dual feasibility condition and complimentary slackness are called Fritz-John Conditions. Sufficient Conditions Theorem If there exists an $varepsilon$-neighbourhood of $hat{x}N_varepsilon left ( hat{x} right ),varepsilon >0$ such that f is pseudoconvex over $N_varepsilon left ( hat{x} right )cap S$ and $g_i,i in I$ are strictly pseudoconvex over $N_varepsilon left ( hat{x}right )cap S$, then $hat{x}$ is local optimal solution to problem described above. If f is pseudoconvex at $hat{x}$ and if $g_i, i in I$ are both strictly pseudoconvex and quasiconvex function at $hat{x},hat{x}$ is global optimal solution to the problem described above. Example $min :fleft ( x_1,x_2 right )=left ( x_1-3 right )^2+left ( x_2-2 right )^2$ such that $x_{1}^{2}+x_{2}^{2} leq 5, x_1+2x_2 leq 4, x_1,x_2 geq 0$ And $hat{x}=left ( 2,1 right )$ Let $g_1left (x_1,x_2 right )=x_{1}^{2}+x_{2}^{2} -5,$ $g_2left (x_1,x_2 right )=x_1+2x_2-4,$ $g_3left (x_1,x_2 right )=-x_1$ and $g_4left ( x_1, x_2 right )= -x_2$. Thus the above constraints can be written as − $g_1left (x_1,x_2 right )leq 0,$ $g_2left (x_1,x_2 right )leq 0,$ $g_3left (x_1,x_2 right )leq 0$ and $g_4left (x_1,x_2 right )leq 0$ Thus, $I = left {1,2 right }$ therefore, $u_3=0,u_4=0$ $bigtriangledown f left (hat{x} right )=left (2,-2 right ),bigtriangledown g_1left (hat{x} right )=left (4,2 right )$ and $bigtriangledown g_2left (hat{x} right )=left (1,2 right )$ Thus putting these values in the first condition of Fritz-John conditions, we get − $u_0=frac{3}{2} u_2, ::u_1= frac{1}{2}u_2,$ and let $u_2=1$, therefore $u_0= frac{3}{2},::u_1= frac{1}{2}$ Thus Fritz John conditions are satisfied. $min fleft (x_1,x_2right )=-x_1$. such that $x_2-left (1-x_1right )^3 leq 0$, $-x_2 leq 0$ and $hat{x}=left (1,0right )$ Let $g_1left (x_1,x_2 right )=x_2-left (1-x_1right )^3$, $g_2left (x_1,x_2 right )=-x_2$ Thus the above constraints can be wriiten as − $g_1left (x_1,x_2 right )leq 0,$ $g_2left (x_1,x_2 right )leq 0,$ Thus, $I=left {1,2 right }$ $bigtriangledown fleft (hat{x} right )=left (-1,0right )$ $bigtriangledown g_1 left (hat{x} right )=left (0,1right )$ and $g_2 left (hat{x} right )=left (0, -1 right )$ Thus putting these values in the first condition of Fritz-John conditions, we get − $u_0=0,:: u_1=u_2=a>0$ Thus Fritz John conditions are satisfied. Learning working make money

Convex Optimization – Polar Cone Let S be a non empty set in $mathbb{R}^n$ Then, the polar cone of S denoted by $S^*$ is given by $S^*=left {p in mathbb{R}^n, p^Tx leq 0 : forall x in S right }$. Remark Polar cone is always convex even if S is not convex. If S is empty set, $S^*=mathbb{R}^n$. Polarity may be seen as a generalisation of orthogonality. Let $Csubseteq mathbb{R}^n$ then the orthogonal space of C, denoted by $C^perp =left { y in mathbb{R}^n:left langle x,y right rangle=0 forall x in C right }$. Lemma Let $S,S_1$ and $S_2$ be non empty sets in $mathbb{R}^n$ then the following statements are true − $S^*$ is a closed convex cone. $S subseteq S^{**}$ where $S^{**}$ is a polar cone of $S^*$. $S_1 subseteq S_2 Rightarrow S_{2}^{*} subseteq S_{1}^{*}$. Proof Step 1 − $S^*=left { p in mathbb{R}^n,p^Txleq 0 : forall 😡 in S right }$ Let $x_1,x_2 in S^*Rightarrow x_{1}^{T}xleq 0 $ and $x_{2}^{T}x leq 0,forall x in S$ For $lambda in left ( 0, 1 right ),left [ lambda x_1+left ( 1-lambda right )x_2 right ]^Tx=left [ left ( lambda x_1 right )^T+ left {left ( 1-lambda right )x_{2} right }^{T}right ]x, forall x in S$ $=left [ lambda x_{1}^{T} +left ( 1-lambda right )x_{2}^{T}right ]x=lambda x_{1}^{T}x+left ( 1-lambda right )x_{2}^{T}leq 0$ Thus $lambda x_1+left ( 1-lambda right )x_{2} in S^*$ Therefore $S^*$ is a convex set. For $lambda geq 0,p^{T}x leq 0, forall 😡 in S$ Therefore, $lambda p^T x leq 0,$ $Rightarrow left ( lambda p right )^T x leq 0$ $Rightarrow lambda p in S^*$ Thus, $S^*$ is a cone. To show $S^*$ is closed, i.e., to show if $p_n rightarrow p$ as $n rightarrow infty$, then $p in S^*$ $forall x in S, p_{n}^{T}x-p^T x=left ( p_n-p right )^T x$ As $p_n rightarrow p$ as $n rightarrow infty Rightarrow left ( p_n rightarrow p right )rightarrow 0$ Therefore $p_{n}^{T}x rightarrow p^{T}x$. But $p_{n}^{T}x leq 0, : forall x in S$ Thus, $p^Tx leq 0, forall x in S$ $Rightarrow p in S^*$ Hence, $S^*$ is closed. Step 2 − $S^{**}=left { q in mathbb{R}^n:q^T p leq 0, forall p in S^*right }$ Let $x in S$, then $ forall p in S^*, p^T x leq 0 Rightarrow x^Tp leq 0 Rightarrow x in S^{**}$ Thus, $S subseteq S^{**}$ Step 3 − $S_2^*=left { p in mathbb{R}^n:p^Txleq 0, forall x in S_2 right }$ Since $S_1 subseteq S_2 Rightarrow forall x in S_2 Rightarrow forall x in S_1$ Therefore, if $hat{p} in S_2^*, $then $hat{p}^Tx leq 0,forall x in S_2$ $Rightarrow hat{p}^Txleq 0, forall x in S_1$ $Rightarrow hat{p}^T in S_1^*$ $Rightarrow S_2^* subseteq S_1^*$ Theorem Let C be a non empty closed convex cone, then $C=C^**$ Proof $C=C^{**}$ by previous lemma. To prove : $x in C^{**} subseteq C$ Let $x in C^{**}$ and let $x notin C$ Then by fundamental separation theorem, there exists a vector $p neq 0$ and a scalar $alpha$ such that $p^Ty leq alpha, forall y in C$ Therefore, $p^Tx > alpha$ But since $left ( y=0 right ) in C$ and $p^Tyleq alpha, forall y in C Rightarrow alphageq 0$ and $p^Tx>0$ If $p notin C^*$, then there exists some $bar{y} in C$ such that $p^T bar{y}>0$ and $p^Tleft ( lambda bar{y} right )$ can be made arbitrarily large by taking $lambda$ sufficiently large. This contradicts with the fact that $p^Ty leq alpha, forall y in C$ Therefore,$p in C^*$ Since $x in C^*=left { q:q^Tpleq 0, forall p in C^* right }$ Therefore, $x^Tp leq 0 Rightarrow p^Tx leq 0$ But $p^Tx> alpha$ Thus is contardiction. Thus, $x in C$ Hence $C=C^{**}$. Learning working make money

Extreme point of a convex set Let S be a convex set in $mathbb{R}^n$. A vector $x in S$ is said to be a extreme point of S if $x= lambda x_1+left ( 1-lambda right )x_2$ with $x_1, x_2 in S$ and $lambda inleft ( 0, 1 right )Rightarrow x=x_1=x_2$. Example Step 1 − $S=left { left ( x_1,x_2 right ) in mathbb{R}^2:x_{1}^{2}+x_{2}^{2}leq 1 right }$ Extreme point, $E=left { left ( x_1, x_2 right )in mathbb{R}^2:x_{1}^{2}+x_{2}^{2}= 1 right }$ Step 2 − $S=left { left ( x_1,x_2 right )in mathbb{R}^2:x_1+x_2 Extreme point, $E=left { left ( 0, 0 right), left ( 2, 0 right), left ( 0, 1 right), left ( frac{2}{3}, frac{4}{3} right) right }$ Step 3 − S is the polytope made by the points $left { left ( 0,0 right ), left ( 1,1 right ), left ( 1,3 right ), left ( -2,4 right ),left ( 0,2 right ) right }$ Extreme point, $E=left { left ( 0,0 right ), left ( 1,1 right ),left ( 1,3 right ),left ( -2,4 right ) right }$ Remarks Any point of the convex set S, can be represented as a convex combination of its extreme points. It is only true for closed and bounded sets in $mathbb{R}^n$. It may not be true for unbounded sets. k extreme points A point in a convex set is called k extreme if and only if it is the interior point of a k-dimensional convex set within S, and it is not an interior point of a (k+1)- dimensional convex set within S. Basically, for a convex set S, k extreme points make k-dimensional open faces. Learning working make money

Convex Optimization – Cones A non empty set C in $mathbb{R}^n$ is said to be cone with vertex 0 if $x in CRightarrow lambda x in C forall lambda geq 0$. A set C is a convex cone if it convex as well as cone. For example, $y=left | x right |$ is not a convex cone because it is not convex. But, $y geq left | x right |$ is a convex cone because it is convex as well as cone. Note − A cone C is convex if and only if for any $x,y in C, x+y in C$. Proof Since C is cone, for $x,y in C Rightarrow lambda x in C$ and $mu y in C :forall :lambda, mu geq 0$ C is convex if $lambda x + left ( 1-lambda right )y in C : forall :lambda in left ( 0, 1 right )$ Since C is cone, $lambda x in C$ and $left ( 1-lambda right )y in C Leftrightarrow x,y in C$ Thus C is convex if $x+y in C$ In general, if $x_1,x_2 in C$, then, $lambda_1x_1+lambda_2x_2 in C, forall lambda_1,lambda_2 geq 0$ Examples The conic combination of infinite set of vectors in $mathbb{R}^n$ is a convex cone. Any empty set is a convex cone. Any linear function is a convex cone. Since a hyperplane is linear, it is also a convex cone. Closed half spaces are also convex cones. Note − The intersection of two convex cones is a convex cone but their union may or may not be a convex cone. Learning working make money

Convex Optimization – Jensen”s Inequality Let S be a non-empty convex set in $mathbb{R}^n$ and $f:S rightarrow mathbb{R}^n$. Then f is convex if and only if for each integer $k>0$ $x_1,x_2,…x_k in S, displaystylesumlimits_{i=1}^k lambda_i=1, lambda_igeq 0, forall i=1,2,s,k$, we have $fleft ( displaystylesumlimits_{i=1}^k lambda_ix_i right )leq displaystylesumlimits_{i=1}^k lambda _ifleft ( x right )$ Proof By induction on k. $k=1:x_1 in S$ Therefore $fleft ( lambda_1 x_1right ) leq lambda_i fleft (x_1right )$ because $lambda_i=1$. $k=2:lambda_1+lambda_2=1$ and $x_1, x_2 in S$ Therefore, $lambda_1x_1+lambda_2x_2 in S$ Hence by definition, $fleft ( lambda_1 x_1 +lambda_2 x_2 right )leq lambda _1fleft ( x_1 right )+lambda _2fleft ( x_2 right )$ Let the statement is true for $n Therefore, $fleft ( lambda_1 x_1+ lambda_2 x_2+….+lambda_k x_kright )leq lambda_1 fleft (x_1 right )+lambda_2 fleft (x_2 right )+…+lambda_k fleft (x_k right )$ $k=n+1:$ Let $x_1, x_2,….x_n,x_{n+1} in S$ and $displaystylesumlimits_{i=1}^{n+1}=1$ Therefore $mu_1x_1+mu_2x_2+…….+mu_nx_n+mu_{n+1} x_{n+1} in S$ thus,$fleft (mu_1x_1+mu_2x_2+…+mu_nx_n+mu_{n+1} x_{n+1} right )$ $=fleft ( left ( mu_1+mu_2+…+mu_n right)frac{mu_1x_1+mu_2x_2+…+mu_nx_n}{mu_1+mu_2+mu_3}+mu_{n+1}x_{n+1} right)$ $=fleft ( mu_y+mu_{n+1}x_{n+1} right )$ where $mu=mu_1+mu_2+…+mu_n$ and $y=frac{mu_1x_1+mu_2x_2+…+mu_nx_n}{mu_1+mu_2+…+mu_n}$ and also $mu_1+mu_{n+1}=1,y in S$ $Rightarrow fleft ( mu_1x_1+mu_2x_2+…+mu_nx_n+mu_{n+1}x_{n+1}right ) leq mu fleft ( y right )+mu_{n+1} fleft ( x_{n+1} right )$ $Rightarrow fleft ( mu_1x_1+mu_2x_2+…+mu_nx_n+mu_{n+1}x_{n+1}right ) leq$ $left ( mu_1+mu_2+…+mu_n right )fleft ( frac{mu_1x_1+mu_2x_2+…+mu_nx_n}{mu_1+mu_2+…+mu_n} right )+mu_{n+1}fleft ( x_{n+1} right )$ $Rightarrow fleft ( mu_1x_1+mu_2x_2+…+mu_nx_n +mu_{n+1}x_{n+1}right )leq left ( mu_1+ mu_2+ …+mu_n right )$ $left [ frac{mu_1}{mu_1+ mu_2+ …+mu_n}fleft ( x_1 right )+…+frac{mu_n}{mu_1+ mu_2+ …+mu_n}fleft ( x_n right ) right ]+mu_{n+1}fleft ( x_{n+1} right )$ $Rightarrow fleft ( mu_1x_1+mu_2x_2+…+mu_nx_n+mu_{n+1}x_{n+1}right )leq mu_1fleft ( x_1 right )+mu_2fleft ( x_2 right )+….$ Hence Proved. 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

Discuss Convex Optimization 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. Learning working make money

Convex Optimization – Norm A norm is a function that gives a strictly positive value to a vector or a variable. Norm is a function $f:mathbb{R}^nrightarrow mathbb{R}$ The basic characteristics of a norm are − Let $X$ be a vector such that $Xin mathbb{R}^n$ $left | x right |geq 0$ $left | x right |= 0 Leftrightarrow x= 0forall x in X$ $left |alpha x right |=left | alpha right |left | x right |forall 😡 in X and :alpha :is :a :scalar$ $left | x+y right |leq left | x right |+left | y right | forall x,y in X$ $left | x-y right |geq left | left | x right |-left | y right | right |$ By definition, norm is calculated as follows − $left | x right |_1=displaystylesumlimits_{i=1}^nleft | x_i right |$ $left | x right |_2=left ( displaystylesumlimits_{i=1}^nleft | x_i right |^2 right )^{frac{1}{2}}$ $left | x right |_p=left ( displaystylesumlimits_{i=1}^nleft | x_i right |^p right )^{frac{1}{p}},1 leq p leq infty$ Norm is a continuous function. Proof By definition, if $x_nrightarrow x$ in $XRightarrow fleft ( x_n right )rightarrow fleft ( x right ) $ then $fleft ( x right )$ is a constant function. Let $fleft ( x right )=left | x right |$ Therefore, $left | fleft ( x_n right )-fleft ( x right ) right |=left | left | x_n right | -left | x right |right |leq left | left | x_n-x right | :right |$ Since $x_n rightarrow x$ thus, $left | x_n-x right |rightarrow 0$ Therefore $left | fleft ( x_n right )-fleft ( x right ) right |leq 0Rightarrow left | fleft ( x_n right )-fleft ( x right ) right |=0Rightarrow fleft ( x_n right )rightarrow fleft ( x right )$ Hence, norm is a continuous function. Learning working make money

Convex Optimization – Direction Let S be a closed convex set in $mathbb{R}^n$. A non zero vector $d in mathbb{R}^n$ is called a direction of S if for each $x in S,x+lambda d in S, forall lambda geq 0.$ Two directions $d_1$ and $d_2$ of S are called distinct if $d neq alpha d_2$ for $ alpha>0$. A direction $d$ of $S$ is said to be extreme direction if it cannot be written as a positive linear combination of two distinct directions, i.e., if $d=lambda _1d_1+lambda _2d_2$ for $lambda _1, lambda _2>0$, then $d_1= alpha d_2$ for some $alpha$. Any other direction can be expressed as a positive combination of extreme directions. For a convex set $S$, the direction d such that $x+lambda d in S$ for some $x in S$ and all $lambda geq0$ is called recessive for $S$. Let E be the set of the points where a certain function $f:S rightarrow$ over a non-empty convex set S in $mathbb{R}^n$ attains its maximum, then $E$ is called exposed face of $S$. The directions of exposed faces are called exposed directions. A ray whose direction is an extreme direction is called an extreme ray. Example Consider the function $fleft ( x right )=y=left |x right |$, where $x in mathbb{R}^n$. Let d be unit vector in $mathbb{R}^n$ Then, d is the direction for the function f because for any $lambda geq 0, x+lambda d in fleft ( x right )$. Learning working make money