本文仅供学习使用
本文参考：
B站：CLEAR_LAB
笔者带更新-运动学
课程主讲教师：
Prof. Wei Zhang
课程链接 ：
https://www.wzhanglab.site/teaching/mee-5114-advanced-control-for-robotics/

---

1. Motivation

Optimization is argulably the most important tool for modern engineering

Robotics:

• Differential Inverse Kinematics
• Dynamics : ABA(most efficient dynamics algorithm) and LQR
• Motion planning
• Whole-body control: formulated as a quadratic program
• SLAM
• Preception

Machine Learning

• Linear regression
• Support vector machine
• Deep learning —— minimize ‘loss’ function

Other domains

• Check system stability : SDP
• Compressive sensing
• Fourier transform : keast square problem

Roughly speaking, most engineering problems (finding a better design, ensure certain properties of the solution, develop an algorithm), can be formulated as optimization / optimal control problems.

Our goal :

• Basic knowledge/key concepts of opt. theory
• Formulate / Reformulate opt. problem
• Educated users of tools/packages

2. Some Linear Algebra

2.1 Real Symmetric Matrices

${\mathcal{S}}^n\in {\mathbb{R}}^{n\times n}$ : set of real symmetric matrices in ${\mathbb{R}}^n$ , $A\in {\mathcal{S}}^n\iff A^{\mathrm{T}}=A$

All eigenvalues are real (diagonalizable) —— Important

There exists a full set of orthogonal eigenvectors $A\in {\mathcal{S}}^n,A=T\Lambda T^{-1}$ nonsigular matrix

