[足式机器人]Part4 南科大高等机器人控制课 CH11 Bascis of Optimization

本文仅供学习使用
本文参考：
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?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$ —— $?{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,?x\in {\mathbb{R}}^n$

$A\in {\mathcal{S}}^n$ is called positive definite(PD) , denoted by $A?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]?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?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?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?0?T^{\mathrm{T}}AT?0$ and $A?0?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?B$
  $?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?tr\left(A^{\mathrm{T}}B\right)=0\\ tr\left(A^{\mathrm{T}}B\right)>0?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)?tr\left(AB\right)?0$

• For ant symmetric $A\in {\mathcal{S}}^n$ , ${\lambda }_{\min }\left(A\right)?\mu ?A?\mu E$ and ${\lambda }_{\max }\left(A\right)?\beta ?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(?\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?\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?a^{\mathrm{T}}\left(x?x_0\right)=0?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?f\left(x\right)?0,?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\}$ $?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?\alpha x_1+\left(1?\alpha \right)x_2\in S,?\alpha \in \left[0,1\right]?{\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?\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?\lambda A?0?\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]$ ($?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?{\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?{\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}?\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),?x_1,x_2\in \mathcal{D},?\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),?x_1\ne x_2\in \mathcal{D},?\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)+?f{\left(x\right)}^{\mathrm{T}}\left(z?x\right),?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
  $${?}^{2}f\left(x\right)?0$$
  (concave ${?}^{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 ${?}^{2}f\left(x\right)=\left[\begin{array}{ccc}\frac{{?}^{2}f}{?x_1?x_1}& \frac{{?}^{2}f}{?x_1?x_2}& ?\\ ?& \frac{{?}^{2}f}{?x_2?x_2}& ?\\ ?& ?& ?\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 $?$ $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 $?$ 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$ $?$ 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,?,m,h_{\mathrm{j}}\left(x\right)=0,j=1,?,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^{?}$

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^{?}$ is local minimizer then $?f\left(x^{?}\right)=0$ (Taylor expension)
  For convex problem , above condition guarantees $x^{?}$ 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^{?}$
  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)?\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$
$?$ change convex optimization problem
min : $?g\left(\lambda ,\nu \right)$
subject to : $?\lambda ?0$

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

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

optimal value denoted $d^{?}$

$\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^{?}?p^{?}$
  always hold (for convex and nonconvex problems)
  can be used to find nontrivial lower bounds for difficult problems
• Strong Duality : $d^{?}=p^{?}$
  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,?,m,h_{\mathrm{j}}\left(x\right)=0,j=1,?,q$

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

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

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

$$f_0\left(x^{?}\right)=g\left({\lambda }^{?},{\nu }^{?}\right)=\underset{x\in \mathcal{D}}{\min }\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)?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)?f_0\left(x^{?}\right)$$

Therefore, all inequalities are actually equalities

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

Replacing the second inequality with equality $?$ complementarity condition

Proof of Sufficiency
Assume $\left(x^{?},{\lambda }^{?},{\nu }^{?}\right)$ satisfies the optimality conditions :
$$g\left({\lambda }^{?},{\nu }^{?}\right)=f\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)=f\left(x^{?}\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^{?},{\lambda }^{?},{\nu }^{?}\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,?,m,h_{\mathrm{j}}\left(x\right)=0,j=1,?,q$

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

• $\frac{?L}{?x}\left(x,{\lambda }^{?},{\nu }^{?}\right)=0$ —— Stationarity
• ${\lambda }_{\mathrm{i}}^{?}{f}_{\mathrm{i}}\left(x^{?}\right)=0,?i$ —— Complementarity
• $f_{\mathrm{i}}\left(x^{?}\right)?0,h_{\mathrm{j}}\left(x^{?}\right)=0,?i,j$ —— primal feasibility
• ${\lambda }_{\mathrm{i}}^{?}?0,?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)$
$?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}$
$?\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 $?$ $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