layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # Lecture 2c: Introduction to Convex Programming .pull-left[ @luk036 👨‍💻 · 2026 📅 ] .pull-right[  ] --- ## 📝 Abstract This lecture provides an introduction to the convex programming and covers various aspects of optimization. The lecture begins with an overview of optimization, including linear and nonlinear programming, duality and convexity, and approximation techniques. It then delves into more specific topics within continuous optimization, such as linear programming problems and their standard form, transformations to standard form, and the duality of linear programming problems. The lecture also touches on nonlinear programming, discussing the standard form of an NLPP (nonlinear programming problem) and the necessary conditions of optimality known as the Karush-Kuhn-Tucker (KKT) conditions. Convexity is another important concept explored in the document, with explanations on the definition of convex functions and their properties. The lecture also discusses the duality of convex optimization problems and their usefulness in computation. Finally, the document briefly mentions various unconstrained optimization techniques, descent methods, and approximation methods under constraints. --- ### Overview 📋 - Introduction - Linear programming - Nonlinear programming - Duality and Convexity - Approximation techniques - Convex Optimization - Books and online resources. --- ### 📊 Classification of Optimizations - Continuous - Linear vs Non-linear - Convex vs Non-convex - Discrete - Polynomial time Solvable - NP-hard - Approximatable - Non-approximatable - Mixed --- ### 🔄 Convex Optimization Process .mermaid[ <pre> graph TD A[Problem Formulation] --> B{Convex?} B -->|Yes| C[Apply Convex Solver] B -->|No| D[Convexify] D --> E[Change of Variables] D --> F[Relaxation] D --> G[Decomposition] E --> C F --> C G --> C C --> H[Optimal Solution] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#fff3e0,stroke:#e65100,stroke-width:3px style C fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px style E fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style F fill:#fff3e0,stroke:#e65100,stroke-width:3px style G fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style H fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- ### 🌊 Continuous Optimization  --- ### 📐 Linear Programming Problem - An LPP in standard form is: $$\min\{ {\color{coral}c}^\mathsf{T} {\color{green}x} \mid {\color{coral}A} {\color{green}x} = {\color{coral}b}, {\color{green}x} \ge 0\}.$$ - The ingredients of LPP are: - An ${\color{coral}m} \times {\color{coral}n}$ matrix ${\color{coral}A}$, with ${\color{coral}n} > {\color{coral}m}$ - A vector ${\color{coral}b} \in \mathbb{R}^{\color{coral}m}$ - A vector ${\color{coral}c} \in \mathbb{R}^{\color{coral}n}$ --- ### 📚 Example $$ \begin{array}{lll} \text{minimize} & 0.4 {\color{green}x_1} + 3.4 {\color{green}x_2} - 3.4 {\color{green}x_3} \\ \text{subject to} & 0.5 {\color{green}x_1} + 0.5 {\color{green}x_2} & = 3.5 \\ & 0.3 {\color{green}x_1} - 0.8 {\color{green}x_2} + 8.4 {\color{green}x_2} & = 4.5 \\ & {\color{green}x_1}, {\color{green}x_2}, {\color{green}x_3} \ge 0 \end{array} $$ --- ### 🔧 Transformations to Standard Form - Theorem: Any LPP can be transformed into the standard form. - Variables not restricted in sign: - Decompose ${\color{green}x}$ to two new variables ${\color{green}x} = {\color{green}x_1} - {\color{green}x_2}, {\color{green}x_1}, {\color{green}x_2} \geq 0$ - Transforming inequalities into equalities: - By putting slack variable ${\color{firebrick}y} = {\color{coral}b} - {\color{coral}A} {\color{green}x} \geq 0$ - Set ${\color{green}x'} = ({\color{green}x}, {\color{firebrick}y}), {\color{coral}A'} = ({\color{coral}A}, 1)$ - Transforming a max into a min - max(expression) = min($-$expression); --- ### ☯ Duality of LPP - If the primal problem of the LPP: $\min\{ {\color{coral}c}^\mathsf{T} {\color{green}x} \mid {\color{coral}A} {\color{green}x} \ge {\color{coral}b}, {\color{green}x} \ge 0\}$. - Its dual is: $\max\{ {\color{firebrick}y}^\mathsf{T} {\color{coral}b} \mid {\color{coral}A}^\mathsf{T} {\color{firebrick}y} \leq {\color{coral}c}, {\color{firebrick}y} \ge 0\}$. - If the primal problem is: $\min\{ {\color{coral}c}^\mathsf{T} {\color{green}x} \mid {\color{coral}A} {\color{green}x} = {\color{coral}b}, {\color{green}x} \ge 0\}$. - Its dual is: $\max\{ {\color{firebrick}y}^\mathsf{T} {\color{coral}b} \mid {\color{coral}A}^\mathsf{T} {\color{firebrick}y} \leq {\color{coral}c}\}$. --- ### 🌀 Nonlinear Programming - The standard form of an NLPP is $$\min\{f({\color{green}x}) \mid g({\color{green}x}) \leq 0, h({\color{green}x})=0 \}.$$ - Necessary conditions of optimality, Karush- Kuhn-Tucker (KKT) conditions: - Gradient Condition: ∇f(x) + µ∇g(x) + λ∇h(x) = 0, where ∇f(x), ∇g(x), and ∇h(x) are the gradients of the objective function, inequality constraints, and equality constraints, respectively. This condition states that the sum of the directional derivatives of the objective function and the constraints must be zero at the optimal solution. - Complementary Slackness Condition: µg(x) = 0, where µ is a Lagrange multiplier associated with the inequality constraints. This condition implies that either the constraint is inactive (g(x) ≤ 0) or its corresponding Lagrange multiplier is zero. - Feasibility Condition: µ ≥ 0, g(x) ≤ 0, h(x) = 0. This condition ensures that the inequality and equality constraints are satisfied at the optimal solution. --- ### 🤔 What is the significance of the KKT conditions mentioned? The significance of the KKT conditions lies in their ability to provide necessary conditions for a solution to be optimal in nonlinear programming problems. By satisfying these conditions, a point can be determined as a possible optimal solution. Moreover, if the objective function is strictly convex, and the KKT conditions are satisfied, then the solution obtained is the unique optimal solution. In essence, the KKT conditions serve as a powerful mathematical tool for analyzing and solving optimization problems. --- ### 🧠 Convexity - A function $f$: ${\color{salmon}K} \subseteq \mathbb{R}^{\color{coral}n} \mapsto R$ is convex if ${\color{salmon}K}$ is a convex set and $f({\color{green}y}) \ge f({\color{green}x}) + \nabla f({\color{green}x}) ({\color{green}y} - {\color{green}x}), \; {\color{green}y},{\color{green}x} \in {\color{salmon}K}$. - **Theorem**: Assume that $f$ and $g$ are convex differentiable functions. If the pair $({\color{green}x}, {\color{coral}m})$ satisfies the KKT conditions above, ${\color{green}x}$ is an optimal solution of the problem. If in addition, $f$ is strictly convex, ${\color{green}x}$ is the only solution of the problem. #### (Local minimum = global minimum) --- ### ☯ Duality and Convexity - Dual is the NLPP: $$\max\{\theta({\color{firebrick}\mu}, {\color{firebrick}\lambda}) \mid {\color{firebrick}\mu} \geq 0\},$$ where $\theta({\color{firebrick}\mu}, {\color{firebrick}\lambda}) = \inf_{\color{green}x} [ f({\color{green}x}) + {\color{firebrick}\mu} g({\color{green}x}) + {\color{firebrick}\lambda} h({\color{green}x}) ]$ - Dual problem is always convex. - Useful for computing the lower/upper bound 🔽🔼. --- ### 💡 Applications - Statistics - Filter design - Power control - Machine learning - SVM classifier - logistic regression --- class: nord-light, middle, center ## Convexify the non-convex's --- ### 🔄 Change of curvature: square Transform: $$0.3 \leq {\color{red} \sqrt{x} } \leq 0.4$$ into: $$0.09 \leq {\color{green} x} \leq 0.16 \, .$$ 👉 Note that $\sqrt{\cdot}$ are **monotonic** **concave** functions in $(0, +\infty)$. Generalization: - Consider $|H({\color{coral}\omega})|^2$ (power) instead of $|H({\color{coral}\omega})|$ (magnitude). - square root -> Spectral factorization --- ### 🔄 Change of curvature: square Transform: $${\color{red} x^2 } + {\color{red} y^2 } \geq 0.16, \quad \text{(non-convex)}$$ into: $${\color{green} x'} + {\color{green} y'} \geq 0.16, \quad {\color{green} x'}, {\color{green} y'} \geq 0$$ Then: $${\color{red} x}_\text{opt} = \pm\sqrt{ {\color{green} x'}_\text{opt} }, \quad {\color{red} y}_\text{opt} = \pm\sqrt{ {\color{green} y'}_\text{opt} }.$$ --- ### 📐 Change of curvature: sine Transform: $${\color{red} \sin^2{x} } \leq 0.4, \quad 0 \leq {\color{red} x} \leq \pi/2$$ into: $${\color{green} y} \leq 0.4, \quad 0 \leq {\color{green} y} \leq 1$$ Then: $${\color{red} x}_\text{opt} = \sin^{-1}(\sqrt{ {\color{green} y}_\text{opt} }).$$ 👉 Note that $\sin(\cdot)$ are monotonic concave functions in $(0, \pi/2)$. --- ### 📉 Change of curvature: log Transform: $$\pi \leq {\color{red} x / y} \leq \phi$$ into: $$\pi' \leq {\color{green} x' - y'} \leq \phi'$$ where ${\color{green} z'} = \log({\color{red} z})$. Then: $${\color{red} z}_\text{opt} = \exp({\color{green} z'}_\text{opt}).$$ Generalization: - Geometric programming --- ### 🔁 Change of curvature: inverse Transform: $${\color{red} \log(x) + \frac{c}{x} } \leq 0.3, \; {\color{red} x} > 0$$ into: $${\color{green} -\log(y) + c \cdot y } \leq 0.3, \; {\color{green} y} > 0 \, .$$ Then: $${\color{red} x}_\text{opt} = {\color{green} y}^{-1}_\text{opt}.$$ 👉 Note that $\sqrt{\cdot}$, $\log(\cdot)$, and $(\cdot)^{-1}$ are monotonic functions. --- ### 🧮 Generalize to matrix inequalities Transform: $${\color{red} \log(\det X) + \text{Tr}(X^{-1} C)} \leq 0.3, \; {\color{red} X} \succ 0$$ into: $${\color{green} -\log(\det Y) + \text{Tr}(Y \cdot C)} \leq 0.3, \; {\color{green} Y} \succ 0$$ Then: $${\color{red} X}_\text{opt} = {\color{green} Y}^{-1}_\text{opt}.$$ --- ### 🔀 Change of variables Transform: $$({\color{coral}a} + {\color{coral}b} \cdot {\color{red} y}) {\color{green}x} \leq 0, \; {\color{green}x} > 0$$ into: $${\color{coral}a} \cdot {\color{green}x} + {\color{coral}b} \cdot {\color{green} z} \leq 0, \; {\color{green}x} > 0$$ where ${\color{green} z} = {\color{red} y} {\color{green}x}$. Then: $${\color{red} y}_\text{opt} = {\color{green} z}_\text{opt} {\color{green}x}^{-1}_\text{opt}$$ --- ### 🧮 Generalize to matrix inequalities Transform: $$({\color{coral}A} + {\color{coral}B} {\color{red} Y}) {\color{green}X} + {\color{green}X} ({\color{coral}A} + {\color{coral}B} {\color{red} Y})^T \prec 0, \; {\color{green}X} \succ 0$$ into: $${\color{coral}A} {\color{green}X} + {\color{green}X} {\color{coral}A}^T + {\color{coral}B} {\color{green} Z} + {\color{green} Z}^T {\color{coral}B}^T \prec 0, \; {\color{green}X} \succ 0$$ where ${\color{green} Z} = {\color{red} Y} {\color{green}X}$. Then: $${\color{red} Y}_\text{opt} = {\color{green} Z}_\text{opt} {\color{green}X}^{-1}_\text{opt}$$ --- ### 🛡️ Some operations that preserve convexity - $-f$ is concave if and only if $f$ is convex. - Nonnegative weighted sums: - if ${\color{coral}w}_1, \ldots, {\color{coral}w}_n \ge 0$ and $f_1, \ldots, f_n$ are all convex, then so is ${\color{coral}w}_1 f_1 + \cdots + {\color{coral}w}_n f_n.$ In particular, the sum of two convex functions is convex. - Composition: - If $f$ and $g$ are convex functions and $g$ is non-decreasing over a univariate domain, then $h({\color{green}x}) = g(f({\color{green}x}))$ is convex. As an example, if $f$ is convex, then so is $e^{f({\color{green}x})},$ because $e^{{\color{green}x}}$ is convex and monotonically increasing. - If $f$ is concave and $g$ is convex and non-increasing over a univariate domain, then $h({\color{green}x}) = g(f({\color{green}x}))$ is convex. - Convexity is invariant under affine maps. --- ### 💭 Other thoughts - Minimizing any quasi-convex function subject to convex constraints can easily be transformed into a convex programming. - Replace a non-convex constraint with a sufficient condition (such as its lower bound). Less optimal. - Relaxation + heuristic - Decomposition --- ### 🛠️ Unconstraint Techniques - Line search methods - Fixed or variable step size - Interpolation - Golden section method - Fibonacci's method - Gradient methods - Steepest descent - Quasi-Newton methods - Conjugate Gradient methods --- ### ⬇️ General Descent Method 1. **Input**: a starting point ${\color{green}x} \in$ dom $f$ 2. **Output**: ${\color{green}x}^*$ 3. **repeat** 1. Determine a descent direction ${\color{green}p}$. 2. Line search. Choose a step size ${\color{coral}\alpha} > 0$. 3. Update. ${\color{green}x} := {\color{green}x} + {\color{coral}\alpha} {\color{green}p}$ 4. **until** stopping criterion satisfied. --- ### 🧭 Some Common Descent Directions - Gradient descent: ${\color{green}p} = -\nabla f({\color{green}x})^\mathsf{T}$ - Steepest descent: - $\triangle {\color{green}x}_{nsd} = \argmin\{\nabla f({\color{green}x})^\mathsf{T} {\color{green}v} \mid \|{\color{green}v}\|=1 \}$ - $\triangle {\color{green}x}$ = $\|\nabla f({\color{green}x})\| \triangle {\color{green}x}_{nsd}$ (un-normalized) - Newton's method: - ${\color{green}p} = -\nabla^2 f({\color{green}x})^{-1} \nabla f({\color{green}x})$ - Conjugate gradient method: - ${\color{green}p}$ is "orthogonal" to all previous ${\color{green}p}$'s - Stochastic subgradient method: - ${\color{green}p}$ is calculated from a set of sample data (instead of using all data) - Network flow problems: - ${\color{green}p}$ is given by a "negative cycle" (or "negative cut"). --- ### ⚖️ Approximation Under Constraints - Penalization and barriers - Dual method - Interior Point method - Augmented Lagrangian method --- ## 📚 Books and Online Resources - Pablo Pedregal. Introduction to Optimization, Springer. 2003 (O224 P371) - Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Dec. 2002 - Mittlemann, H. D. and Spellucci, P. Decision Tree for Optimization Software, 2003 --- count: false class: nord-dark, middle, center .pull-left[ # Q&A️ 🎤 ] .pull-right[  ]