Spectral decomposition : If $A\in {\mathcal{S}}^n$ , then $A=Q\Lambda Q^{-1}$ , where $\Lambda$ diagonal and $Q$ is unitary —— $Q^{\mathrm{T}}Q=E$ $Q=\left[q_1,...,q_{\mathrm{n}}\right]$ $q_{\mathrm{i}}$ is $i$th-column of $Q$ —— $\Rightarrow {q_{\mathrm{i}}}^{\mathrm{T}}{q}_{\mathrm{j}}=\{\begin{array}{l}0i=j\\ 1otherwise\end{array}$ , { q i } \left\{ q_{\mathrm{i}} \right\} {qi​} orthonormal

2.2 Positive Semidefinite Matrices

$A\in {\mathcal{S}}^n$ is called positive semidefinite(PSD), denoted by $A⪰0$ , if $x^{\mathrm{T}}Ax⩾0,\forall x\in {\mathbb{R}}^n$

$A\in {\mathcal{S}}^n$ is called positive definite(PD) , denoted by $A\succ 0$ , $x^{\mathrm{T}}Ax>0$ for all nonzero $x\in {\mathbb{R}}^n$

${\mathcal{S}}_{+}^n$ : set of all PSD (symmetric) matrices

${\mathcal{S}}_{++}^n$ : set of all PD (symmetric) matrices

PSD or PD matrices can also be defined for non-symmetric matrices : e.g. $\left[\begin{array}{cc}1& 1\\ -1& 1\end{array}\right]\Rightarrow x^{\mathrm{T}}\left[\begin{array}{cc}1& 1\\ -1& 1\end{array}\right]x={x_1}^2+{x_2}^2$

We assume PSD and PD are symmetric (unless otherwise noted)

Notation : $A⪰B$ (resp. $A\succ B$) means $A-B\in {\mathcal{S}}_{+}^n$ (resp. $A-B\in {\mathcal{S}}_{++}^n$) —— $A-B$ PSD - defined a partial order on ${\mathcal{S}}^n$ —— It is possible to have $A\nsucc B,A⋡B$

Other equivalent definitions for symmetric PSD matrices :

• All $2^n-1$ principal minors of $A$ are nonnegative
• All eigs of $A$ are nonnegative
• There exists a factorization $A=B^{\mathrm{T}}B$

Other equivalent definitions for symmetric PD matrices :

• All $n$ principal minors of $A$ are positive
• All eigs of $A$ are strictly positive
• There exists a factorization $A=B^{\mathrm{T}}B$ with $B$ square and nonsingular
  If $A>0$ , $A=Q\Lambda Q^{\mathrm{T}}=Q{\Lambda }^{\frac{1}{2}}{\Lambda }^{\frac{1}{2}}{Q}^{\mathrm{T}}=B^{\mathrm{T}}B,B={\Lambda }^{\frac{1}{2}}{Q}^{\mathrm{T}}$

Useful facts :

• If $T$ nonsigular(doesn’t need to unitary) , $A\succ 0\iff T^{\mathrm{T}}AT\succ 0$ and $A⪰0\iff T^{\mathrm{T}}AT⪰0$
  Recall : $TA{T}^{-1}$ : similarity transformation ${\mathcal{S}}_{+}^n$ ; $T^{\mathrm{T}}AT$: congruent transformation ${\mathcal{S}}_{++}^n$ —— are invariant under congruent transformation

• Inner product on ${\mathbb{R}}^{m\times n}$ : $<A,B>=tr\left(A^{\mathrm{T}}B\right)=A\cdot B$
  $\forall A\in {\mathbb{R}}^{m\times n},B\in {\mathbb{R}}^{m\times n}tr\left(A^{\mathrm{T}}B\right)={\sum }_{i=1}^m{\sum }_{j=1}^n{A}_{\mathrm{ij}}{B}_{\mathrm{ij}}$ , Angle between $A,B$ $\cos \theta =\frac{<A,B>}{\sqrt{<A,A><B,B>}},\{\begin{array}{l}A\perp B\Rightarrow tr\left(A^{\mathrm{T}}B\right)=0\\ tr\left(A^{\mathrm{T}}B\right)>0\Rightarrow acute\end{array}$

• For $A,B\in {\mathcal{S}}_{+}^n,tr\left(AB\right)>0$ —— $A,B$ square symmetric PSD : $<A,B>=tr\left(A^{\mathrm{T}}B\right)=tr\left(AB\right)\Rightarrow tr\left(AB\right)⩾0$

• For ant symmetric $A\in {\mathcal{S}}^n$ , ${\lambda }_{\min }\left(A\right)⩾\mu \iff A⪰\mu E$ and ${\lambda }_{\max }\left(A\right)⩽\beta \iff A⪯\beta E$ (easy proof)

3. Set and Functions

3.1 Affine Sets and Functions

Linear mapping : $f\left(x+y\right)=f\left(x\right)+f\left(y\right),f\left(\alpha x\right)=\alpha f\left(x\right)$ , for any $x,y$ in some vector space , and $\alpha \in \mathbb{R}$

Examples:

• $f\left(x\right)=Ax,x\in {\mathbb{R}}^3,A\in SO\left(3\right)$
• $f\left(x\right)=\int x\left(\tau \right)d\tau$ , for all integrable function $x\left(\cdot \right)$
• $E\left(x\right)$ expection of random variable/vector $x$ —— $E\left(x\right)=\int xf\left(x\right)dx$
• $f\left(x\right)=tr\left(x\right),x\in {\mathbb{R}}^{n\times n}$

Affine mapping : $f\left(x\right)$ is an affine mapping of $x$ if $g\left(x\right)=f\left(x\right)-f\left(x_0\right)$ is a linear mapping for some fixed $x_0$

Finite-deimension representation fo affine function : $f\left(x\right)=Ax+b$ —— $g\left(x\right)=f\left(x\right)-f\left(0\right)=Ax+b-b=Ax$

Homogeneous representation in ${\mathbb{R}}^n$ : $f\left(x\right)=Ax+b\iff \hat{f}\left(x\right)=\hat{A}\hat{x},\hat{A}=\left[\begin{array}{cc}A& b\\ 0& 1\end{array}\right],\hat{x}=\left[\begin{array}{c}x\\ 1\end{array}\right]$

Linear and affine are often used interchangeably

Linear/affine sets: { x : f ( x ) ⩽ 0 } \left\{ x:f\left( x \right) \leqslant 0 \right\} {x:f(x)⩽0} ofr affine mapping $f$

• Line/hyperplane : $a^{\mathrm{T}}x=b$
  $a^{\mathrm{T}}x=b\Rightarrow a^{\mathrm{T}}\left(x-x_0\right)=0\Rightarrow a^{\mathrm{T}}x-a^{\mathrm{T}}{x}_0=0,a^{\mathrm{T}}{x}_0=b$
• Half space : $a^{\mathrm{T}}x⩽b$ —— $a^{\mathrm{T}}x-a^{\mathrm{T}}{x}_0⩽0$
• Polyhedron : $Hx⩽h$ —— $H\in {\mathbb{R}}^{m\times n},x\in {\mathbb{R}}^n,h\in {\mathbb{R}}^m$
  $\left[\begin{array}{c}{H_1}^{\mathrm{T}}\\ ⋮\\ {H_{\mathrm{m}}}^{\mathrm{T}}\end{array}\right]x⩽\left[\begin{array}{c}{h}_1\\ ⋮\\ h_{\mathrm{m}}\end{array}\right]$ —— Imposes $m$ inequality ${H_{\mathrm{i}}}^{\mathrm{T}}x⩽h_{\mathrm{i}}$ —— half space
• For matrix variable $X\in {\mathbb{R}}^{n\times n}$, $tr\left(AX\right)⩽0$ for given constant matrix $A\in {\mathbb{R}}^{n\times n}$ is halfspace in ${\mathbb{R}}^{n\times n}$
  

3.2 Qyadratic Sets and Functions

Quadratic functions in ${\mathbb{R}}^n$ : $f\left(x\right)=x^{\mathrm{T}}Ax+b^{\mathrm{T}}x+c,x=\left[\begin{array}{c}{x}_1\\ ⋮\\ x_{\mathrm{n}}\end{array}\right],f:{\mathbb{R}}^n\to \mathbb{R}$

Quadratic functions (honogeneous form) : $\hat{x}=\left[\begin{array}{c}x\\ 1\end{array}\right],\hat{f}\left(x\right)={\left[\begin{array}{c}x\\ 1\end{array}\right]}^{\mathrm{T}}\left[\begin{array}{cc}A& \frac{b}{2}\\ \frac{b}{2}& c\end{array}\right]\left[\begin{array}{c}x\\ 1\end{array}\right]$ —— $\hat{f}\left(x\right)={\hat{x}}^{\mathrm{T}}\hat{A}\hat{x}$ ($A\in {\mathcal{S}}_{+}^n\iff f\left(x\right)⩾0,\forall x\in {\mathbb{R}}^n$) —— $f$ - PSD $f\left(x\right)>0$ for all $x\ne 0$ ; $f\left(x\right)=0$ for all $x=0$

Quadratic sets : { x ∈ R n : f ( x ) ⩽ 0 } \left\{ x\in \mathbb{R} ^n:f\left( x \right) \leqslant 0 \right\} {x∈Rn:f(x)⩽0} for some quadratic function $f$
eg1: Ball —— $\left\{x\in {\mathbb{R}}^n{\Vert x-x_{\mathrm{c}}\Vert }^2⩽{r_{\mathrm{c}}}^2\right\}$ $\Rightarrow f\left(x\right)={\left(x-x_{\mathrm{c}}\right)}^{\mathrm{T}}\left(x-x_{\mathrm{c}}\right)-{r_{\mathrm{c}}}^2⩽0$
eg2 : Ellipsoid : $\left\{x\in {\mathbb{R}}^n{\left(x-x_{\mathrm{c}}\right)}^{\mathrm{T}}{P}^{-1}\left(x-x_{\mathrm{c}}\right)⩽1,P\in {\mathcal{S}}_{++}^n\right\}$

3.3 Convex Set

Convex Set : A set $S$ is convex if any line segment stays in the set
$$x_1,x_2\in S\Rightarrow \alpha x_1+\left(1-\alpha \right)x_2\in S,\forall \alpha \in \left[0,1\right]\Rightarrow {\alpha }_1{x}_1+{\alpha }_2{x}_2,{\alpha }_1+{\alpha }_2=1,{\alpha }_1⩾0,{\alpha }_2⩾0$$

• convex combination of $x_1,x_2$
  

Convex combination of $x_1,...,x_{\mathrm{k}}$ :
$$\left\{{\alpha }_1{x}_1+{\alpha }_2{x}_2+...+{\alpha }_{\mathrm{k}}{x}_{\mathrm{k}}:{\alpha }_{\mathrm{i}}⩾0,\sum _i{\alpha }_{\mathrm{i}}=1\right\}$$

Convex hull-凸包 : c o ‾ { S } \overline{co}\left\{ S \right\} co{S} set of all convex combinations of points in $S$

3.4 Cone

A set $S$ is called a cone if $\lambda >0,x\in S\Rightarrow \lambda x\in S$

Conic-圆锥的 combination of $x_1$ and $x_2$ : $x={\alpha }_1{x}_1+{\alpha }_2{x}_2,{\alpha }_1⩾0,{\alpha }_2⩾0$ —— c o n e ( x 1 , . . . , x k ) = { ∑ i α i x i : α i ⩾ 0 } cone\left( x_1,...,x_{\mathrm{k}} \right) =\left\{ \sum_i{\alpha _{\mathrm{i}}x_{\mathrm{i}}}:\alpha _{\mathrm{i}}\geqslant 0 \right\} cone(x1​,...,xk​)={∑i​αi​xi​:αi​⩾0}

Convex cone:

1. a cone that is convex
2. equivalently,a set that contains all the conic combinations of points in the set

3.5 Positve Semidefinite Cone

The set of positive semidefinite matrices(i.e, ${\mathcal{S}}_{+}^n$ is a convex cone and is referred to as the positive semidefinite(PSD) cone) —— ${\mathcal{S}}_{+}^n$ : set of PSD $A\in {\mathcal{S}}_{+}^n\Rightarrow \lambda A⩾0\Rightarrow \lambda A\in {\mathcal{S}}_{+}^n$ ${\mathcal{S}}_{+}^n$ is a cone
By definition : pick arbitrary $A,B\in {\mathcal{S}}_{+}^n$ , $\alpha A+\left(1-\alpha \right)B\in {\mathcal{S}}_{+}^n,\alpha \in \left[0,1\right]$ ($\Rightarrow x^{\mathrm{T}}\left(\alpha A+\left(1-\alpha \right)B\right)x=\alpha x^{\mathrm{T}}Ax+\left(1-\alpha \right)x^{\mathrm{T}}Bx⩾0$)

Recall that if $A,B\in {\mathcal{S}}_{+}^n$ , then $tr\left(AB\right)⩾0$ . This indicates that the cone ${\mathcal{S}}_{+}^n$ is acute.

$x_1\in {\mathbb{R}}^n,x_2\in {\mathbb{R}}^n$
${\alpha }_1{x}_1+{\alpha }_2{x}_2$ linear combination
${\alpha }_1{x}_1+{\alpha }_2{x}_2$ ${\alpha }_1⩾0,{\alpha }_2⩾0$ conic combination
${\alpha }_1{x}_1+{\alpha }_2{x}_2$ ${\alpha }_1⩾0,{\alpha }_2⩾0$ ${\alpha }_1+{\alpha }_2=1$ convex combination

3.6 Operations that Preserve Convexity

Intersection of possibly infinite number of convex sets is convex
eg: polyhedron —— ${H_1}^{\mathrm{T}}x⩽h_1,{H_2}^{\mathrm{T}}x⩽h_2,\left[\begin{array}{c}{H_1}^{\mathrm{T}}\\ {H_2}^{\mathrm{T}}\end{array}\right]x⩽\left[\begin{array}{c}{h}_1\\ h_2\end{array}\right]$
eg: PSD cone

Affine mapping $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ (i.e. $f\left(x\right)=Ax+b$)

• f ( X ) = { f ( x ) : x ∈ X } f\left( X \right) =\left\{ f\left( x \right) :x\in X \right\} f(X)={f(x):x∈X} is convex whenever $X\subseteq {\mathbb{R}}^n$ is convex
  e.g. : Ellipsoid : $E_1=\left\{x\in {\mathbb{R}}^n:{\left(x-x_{\mathrm{c}}\right)}^{\mathrm{T}}{P}^{-1}\left(x-x_{\mathrm{c}}\right)⩽1\right\}$ or E 2 = { x c + A u : ∥ u ∥ 2 ⩽ 1 } E_2=\left\{ x_{\mathrm{c}}+Au:\left\| u \right\| _2\leqslant 1 \right\} E2​={xc​+Au:∥u∥2​⩽1}
• f − 1 ( Y ) = { x ∈ R n : f ( x ) ∈ Y } f^{-1}\left( Y \right) =\left\{ x\in \mathbb{R} ^n:f\left( x \right) \in Y \right\} f−1(Y)={x∈Rn:f(x)∈Y} is convex whenever $Y\subseteq {\mathbb{R}}^m$ is convex
  e.g. { A x ⩽ b } = f − 1 ( R + n ) \left\{ Ax\leqslant b \right\} =f^{-1}\left( \mathbb{R} _{+}^{n} \right) {Ax⩽b}=f−1(R+n​) , where ${\mathbb{R}}_{+}^n$ in nonnegative orthant

3.7 Convex Function

Consider a finite dimensional vector space $\chi$ . Let $\mathcal{D}\subset \chi$ be convex

Definition 1 (Convex Function)
A function $f:\mathcal{D}\to \mathbb{R}$ is called convex if
$$f\left(\alpha x_1+\left(1-\alpha \right)x_2\right)⩽\alpha f\left(x_1\right)+\left(1-\alpha \right)f\left(x_2\right),\forall x_1,x_2\in \mathcal{D},\forall \alpha \in \left[0,1\right]$$

• $f:\mathcal{D}\to \mathbb{R}$ is called strictly convex if
  $f\left(\alpha x_1+\left(1-\alpha \right)x_2\right)<\alpha f\left(x_1\right)+\left(1-\alpha \right)f\left(x_2\right),\forall x_1\ne x_2\in \mathcal{D},\forall \alpha \in \left[0,1\right]$
• $f:\mathcal{D}\to \mathbb{R}$ is called concave if $-f$ is convex

3.8 How to Check a Function of Convex?

Directly use definition

• First-order condition : if $f$ is differentiable over an open set that contains $\mathcal{D}$ , then $f$ is convex over $\mathcal{D}$ iff(if and only if) —— stay above Taylor around $x$
  $$f\left(z\right)⩾f\left(x\right)+\nabla f{\left(x\right)}^{\mathrm{T}}\left(z-x\right),\forall x,z\in \mathcal{D}$$
• Second-order condition: Suppose $f$ is twicely differentiable over an open set that contains $\mathcal{D}$ , then $f$ is convex over $\mathcal{D}$ iff
  $${\nabla }^{2}f\left(x\right)⪰0$$
  (concave ${\nabla }^{2}f\left(x\right)⪯0$)
  Many other conditions , tricks,…

3.9 Example of Convex Functions

In general , affine functions are both convex and concave
e.g. : $f\left(x\right)=a^{\mathrm{T}}x+b,x\in {\mathbb{R}}^n$
e.g. : $f\left(X\right)=tr\left(A^{\mathrm{T}}X\right)+c={\sum }_{i=1}^m{\sum }_{j=1}^n{A}_{\mathrm{ij}}{X}_{\mathrm{ij}}+c,X\in {\mathbb{R}}^{m\times n}$
$f:{\mathbb{R}}^{m\times n}\to scalar$ / affine func of $X$ (matrix)

Quadratic functions : $f\left(x\right)=x^{\mathrm{T}}Qx+b^{\mathrm{T}}x+c$ is convex iff $Q⪰0$
unsing 2nd-order condition ${\nabla }^{2}f\left(x\right)=\left[\begin{array}{ccc}\frac{{\partial }^{2}f}{\partial x_1\partial x_1}& \frac{{\partial }^{2}f}{\partial x_1\partial x_2}& \cdots \\ ⋮& \frac{{\partial }^{2}f}{\partial x_2\partial x_2}& \cdots \\ ⋮& ⋮& \ddots \end{array}\right]=Q$

All norms are convex
e.g. : in ${\mathbb{R}}^n$ : $f\left(x\right)={\Vert x\Vert }_{\mathrm{p}}={\left({\sum }_{i=1}^n{\left|x_{\mathrm{i}}\right|}^p\right)}^{1/p}$ , ${\Vert x\Vert }_{\infty }={\max }_{\mathrm{k}}\left|x_{\mathrm{k}}\right|$
e.g. : in ${\mathbb{R}}^{m\times n}$ : $f\left(X\right)={\Vert X\Vert }_2={\sigma }_{\max }$

Affine mapping of convex func is still convex
e.g. : suppose $f\left(x\right)$ convex $\Rightarrow$ $g\left(x\right)=af\left(x\right)+b$ is also convex

Pointwise maximum of convex func is convex
e.g. : suppose $f_1\left(x\right),f_2\left(x\right)$ are convex $\Rightarrow$ g ( x ) = max ⁡ { f 1 ( x ) , f 2 ( x ) } g\left( x \right) =\max \left\{ f_1\left( x \right) ,f_2\left( x \right) \right\} g(x)=max{f1​(x),f2​(x)} is convex

e.g. : suppose $f\left(x,\theta \right)$ is convex for each $\theta \in \left[1,2\right]$ , then g ( x ) = max ⁡ θ ∈ [ 1 , 2 ] { f ( x , θ ) } g\left( x \right) =\underset{\theta \in \left[ 1,2 \right]}{\max}\left\{ f\left( x,\theta \right) \right\} g(x)=θ∈[1,2]max​{f(x,θ)} convex —— $f\left(x,\theta \right)=\theta x+b$ $\Rightarrow$ g ( x ) = max ⁡ θ ∈ [ 1 , 2 ] { θ x + b } g\left( x \right) =\underset{\theta \in \left[ 1,2 \right]}{\max}\left\{ \theta x+b \right\} g(x)=θ∈[1,2]max​{θx+b}

Pointwise minimum of concave func is concave —— S ( x ) = min ⁡ θ ∈ [ 1 , 2 ] { θ x + b } S\left( x \right) =\underset{\theta \in \left[ 1,2 \right]}{\min}\left\{ \theta x+b \right\} S(x)=θ∈[1,2]min​{θx+b} is concave

4. Short Introduction to Optimization

4.1 Nonlinear Optimiazation Problems

Nonlinear Optimiazation： Primal problem
minimize : $f_0\left(x\right)$ —— cost func $f:{\mathbb{R}}^n\to \mathbb{R}$ , $x=\left[\begin{array}{c}{x}_1\\ ⋮\\ x_{\mathrm{n}}\end{array}\right]\in {\mathbb{R}}^n$
subject to : $f_{\mathrm{i}}\left(x\right)⩽0,i=1,\cdots ,m,h_{\mathrm{j}}\left(x\right)=0,j=1,\cdots ,q$ —— constrain set C = { x ∈ R n : f i ( x ) ⩽ 0 , h j ( x ) = 0 } C=\left\{ x\in \mathbb{R} ^n:f_{\mathrm{i}}\left( x \right) \leqslant 0,h_{\mathrm{j}}\left( x \right) =0 \right\} C={x∈Rn:fi​(x)⩽0,hj​(x)=0} , if $x\in C$ , then $x$ is called feasible

decison variable $x\in {\mathbb{R}}^n$ , domain $\mathcal{D}$, referred to as primal problem

optimal value $p^{\ast }$

is called a convex optimization problem if $f_0,...,f_{\mathrm{m}}$ are convex and $h_1,...,h_{\mathrm{q}}$ are affine —— means objective function $f_0$ is convex and constrain set is convex

typically convex optimization can be solved efficiently

• Categories :
  objective func (Linear/affine) + constrain set/func(Linear/affine) —— Linear Program LP
  objective func (Quardratic - convex) + constrain set/func(Linear/affine) —— Quardratic Program QP
  objective func (Quardratic - convex) + constrain set/func(uardratic) —— Quardratic Constrained Quardratic Program QCQP - Hard to solve
  
• How to find optimal solutions?
  optimality condition: for unconstrained problems : 1st-order optimality condition $x^{\ast }$ is local minimizer then $\nabla f\left(x^{\ast }\right)=0$ (Taylor expension)
  For convex problem , above condition guarantees $x^{\ast }$ is global minimizer

Question : what about constrained optimization?

4.2 Lagrangian

Associated Lagrangian : $L:\mathcal{D}\times {\mathbb{R}}^m\times {\mathbb{R}}^q\to \mathbb{R}$
$$L\left(x,\lambda ,\nu \right)=f_0\left(x\right)+\sum _{i=1}^m{\lambda }_{\mathrm{i}}{f}_{\mathrm{i}}\left(x\right)+\sum _{j=1}^q{\nu }_{\mathrm{j}}{h}_{\mathrm{j}}\left(x\right),{\lambda }_{\mathrm{i}}⩾0,{\nu }_{\mathrm{j}}⩾0$$
weighted sum of objective and constraints functions
${\lambda }_{\mathrm{i}}$ : Lagrangian multiplier associated with $f_{\mathrm{i}}\left(x\right)⩽0$
${\nu }_{\mathrm{j}}$ : Lagrangian multiplier associated with $h_{\mathrm{j}}\left(x\right)=0$

4.2.1 Lagrangian Dual Problems

Lagrangian Dual Problems : $g:{\mathbb{R}}^m\times {\mathbb{R}}^q\to \mathbb{R}$
$$g\left(\lambda ,\nu \right)=\underset{x\in \mathcal{D}}{\inf }L\left(x,\lambda ,\nu \right)=\underset{x\in \mathcal{D}}{\inf }\left\{f_0\left(x\right)+\sum _{i=1}^m{\lambda }_{\mathrm{i}}{f}_{\mathrm{i}}\left(x\right)+\sum _{j=1}^q{\nu }_{\mathrm{j}}{h}_{\mathrm{j}}\left(x\right)\right\}$$

• $g$ is convex(always true - regardless fo whether the primal peoblem is convex or not) , can be $-\infty$ for some $\lambda ,\nu$
• Lower bound property : If $\lambda ⪰0$ (elementwise) , then $g\left(\lambda ,\nu \right)⩽p^{\ast }$
  Let $\tilde{x}$ be arbitrary feasible primal variable and $\lambda ⩾0$ , $f_0\left(\tilde{x}\right)⩾L\left(\tilde{x},\lambda ,\nu \right)⩾\underset{x\in \mathcal{D}}{\inf }L\left(x,\lambda ,\nu \right)=g\left(\lambda ,\nu \right)\Rightarrow \underset{\tilde{x}feasible}{\min }{f}_0\left(\tilde{x}\right)⩾g\left(\lambda ,\nu \right)$

Lagrangian Dual Problems :
maximize : $g\left(\lambda ,\nu \right)$
subject to : $\lambda ⪰0$
$\iff$ change convex optimization problem
min : $-g\left(\lambda ,\nu \right)$
subject to : $-\lambda ⪯0$

Fined the best lower bound on $p^{\ast }$ using the Lagrange dual function

Dual problem is a convex optimization problem even when the primal is nonconvex

optimal value denoted $d^{\ast }$

$\left(\lambda ,\nu \right)$ is called dual feasible if $\lambda ⪰0$ and $\left(\lambda ,\nu \right)\in dom\left(g\right)$

Often simplified by making the implicit constraint $\left(\lambda ,\nu \right)\in dom\left(g\right)$ explicit

例子-见 5

4.2.2 Duality Theorems

• Weak Duality : $d^{\ast }⩽p^{\ast }$
  always hold (for convex and nonconvex problems)
  can be used to find nontrivial lower bounds for difficult problems
• Strong Duality : $d^{\ast }=p^{\ast }$
  not true in general, but typically holds for convex problems
  conditions that guarantee strong duality in convex problems are called constriant qualifications
  Slater’s constraint qualification : Primal is strictly feasible

4.3 General Optimality Conditions

For general optimization problem:
minimize : $f_0\left(x\right)$
subject to : $f_{\mathrm{i}}\left(x\right)⩽0,i=1,\cdots ,m,h_{\mathrm{j}}\left(x\right)=0,j=1,\cdots ,q$

General Optimality Conditions : strong duality and $\left(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast }\right)$ is primal-dual optimal $\iff$

• $x^{\ast }=arg{\min }_{\mathrm{x}}L\left(x,{\lambda }^{\ast },{\nu }^{\ast }\right)$ —— Lagrange optimality
• ${\lambda }_{\mathrm{i}}^{\ast }{f}_{\mathrm{i}}\left(x\right)=0,\forall i$ —— Complementarity
• $f_{\mathrm{i}}\left(x^{\ast }\right)⩽0,h_{\mathrm{j}}\left(x^{\ast }\right)=0,\forall i,j$ —— primal feasibility
• ${\lambda }_{\mathrm{i}}^{\ast }⩾0,\forall i$ —— dual feasibility

Proof Necessity
Assume $x^{\ast }$ and $\left({\lambda }^{\ast },{\nu }^{\ast }\right)$ are primal-dual optimal slns with zero duality gap

$$f_0\left(x^{\ast }\right)=g\left({\lambda }^{\ast },{\nu }^{\ast }\right)=\underset{x\in \mathcal{D}}{\min }\left(f_0\left(x\right)+\sum _{i=1}^m{\lambda }_{\mathrm{i}}^{\ast }{f}_{\mathrm{i}}\left(x\right)+\sum _{j=1}^q{\nu }_{\mathrm{j}}^{\ast }{h}_{\mathrm{j}}\left(x\right)\right)⩽f_0\left(x^{\ast }\right)+\sum _{i=1}^m{\lambda }_{\mathrm{i}}^{\ast }{f}_{\mathrm{i}}\left(x^{\ast }\right)+\sum _{j=1}^q{\nu }_{\mathrm{j}}^{\ast }{h}_{\mathrm{j}}\left(x^{\ast }\right)⩽f_0\left(x^{\ast }\right)$$

Therefore, all inequalities are actually equalities

Replacing the first inequality with equality $\Rightarrow x^{\ast }=arg{\min }_{\mathrm{x}}L\left(x,{\lambda }^{\ast },{\nu }^{\ast }\right)$

Replacing the second inequality with equality $\Rightarrow$ complementarity condition

Proof of Sufficiency
Assume $\left(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast }\right)$ satisfies the optimality conditions :
$$g\left({\lambda }^{\ast },{\nu }^{\ast }\right)=f\left(x^{\ast }\right)+\sum _{i=1}^m{\lambda }_{\mathrm{i}}^{\ast }{f}_{\mathrm{i}}\left(x^{\ast }\right)+\sum _{j=1}^q{\nu }_{\mathrm{j}}^{\ast }{h}_{\mathrm{j}}\left(x^{\ast }\right)=f\left(x^{\ast }\right)$$

