# Constrained Optimization Boyd. Chapter 10. [Slides](https://cseweb.ucsd.edu/classes/wi23/cse203B-a/slides/lec10_opteqa.pdf) ## Formulation $\begin{align*} \min f(x) \quad\text{s.t. } Ax-b \end{align*}$ where $f: \mathbb{R}^n \rightarrow \mathbb{R}_{}^{}$ is twice differentiable, $A\in \mathbb{R}_{p}^{n}, rank(A)=p,\;p\leq n$. Formulation 0 - Equality-to-inequality: $\begin{align*} \min f(x) \quad\text{s.t. }Ax \geq b,\; -Ax \geq b \end{align*}$ ### Formulation 1 - Algebraically eliminate equality constraint: $\begin{align*} \min f(x) \quad\text{s.t. }\\ z\in \mathbb{R}_{}^{^{n-p}}, \;Ax_0=b,\; rank(F)=n-p,\; AF =0 \end{align*}$ - Let $Ax_0=b, \text{null}A=F\in \mathbb{R}_{}^{n\times(n-p)}, AF=0$ - We can write $x=x_0+Fz,\;z\in \mathbb{R}_{}^{n-p}$, then $f(x)=f(x_0+Fz)$ - To min $f(x)=f(x_0+Fz)$, we need $\nabla_z f\left(x_0+F z\right)=\left.F^T \nabla f(x)\right|_{x=x_0+F z}=0$ - #note This is equivalent to $\nabla f(x)=-A^T v, \quad v \in R^p$. ### Formulation 2 - Lagrange dual function: $\begin{align*} \max _v g(v) & =\max _v \min _x f(x)+v^T A x-v^T b \\ & =\max _v\left[-v^T b+\min _x\left(f(x)+v^T A x\right)\right] \\ & =\max _v\left[-v^T b-\max _x\left(-v^T A x-f(x)\right)\right] \\ & =\max _v\left(-v^T b-f^*\left(-A^T v\right)\right) \end{align*}$ #exercise $\min f(x)=\frac{1}{2} x^T P x+q^T x+r \text { s.t. } A x=b, \quad P \in S_{++}^n$ $\begin{align*} \end{align*}$ ![[Pasted image 20230307134040.png|400]] ### Formulation 3 - KKT conditions $\begin{align*} \begin{cases} \nabla f(x)+A^Tv=0\\ Ax=b \end{cases} \end{align*}$ Nonsingularity: ## Newton's Method ## Infeasible Start Newton's Method ## Summary