---
id: wiki-2026-0508-optimization-algorithms
title: Optimization Algorithms
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [Numerical Optimization, Mathematical Programming]
duplicate_of: none
source_trust_level: A
confidence_score: 0.9
verification_status: applied
tags: [optimization, numerics, ml, operations-research]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: python
  framework: scipy/jax/cvxpy
---

# Optimization Algorithms

## 매 한 줄
> **"매 objective f(x) 의 minimum (또는 max) 을 찾는 numerical procedure"**. Newton 1690s gradient 발상에서 시작, 매 1947 Dantzig simplex (LP), 매 1986 backprop (Rumelhart) 으로 ML 에 폭발적 확산. 매 2026 의 landscape: convex (CVXPY/Mosek), nonconvex first-order (AdamW, Lion, Sophia), second-order approximations (Shampoo, K-FAC), black-box (BO, CMA-ES), discrete (MILP via Gurobi/HiGHS).

## 매 핵심

### 매 problem class
- **Convex** (LP, QP, SDP): 매 global optimum 보장. 매 CVXPY/Mosek/SCS.
- **Smooth nonconvex**: 매 deep learning loss. 매 first-order (SGD, Adam, Lion).
- **Nonsmooth**: 매 L1 (Lasso) — proximal methods.
- **Constrained**: KKT conditions, augmented Lagrangian, interior point, projected gradient.
- **Discrete**: ILP, combinatorial — branch-and-bound, MCTS.
- **Black-box (no gradient)**: BO, CMA-ES, Nelder-Mead.

### 매 method family
- **Zeroth-order**: Nelder-Mead, BO, CMA-ES, evolutionary.
- **First-order**: GD, momentum, Nesterov, Adam, AdamW, Lion, RMSProp.
- **Quasi-Newton**: BFGS, L-BFGS — Hessian approximation.
- **Second-order**: Newton, Gauss-Newton, Levenberg-Marquardt.
- **Approx 2nd-order for DL**: K-FAC, Shampoo, Sophia.
- **Trust region**: dogleg, Steihaug.
- **Interior point**: LP/QP/SDP barrier methods.

### 매 응용
1. Deep learning (AdamW, Lion, Shampoo).
2. Reinforcement learning (PPO step, natural gradient).
3. LP/MILP (logistics, scheduling — Gurobi).
4. Hyperparameter tuning (Optuna with TPE).
5. Robotics trajectory (CHOMP, MPC, iLQR).
6. RLHF policy optimization.

## 💻 패턴

### scipy.optimize basic
```python
from scipy.optimize import minimize
import numpy as np

f = lambda x: (x[0]-1)**2 + 100*(x[1]-x[0]**2)**2  # Rosenbrock
res = minimize(f, x0=[0, 0], method="L-BFGS-B")
print(res.x, res.fun)
```

### Convex via CVXPY
```python
import cvxpy as cp

x = cp.Variable(10)
A = np.random.randn(20, 10); b = np.random.randn(20)
obj = cp.Minimize(cp.sum_squares(A @ x - b) + 0.1 * cp.norm(x, 1))
prob = cp.Problem(obj)
prob.solve()  # Lasso
```

### PyTorch optimizer (AdamW)
```python
import torch

opt = torch.optim.AdamW(model.parameters(), lr=3e-4, weight_decay=0.01,
                        betas=(0.9, 0.95))
sched = torch.optim.lr_scheduler.CosineAnnealingLR(opt, T_max=10_000)

for step, (x, y) in enumerate(loader):
    opt.zero_grad()
    loss = criterion(model(x), y)
    loss.backward()
    torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)
    opt.step(); sched.step()
```