The first equality is by Lagrange optimality, and the 2nd equality is due to conplementarity

Therefore, the duality gap is zero, and $\left(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast }\right)$ is the primal dual optimal solution

4.4 KKT Conditions

For convex optimization problem:
minimize : $f_0\left(x\right)$
subject to : $f_{\mathrm{i}}\left(x\right)⩽0,i=1,\cdots ,m,h_{\mathrm{j}}\left(x\right)=0,j=1,\cdots ,q$

Suppose duality gap is zero , then $\left(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast }\right)$ is primal-dual optimal if and only if it satisfies the Karush-Kuhn-Tucker(KKT) conditions

• $\frac{\partial L}{\partial x}\left(x,{\lambda }^{\ast },{\nu }^{\ast }\right)=0$ —— Stationarity
• ${\lambda }_{\mathrm{i}}^{\ast }{f}_{\mathrm{i}}\left(x^{\ast }\right)=0,\forall i$ —— Complementarity
• $f_{\mathrm{i}}\left(x^{\ast }\right)⩽0,h_{\mathrm{j}}\left(x^{\ast }\right)=0,\forall i,j$ —— primal feasibility
• ${\lambda }_{\mathrm{i}}^{\ast }⩾0,\forall i$ —— dual feasibility

5. Linear Program

