# KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey

arXiv: https://arxiv.org/abs/2110.01858 · HTML: https://mlsanity.com/paper/2110.01858/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 170 references that are in the map.
- First posted on arXiv 5 Oct 2021.

## Builds on (most cited first, 11 of 11)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nystr"om Method, and Use of Kernels in Machine Learning: Tutorial and Survey](https://mlsanity.com/paper/2106.08443/) (2021)
- [The Theory Behind Overfitting, Cross Validation, Regularization, Bagging, and Boosting: Tutorial](https://mlsanity.com/paper/1905.12787/) (2019)
- [Sampling Algorithms, from Survey Sampling to Monte Carlo Methods: Tutorial and Literature Review](https://mlsanity.com/paper/2011.00901/) (2020)
- [Porcupine Neural Networks: (Almost) All Local Optima are Global](https://mlsanity.com/paper/1710.02196/) (2017)
- [Distributed Convex Optimization with Many Convex Constraints](https://mlsanity.com/paper/1610.02967/) (2016)
- [SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums](https://mlsanity.com/paper/2106.10520/) (2021)
- [On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization](https://mlsanity.com/paper/2101.00236/) (2021)

## Built on by (most cited first, 16 of 16)

- [MAC-PO: Multi-Agent Experience Replay via Collective Priority Optimization](https://mlsanity.com/paper/2302.10418/) (2023)
- [GATE: Graph CCA for Temporal SElf-supervised Learning for Label-efficient fMRI Analysis](https://mlsanity.com/paper/2203.09034/) (2022)
- [Spectral, Probabilistic, and Deep Metric Learning: Tutorial and Survey](https://mlsanity.com/paper/2201.09267/) (2022)
- [Recurrent Neural Networks and Long Short-Term Memory Networks: Tutorial and Survey](https://mlsanity.com/paper/2304.11461/) (2023)
- [Latent Space Alignment for AI-Native MIMO Semantic Communications](https://mlsanity.com/paper/2507.16680/) (2025)
- [Generative Adversarial Networks and Adversarial Autoencoders: Tutorial and Survey](https://mlsanity.com/paper/2111.13282/) (2021)
- [Models and Mechanisms for Spatial Data Fairness](https://mlsanity.com/paper/2204.01880/) (2022)
- [ReMIX: Regret Minimization for Monotonic Value Function Factorization in Multiagent Reinforcement Learning](https://mlsanity.com/paper/2302.05593/) (2023)
- [Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.16600/) (2024)
- [Trust-Region Adaptive Policy Optimization](https://mlsanity.com/paper/2512.17636/) (2025)
- [On Philomatics and Psychomatics for Combining Philosophy and Psychology with Mathematics](https://mlsanity.com/paper/2308.13738/) (2023)
- [Sufficient Dimension Reduction for High-Dimensional Regression and Low-Dimensional Embedding: Tutorial and Survey](https://mlsanity.com/paper/2110.09620/) (2021)
- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)
- [Constrained Non-negative Matrix Factorization for Guided Topic Modeling of Minority Topics](https://mlsanity.com/paper/2505.16493/) (2025)
- [Foundations of Riemannian Geometry for Riemannian Optimization: A Monograph with Detailed Derivations](https://mlsanity.com/paper/2605.02279/) (2026)
- [SORA: Free Second-Order Attacks in Fast Adversarial Training](https://mlsanity.com/paper/2606.00738/) (2026)

## Abstract (arXiv)

This is a tutorial and survey paper on Karush-Kuhn-Tucker (KKT) conditions, first-order and second-order numerical optimization, and distributed optimization. After a brief review of history of optimization, we start with some preliminaries on properties of sets, norms, functions, and concepts of optimization. Then, we introduce the optimization problem, standard optimization problems (including linear programming, quadratic programming, and semidefinite programming), and convex problems. We also introduce some techniques such as eliminating inequality, equality, and set constraints, adding slack variables, and epigraph form. We introduce Lagrangian function, dual variables, KKT conditions (including primal feasibility, dual feasibility, weak and strong duality, complementary slackness, and stationarity condition), and solving optimization by method of Lagrange multipliers. Then, we cover first-order optimization including gradient descent, line-search, convergence of gradient methods, momentum, steepest descent, and backpropagation. Other first-order methods are explained, such as accelerated gradient method, stochastic gradient descent, mini-batch gradient descent, stochastic average gradient, stochastic variance reduced gradient, AdaGrad, RMSProp, and Adam optimizer, proximal methods (including proximal mapping, proximal point algorithm, and proximal gradient method), and constrained gradient methods (including projected gradient method, projection onto convex sets, and Frank-Wolfe method). We also cover non-smooth and ℓ1 optimization methods including lasso regularization, convex conjugate, Huber function, soft-thresholding, coordinate descent, and subgradient methods. Then, we explain second-order methods including Newton's method for unconstrained, equality constrained, and inequality constrained problems....