### Lion optimizer (2023, memory-efficient)
```python
class Lion(torch.optim.Optimizer):
    def __init__(self, params, lr=1e-4, betas=(0.9, 0.99), weight_decay=0.0):
        super().__init__(params, dict(lr=lr, betas=betas, weight_decay=weight_decay))

    @torch.no_grad()
    def step(self):
        for group in self.param_groups:
            for p in group["params"]:
                if p.grad is None: continue
                state = self.state[p]
                if "exp_avg" not in state: state["exp_avg"] = torch.zeros_like(p)
                m = state["exp_avg"]
                b1, b2 = group["betas"]
                update = (b1*m + (1-b1)*p.grad).sign_()
                p.mul_(1 - group["lr"] * group["weight_decay"]).add_(update, alpha=-group["lr"])
                m.mul_(b2).add_(p.grad, alpha=1-b2)
```

### Bayesian Optimization (Optuna TPE)
```python
import optuna

def objective(trial):
    lr = trial.suggest_float("lr", 1e-5, 1e-2, log=True)
    wd = trial.suggest_float("wd", 1e-6, 1e-1, log=True)
    return train_and_eval(lr, wd)

study = optuna.create_study(direction="minimize",
                            sampler=optuna.samplers.TPESampler(seed=42))
study.optimize(objective, n_trials=50)
```

### CMA-ES (black-box, robust)
```python
import cma

es = cma.CMAEvolutionStrategy(x0=[0]*10, sigma0=0.5,
                              inopts={"maxiter": 200, "verbose": -9})
es.optimize(lambda x: sum(xi**2 for xi in x))
print(es.result.xbest)
```

### MILP via HiGHS
```python
from scipy.optimize import linprog, milp, LinearConstraint, Bounds

# minimize cT x s.t. A_ub x <= b_ub, x integer in [0, 1]
c = [-1, -2, -3]  # minimize → negate to maximize 1+2+3
A = [[1, 1, 1]]; b = [2]
res = milp(c=c, constraints=LinearConstraint(A, ub=b),
           integrality=[1, 1, 1], bounds=Bounds(0, 1))
```

### Trust-region Newton (small dense)
```python
from scipy.optimize import minimize

res = minimize(f, x0, jac=grad, hess=hess, method="trust-ncg")
```

## 매 결정 기준
| 상황 | Algorithm |
|---|---|
| convex small/medium | CVXPY (auto solver) |
| LP/MILP industrial | Gurobi / HiGHS |
| smooth small (~100 params) | L-BFGS |
| deep learning | AdamW / Lion |
| HP tuning (cheap eval) | Random / Grid |
| HP tuning (expensive) | Optuna TPE / BoTorch |
| black-box noisy | CMA-ES |
| 2nd-order for transformers | Shampoo / Sophia |
| RL policy | PPO / TRPO (natural gradient) |

**기본값**: 매 ML training → AdamW; 매 cost-expensive HP → BO; 매 industrial LP/MILP → Gurobi.

## 🔗 Graph
- 부모: [[Operations-Research]]
- 변형: [[Combinatorial Optimization]]
- 응용: [[Deep Learning]] · [[Reinforcement Learning]]
- Adjacent: [[Gradient Descent]] · [[Adam]] · [[Bayesian Optimization]] · [[CMA-ES]]

## 🤖 LLM 활용
**언제**: 매 PEFT (LoRA) AdamW config, 매 RLHF PPO/DPO step, 매 hyperparameter search via Optuna.
**언제 X**: 매 closed-form solution 가능한 단순 LS — np.linalg.lstsq.

## ❌ 안티패턴
- **No grad clipping in deep learning**: 매 spike → NaN.
- **Adam without weight decay**: 매 use AdamW (decoupled).
- **Convex problem 인데 SGD**: 매 CVXPY/Mosek 가 정확하고 빠르다.
- **MILP 를 LP relaxation 으로 풀고 round**: 매 infeasibility / suboptimal.
- **Black-box BO 를 cheap function 에 사용**: 매 random search 가 빠름.
- **No restart in nonconvex**: 매 local min 갇힘. 매 multi-start.

## 🧪 검증 / 중복
- Verified (Boyd & Vandenberghe *Convex Optimization*; Nocedal & Wright *Numerical Optimization*; Lion Chen et al. 2023; Sophia 2023; Gurobi/HiGHS docs).
- 신뢰도 A.

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — Optimization Algorithms FULL with AdamW/Lion/CVXPY/Optuna/MILP patterns |