Primal Formulations
minimize : $c^{\mathrm{T}}x$
subject to : $Ax+b,x⩾0$

Lagrangian func : $L\left(x,\lambda ,\nu \right)=c^{\mathrm{T}}x+{\lambda }^{\mathrm{T}}\left(-x\right)+{\nu }^{\mathrm{T}}\left(Ax-b\right)$
$\Rightarrow g\left(\lambda ,\nu \right)=\underset{x\in {\mathbb{R}}^n}{\inf }\left\{\left(c^{\mathrm{T}}-{\lambda }^{\mathrm{T}}+{\nu }^{\mathrm{T}}A\right)x-{\nu }^{\mathrm{T}}b\right\}=\{\begin{array}{l}-\infty if{c}^{\mathrm{T}}-{\lambda }^{\mathrm{T}}+{\nu }^{\mathrm{T}}A\ne 0\\ -b^{\mathrm{T}}\nu if{c}^{\mathrm{T}}-{\lambda }^{\mathrm{T}}+{\nu }^{\mathrm{T}}A=0\end{array}$
$\Rightarrow \underset{\lambda ,\nu }{\max }g\left(\lambda ,\nu \right)$ , subject to : $\lambda ⩾0,c^{\mathrm{T}}-{\lambda }^{\mathrm{T}}+{\nu }^{\mathrm{T}}A=0$

Its Dual:
maximize : $-b^{\mathrm{T}}\nu$
subject to : $A^{\mathrm{T}}\nu +c⩾0$

• $n$ variables $q$ equality constraint $n$ inequalities $\Rightarrow$ $q$ variables $n$ inequalities constraint

6. Quadratic Program

Unconstrained Quadratic Program : Least Squares

minimize : $J\left(x\right)=\frac{1}{2}{x}^{\mathrm{T}}Qx+q^{\mathrm{T}}x+q_0$
Problem is convex iff $Q⪰0$
When $J$ is convex , it can be wrtitten as : $J\left(x\right)={\Vert Q^{\frac{1}{2}}x-y\Vert }^2+c$

KKT condition

Optimal solution