mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
hanzoskills.com/llms.txt now opens with the install line, the API reference index and the company index, so an agent that lands on any one of the three can find the rest. robots.txt claimed 537 documents while llms.txt counts 920. The number is gone from robots.txt; llms.txt derives it. public/ is regenerated from scripts/site.py, which it had fallen behind: the copy-prompt menu and agent bar were in the generator and not in the committed pages. tests/site.mjs passes against the result. Co-authored-by: Hanzo Dev <[email protected]>
866 lines
34 KiB
HTML
866 lines
34 KiB
HTML
<!doctype html>
|
|
<html lang="en"><head>
|
|
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
|
<title>math-optimization-algorithms</title>
|
|
<meta name="color-scheme" content="dark">
|
|
<style>
|
|
/* Committed to one visual world: a dark instrument panel. No light variant —
|
|
the dot field and the hairline rules only read on black, and a naive
|
|
inversion would wash both out. Every colour is painted explicitly so the page
|
|
never borrows a host background. */
|
|
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
|
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
|
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
|
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
|
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
|
|
|
|
:root{
|
|
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
|
|
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
|
|
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
|
|
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
|
|
--font-zen-pixel-square:'Zen Pixel Square',monospace;
|
|
--mono:var(--font-zen-mono);
|
|
--sans:var(--font-zen-sans);
|
|
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
|
|
--r:999px; --r-soft:14px;
|
|
}
|
|
*{box-sizing:border-box}
|
|
html{-webkit-text-size-adjust:100%}
|
|
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
|
|
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
|
|
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
|
|
|
|
/* The dot field. A halftone made of one repeating radial-gradient, faded out
|
|
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
|
|
/* No overflow clip here: the dot field is inset to the box already, and a clip
|
|
would cut off the copy-prompt menu. */
|
|
.hero{position:relative;border-bottom:1px solid var(--line)}
|
|
.hero::before{content:"";position:absolute;inset:0;
|
|
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
|
|
background-size:7px 7px;
|
|
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
|
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
|
pointer-events:none}
|
|
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
|
|
|
|
nav{border-bottom:1px solid var(--line)}
|
|
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
|
|
justify-content:space-between;align-items:center;gap:1rem}
|
|
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
|
|
text-transform:uppercase;color:var(--ink);text-decoration:none;
|
|
display:inline-flex;align-items:center;gap:.6rem}
|
|
.brand i{font-style:normal;color:var(--faint)}
|
|
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
|
|
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
|
|
text-transform:uppercase;color:var(--soft);text-decoration:none}
|
|
nav a.up:hover{color:var(--ink)}
|
|
|
|
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
|
|
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
|
|
h1 em{font-style:normal;color:var(--faint)}
|
|
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
|
|
|
|
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
|
|
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
|
|
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
|
|
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
|
|
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
|
|
line-height:1.2;font-weight:400}
|
|
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
|
|
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
|
|
.btn.solid:hover{background:#d8d8d4}
|
|
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
|
|
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
|
|
|
|
/* Copy-prompt selector. Each row copies the prompt for its own target. */
|
|
.copy{position:relative;display:inline-flex}
|
|
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
|
|
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
|
|
padding:.4rem;display:flex;flex-direction:column;
|
|
box-shadow:0 12px 32px rgba(0,0,0,.75)}
|
|
.menu[hidden]{display:none}
|
|
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
|
|
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
|
|
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
|
|
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
|
|
white-space:nowrap}
|
|
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
|
|
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
|
|
.mi:hover .mark{color:var(--ink)}
|
|
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
|
|
letter-spacing:.1em;text-transform:uppercase}
|
|
|
|
/* Works-with bar: one scrolling row, name and mark per agent. */
|
|
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
|
|
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
|
|
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
|
|
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
|
|
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
|
|
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
|
|
display:flex;align-items:center}
|
|
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
|
|
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
|
|
-webkit-overflow-scrolling:touch;
|
|
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
|
|
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
|
|
.bar::-webkit-scrollbar{display:none}
|
|
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
|
|
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
|
|
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
|
|
text-decoration:none;background:var(--ground)}
|
|
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
|
|
.agent .mark{width:.95rem;height:.95rem}
|
|
|
|
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
|
|
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
|
|
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
|
|
p{margin:0 0 1rem;max-width:70ch}
|
|
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
|
|
li{margin:.22rem 0}
|
|
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
|
|
text-decoration-color:var(--line-hi)}
|
|
a:hover{text-decoration-color:var(--ink)}
|
|
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
|
|
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
|
|
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
|
|
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
|
|
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
|
|
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
|
|
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
|
|
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
|
|
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
|
|
display:block;overflow-x:auto}
|
|
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
|
|
|
|
.curl{display:block;background:var(--panel);border:1px solid var(--line);
|
|
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
|
|
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
|
|
white-space:pre;line-height:1.9}
|
|
.curl b{color:var(--ink);font-weight:400}
|
|
.curl i{font-style:normal;color:var(--faint)}
|
|
|
|
/* index */
|
|
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
|
|
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
|
|
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
|
|
#q:focus{outline:none;border-color:var(--soft)}
|
|
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
|
|
text-transform:uppercase;margin:0 0 2rem}
|
|
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
|
|
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
|
|
padding-bottom:.45rem}
|
|
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
|
|
border-radius:var(--r-soft);text-decoration:none}
|
|
.row:hover{background:#0a0a0a}
|
|
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
|
|
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
|
|
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
|
|
color:var(--faint);font-size:.85rem}
|
|
footer a{color:var(--soft)}
|
|
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
|
|
margin:0 0 2rem;font-size:.85rem}
|
|
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
|
|
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
|
|
border-bottom:1px solid var(--line);padding-bottom:.4rem}
|
|
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
|
|
.fmap a:hover{text-decoration:underline}
|
|
.fmap div{color:var(--faint);line-height:1.5}
|
|
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
|
|
|
|
@media (max-width:640px){
|
|
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
|
|
.btns{gap:.5rem}
|
|
.btn{padding:.75rem 1.15rem;font-size:.68rem}
|
|
.copy,.copy .btn{width:100%;justify-content:center}
|
|
.menu{left:0;right:0;min-width:0}
|
|
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
|
|
.strip b{border-right:0;padding-right:0}
|
|
.bar{width:100%}
|
|
}
|
|
</style>
|
|
<link rel="alternate" type="text/markdown" href="/math-optimization-algorithms.md">
|
|
|
|
<link rel="icon" href="/favicon.svg">
|
|
<link rel="canonical" href="https://hanzoskills.com/math-optimization-algorithms">
|
|
</head>
|
|
<!-- Reading this with a machine? Every page here is also plain markdown.
|
|
This one: https://hanzoskills.com/math-optimization-algorithms.md
|
|
Index: https://hanzoskills.com/llms.txt
|
|
Corpus: https://hanzoskills.com/all.md
|
|
Append .md to any path for the markdown twin. -->
|
|
<body>
|
|
<nav><div class="in">
|
|
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
|
|
<a class="up" href="/">All skills</a>
|
|
</div></nav>
|
|
|
|
<div class="wrap">
|
|
<h1>math-optimization-algorithms</h1><p class="lede">Machine learning model training (gradient descent, Adam, SGD)</p><h1>Optimization Algorithms</h1>
|
|
<h2>Metadata</h2>
|
|
<ul><li><strong>Skill ID</strong>: optimization-algorithms</li><li><strong>Category</strong>: Mathematics/Optimization</li><li><strong>Complexity</strong>: Advanced</li><li><strong>Last Updated</strong>: 2025-10-18</li></ul>
|
|
<h2>Overview</h2>
|
|
<p>Numerical optimization algorithms for unconstrained and constrained problems using SciPy and custom implementations. Covers gradient descent variants, Newton methods, convex optimization, and operations research applications.</p>
|
|
<h2>When to Use This Skill</h2>
|
|
<ul><li>Machine learning model training (gradient descent, Adam, SGD)</li><li>Parameter tuning and hyperparameter optimization</li><li>Resource allocation and operations research</li><li>Curve fitting and nonlinear regression</li><li>Constrained optimization (linear/quadratic programming)</li><li>Portfolio optimization and economics</li><li>Engineering design optimization</li></ul>
|
|
<h2>When NOT to Use This Skill</h2>
|
|
<ul><li>Symbolic optimization (use SymPy)</li><li>Discrete/combinatorial optimization (use OR-Tools, Gurobi)</li><li>Multi-objective optimization without scalarization</li><li>Global optimization of highly non-convex functions (use evolutionary algorithms)</li><li>When analytical solution exists</li></ul>
|
|
<h2>Prerequisites</h2>
|
|
<ul><li>Linear algebra basics</li><li>Calculus (derivatives, gradients)</li><li>NumPy array operations</li><li>Understanding of convexity concepts</li></ul>
|
|
<h2>Core Concepts</h2>
|
|
<h3>1. Unconstrained Optimization Basics</h3>
|
|
<p><strong>Gradient Descent Framework</strong></p>
|
|
<pre><code class="lang-python">import numpy as np
|
|
from numpy.linalg import norm
|
|
|
|
def gradient_descent(f, grad_f, x0, lr=0.01, max_iter=1000, tol=1e-6):
|
|
"""
|
|
Minimize f(x) using gradient descent.
|
|
|
|
Args:
|
|
f: Objective function
|
|
grad_f: Gradient of f
|
|
x0: Initial point
|
|
lr: Learning rate
|
|
max_iter: Maximum iterations
|
|
tol: Convergence tolerance
|
|
"""
|
|
x = x0.copy()
|
|
history = {'x': [x.copy()], 'f': [f(x)]}
|
|
|
|
for i in range(max_iter):
|
|
grad = grad_f(x)
|
|
x_new = x - lr * grad
|
|
|
|
# Check convergence
|
|
if norm(x_new - x) < tol:
|
|
print(f"Converged in {i+1} iterations")
|
|
break
|
|
|
|
x = x_new
|
|
history['x'].append(x.copy())
|
|
history['f'].append(f(x))
|
|
|
|
return x, history
|
|
|
|
# Example: Minimize f(x) = x^T A x - b^T x (quadratic)
|
|
n = 10
|
|
A = np.random.rand(n, n)
|
|
A = A @ A.T + np.eye(n) # Make positive definite
|
|
b = np.random.rand(n)
|
|
|
|
def f(x):
|
|
return 0.5 * x @ A @ x - b @ x
|
|
|
|
def grad_f(x):
|
|
return A @ x - b
|
|
|
|
x0 = np.random.rand(n)
|
|
x_opt, history = gradient_descent(f, grad_f, x0, lr=0.01)
|
|
|
|
# Analytical solution: A x = b
|
|
x_exact = np.linalg.solve(A, b)
|
|
print(f"Error: {norm(x_opt - x_exact):.2e}")</code></pre>
|
|
<p><strong>Momentum and Acceleration</strong></p>
|
|
<pre><code class="lang-python">def momentum_gd(f, grad_f, x0, lr=0.01, momentum=0.9, max_iter=1000, tol=1e-6):
|
|
"""Gradient descent with momentum (Polyak, 1964)"""
|
|
x = x0.copy()
|
|
v = np.zeros_like(x) # Velocity
|
|
|
|
for i in range(max_iter):
|
|
grad = grad_f(x)
|
|
v = momentum * v - lr * grad
|
|
x_new = x + v
|
|
|
|
if norm(x_new - x) < tol:
|
|
break
|
|
|
|
x = x_new
|
|
|
|
return x
|
|
|
|
def nesterov_gd(f, grad_f, x0, lr=0.01, momentum=0.9, max_iter=1000, tol=1e-6):
|
|
"""Nesterov accelerated gradient (NAG)"""
|
|
x = x0.copy()
|
|
v = np.zeros_like(x)
|
|
|
|
for i in range(max_iter):
|
|
# Look ahead
|
|
x_ahead = x + momentum * v
|
|
grad = grad_f(x_ahead)
|
|
|
|
v = momentum * v - lr * grad
|
|
x_new = x + v
|
|
|
|
if norm(x_new - x) < tol:
|
|
break
|
|
|
|
x = x_new
|
|
|
|
return x</code></pre>
|
|
<h3>2. Adaptive Learning Rate Methods</h3>
|
|
<p><strong>Adam Optimizer</strong></p>
|
|
<pre><code class="lang-python">def adam(f, grad_f, x0, lr=0.001, beta1=0.9, beta2=0.999,
|
|
eps=1e-8, max_iter=1000, tol=1e-6):
|
|
"""
|
|
Adam: Adaptive Moment Estimation (Kingma & Ba, 2015)
|
|
Most popular optimizer for deep learning.
|
|
"""
|
|
x = x0.copy()
|
|
m = np.zeros_like(x) # First moment (mean)
|
|
v = np.zeros_like(x) # Second moment (variance)
|
|
|
|
for t in range(1, max_iter + 1):
|
|
grad = grad_f(x)
|
|
|
|
# Update biased first moment estimate
|
|
m = beta1 * m + (1 - beta1) * grad
|
|
|
|
# Update biased second moment estimate
|
|
v = beta2 * v + (1 - beta2) * (grad ** 2)
|
|
|
|
# Bias correction
|
|
m_hat = m / (1 - beta1 ** t)
|
|
v_hat = v / (1 - beta2 ** t)
|
|
|
|
# Update parameters
|
|
x_new = x - lr * m_hat / (np.sqrt(v_hat) + eps)
|
|
|
|
if norm(x_new - x) < tol:
|
|
break
|
|
|
|
x = x_new
|
|
|
|
return x
|
|
|
|
def rmsprop(f, grad_f, x0, lr=0.01, decay=0.9, eps=1e-8,
|
|
max_iter=1000, tol=1e-6):
|
|
"""RMSprop: Root Mean Square Propagation (Hinton)"""
|
|
x = x0.copy()
|
|
cache = np.zeros_like(x)
|
|
|
|
for i in range(max_iter):
|
|
grad = grad_f(x)
|
|
|
|
# Accumulate squared gradient
|
|
cache = decay * cache + (1 - decay) * (grad ** 2)
|
|
|
|
# Update with normalized gradient
|
|
x_new = x - lr * grad / (np.sqrt(cache) + eps)
|
|
|
|
if norm(x_new - x) < tol:
|
|
break
|
|
|
|
x = x_new
|
|
|
|
return x
|
|
|
|
def adagrad(f, grad_f, x0, lr=0.01, eps=1e-8, max_iter=1000, tol=1e-6):
|
|
"""AdaGrad: Adaptive Gradient (Duchi et al., 2011)"""
|
|
x = x0.copy()
|
|
cache = np.zeros_like(x)
|
|
|
|
for i in range(max_iter):
|
|
grad = grad_f(x)
|
|
|
|
# Accumulate all squared gradients
|
|
cache += grad ** 2
|
|
|
|
# Adaptive learning rate per parameter
|
|
x_new = x - lr * grad / (np.sqrt(cache) + eps)
|
|
|
|
if norm(x_new - x) < tol:
|
|
break
|
|
|
|
x = x_new
|
|
|
|
return x</code></pre>
|
|
<h3>3. Newton and Quasi-Newton Methods</h3>
|
|
<p><strong>Newton's Method</strong></p>
|
|
<pre><code class="lang-python">def newton_method(f, grad_f, hess_f, x0, max_iter=100, tol=1e-6):
|
|
"""
|
|
Newton's method: uses second-order information (Hessian).
|
|
Quadratic convergence near minimum.
|
|
"""
|
|
x = x0.copy()
|
|
|
|
for i in range(max_iter):
|
|
grad = grad_f(x)
|
|
hess = hess_f(x)
|
|
|
|
# Solve H * delta = -grad
|
|
delta = np.linalg.solve(hess, -grad)
|
|
x_new = x + delta
|
|
|
|
if norm(delta) < tol:
|
|
print(f"Converged in {i+1} iterations")
|
|
break
|
|
|
|
x = x_new
|
|
|
|
return x
|
|
|
|
# Example: Rosenbrock function
|
|
def rosenbrock(x):
|
|
return 100 * (x[1] - x[0]**2)**2 + (1 - x[0])**2
|
|
|
|
def rosenbrock_grad(x):
|
|
return np.array([
|
|
-400 * x[0] * (x[1] - x[0]**2) - 2 * (1 - x[0]),
|
|
200 * (x[1] - x[0]**2)
|
|
])
|
|
|
|
def rosenbrock_hess(x):
|
|
return np.array([
|
|
[1200 * x[0]**2 - 400 * x[1] + 2, -400 * x[0]],
|
|
[-400 * x[0], 200]
|
|
])
|
|
|
|
x0 = np.array([0.0, 0.0])
|
|
x_opt = newton_method(rosenbrock, rosenbrock_grad, rosenbrock_hess, x0)
|
|
print(f"Optimum: {x_opt}, f(x*) = {rosenbrock(x_opt):.2e}")</code></pre>
|
|
<p><strong>BFGS (Quasi-Newton)</strong></p>
|
|
<pre><code class="lang-python">def bfgs(f, grad_f, x0, max_iter=100, tol=1e-6):
|
|
"""
|
|
BFGS: Broyden-Fletcher-Goldfarb-Shanno algorithm.
|
|
Approximates Hessian inverse using gradient information only.
|
|
"""
|
|
x = x0.copy()
|
|
n = len(x)
|
|
H = np.eye(n) # Initial Hessian inverse approximation
|
|
|
|
grad = grad_f(x)
|
|
|
|
for i in range(max_iter):
|
|
# Search direction
|
|
p = -H @ grad
|
|
|
|
# Line search (simplified backtracking)
|
|
alpha = 1.0
|
|
while f(x + alpha * p) > f(x) + 1e-4 * alpha * grad @ p:
|
|
alpha *= 0.5
|
|
if alpha < 1e-10:
|
|
break
|
|
|
|
# Update
|
|
x_new = x + alpha * p
|
|
grad_new = grad_f(x_new)
|
|
|
|
# Check convergence
|
|
if norm(grad_new) < tol:
|
|
print(f"Converged in {i+1} iterations")
|
|
break
|
|
|
|
# BFGS update of Hessian inverse
|
|
s = x_new - x
|
|
y = grad_new - grad
|
|
|
|
rho = 1.0 / (y @ s)
|
|
if rho > 0: # Ensure positive definiteness
|
|
I = np.eye(n)
|
|
H = (I - rho * np.outer(s, y)) @ H @ (I - rho * np.outer(y, s)) + rho * np.outer(s, s)
|
|
|
|
x = x_new
|
|
grad = grad_new
|
|
|
|
return x
|
|
|
|
# Compare with SciPy implementation
|
|
from scipy.optimize import minimize
|
|
|
|
result = minimize(rosenbrock, x0, method='BFGS', jac=rosenbrock_grad)
|
|
print(f"SciPy BFGS: {result.x}, f(x*) = {result.fun:.2e}")</code></pre>
|
|
<p><strong>L-BFGS (Limited-Memory BFGS)</strong></p>
|
|
<pre><code class="lang-python">from scipy.optimize import minimize
|
|
|
|
# L-BFGS: More efficient for high-dimensional problems
|
|
# Only stores a few vectors instead of full Hessian approximation
|
|
|
|
def high_dim_function(x):
|
|
# Example: L2 regularized logistic regression
|
|
# Assume X, y are data matrices/vectors
|
|
pass
|
|
|
|
result = minimize(
|
|
rosenbrock,
|
|
x0,
|
|
method='L-BFGS-B', # Bounded L-BFGS
|
|
jac=rosenbrock_grad,
|
|
bounds=[(-2, 2), (-2, 2)] # Box constraints
|
|
)</code></pre>
|
|
<h3>4. Constrained Optimization</h3>
|
|
<p><strong>Linear Programming</strong></p>
|
|
<pre><code class="lang-python">from scipy.optimize import linprog
|
|
|
|
# Minimize c^T x subject to:
|
|
# A_ub @ x <= b_ub (inequality constraints)
|
|
# A_eq @ x == b_eq (equality constraints)
|
|
# bounds on x
|
|
|
|
# Example: Diet problem
|
|
# Minimize cost: 2*x1 + 3*x2 (x1=bread, x2=milk)
|
|
c = np.array([2, 3])
|
|
|
|
# Constraints: at least 10 units protein, 8 units vitamins
|
|
# x1 + 2*x2 >= 10 => -x1 - 2*x2 <= -10
|
|
# 2*x1 + x2 >= 8 => -2*x1 - x2 <= -8
|
|
A_ub = np.array([[-1, -2], [-2, -1]])
|
|
b_ub = np.array([-10, -8])
|
|
|
|
# Non-negativity
|
|
bounds = [(0, None), (0, None)]
|
|
|
|
result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')
|
|
print(f"Optimal solution: {result.x}")
|
|
print(f"Minimum cost: {result.fun:.2f}")</code></pre>
|
|
<p><strong>Quadratic Programming</strong></p>
|
|
<pre><code class="lang-python">from scipy.optimize import minimize
|
|
|
|
# Minimize 0.5 x^T H x + f^T x subject to constraints
|
|
|
|
# Example: Portfolio optimization
|
|
# Minimize variance: 0.5 x^T Sigma x
|
|
# Subject to: sum(x) = 1 (fully invested)
|
|
# mu^T x >= target_return (return constraint)
|
|
# x >= 0 (long only)
|
|
|
|
n_assets = 5
|
|
np.random.seed(42)
|
|
|
|
# Covariance matrix (risk)
|
|
Sigma = np.random.rand(n_assets, n_assets)
|
|
Sigma = Sigma @ Sigma.T # Ensure positive semi-definite
|
|
|
|
# Expected returns
|
|
mu = np.random.rand(n_assets) * 0.1 + 0.05
|
|
target_return = 0.08
|
|
|
|
def portfolio_variance(x):
|
|
return 0.5 * x @ Sigma @ x
|
|
|
|
def portfolio_variance_grad(x):
|
|
return Sigma @ x
|
|
|
|
# Constraints
|
|
constraints = [
|
|
{'type': 'eq', 'fun': lambda x: np.sum(x) - 1}, # Fully invested
|
|
{'type': 'ineq', 'fun': lambda x: mu @ x - target_return} # Return target
|
|
]
|
|
|
|
# Bounds: long only
|
|
bounds = [(0, 1) for _ in range(n_assets)]
|
|
|
|
x0 = np.ones(n_assets) / n_assets # Equal weight initial guess
|
|
|
|
result = minimize(
|
|
portfolio_variance,
|
|
x0,
|
|
method='SLSQP', # Sequential Least Squares Programming
|
|
jac=portfolio_variance_grad,
|
|
bounds=bounds,
|
|
constraints=constraints
|
|
)
|
|
|
|
print(f"Optimal portfolio: {result.x}")
|
|
print(f"Expected return: {mu @ result.x:.4f}")
|
|
print(f"Portfolio variance: {result.fun:.6f}")</code></pre>
|
|
<p><strong>Non-Linear Constrained Optimization</strong></p>
|
|
<pre><code class="lang-python">from scipy.optimize import minimize, NonlinearConstraint
|
|
|
|
# Example: Minimize Rosenbrock with circle constraint
|
|
# min f(x) s.t. x[0]^2 + x[1]^2 <= 1
|
|
|
|
def constraint_fun(x):
|
|
return 1 - (x[0]**2 + x[1]**2) # >= 0
|
|
|
|
def constraint_jac(x):
|
|
return np.array([-2*x[0], -2*x[1]])
|
|
|
|
# Method 1: Dictionary constraint
|
|
constraint = {'type': 'ineq', 'fun': constraint_fun, 'jac': constraint_jac}
|
|
|
|
result = minimize(
|
|
rosenbrock,
|
|
x0,
|
|
method='SLSQP',
|
|
jac=rosenbrock_grad,
|
|
constraints=constraint
|
|
)
|
|
|
|
# Method 2: NonlinearConstraint (more general)
|
|
nlc = NonlinearConstraint(
|
|
lambda x: x[0]**2 + x[1]**2, # Constraint function
|
|
-np.inf, # Lower bound
|
|
1, # Upper bound
|
|
jac=lambda x: np.array([2*x[0], 2*x[1]])
|
|
)
|
|
|
|
result2 = minimize(
|
|
rosenbrock,
|
|
x0,
|
|
method='trust-constr', # Interior point method
|
|
jac=rosenbrock_grad,
|
|
hess=rosenbrock_hess,
|
|
constraints=nlc
|
|
)</code></pre>
|
|
<h3>5. Special Optimization Problems</h3>
|
|
<p><strong>Least Squares (Levenberg-Marquardt)</strong></p>
|
|
<pre><code class="lang-python">from scipy.optimize import least_squares
|
|
|
|
# Nonlinear least squares: min sum_i r_i(x)^2
|
|
# where r(x) is residual vector
|
|
|
|
# Example: Curve fitting to exponential decay
|
|
t = np.linspace(0, 5, 50)
|
|
y_true = 3 * np.exp(-0.5 * t) + 0.1 * np.random.randn(50)
|
|
|
|
def residuals(params, t, y):
|
|
a, b = params
|
|
return y - a * np.exp(-b * t)
|
|
|
|
def jacobian(params, t, y):
|
|
a, b = params
|
|
J = np.zeros((len(t), 2))
|
|
J[:, 0] = -np.exp(-b * t)
|
|
J[:, 1] = a * t * np.exp(-b * t)
|
|
return J
|
|
|
|
params0 = [1.0, 0.1]
|
|
result = least_squares(
|
|
residuals,
|
|
params0,
|
|
args=(t, y_true),
|
|
jac=jacobian,
|
|
method='lm' # Levenberg-Marquardt
|
|
)
|
|
|
|
print(f"Fitted parameters: a={result.x[0]:.4f}, b={result.x[1]:.4f}")</code></pre>
|
|
<p><strong>Convex Optimization (CVXPY)</strong></p>
|
|
<pre><code class="lang-python">import cvxpy as cp
|
|
|
|
# Example: L1-regularized regression (Lasso)
|
|
# min ||Ax - b||_2^2 + lambda ||x||_1
|
|
|
|
n, m = 100, 50
|
|
np.random.seed(0)
|
|
A = np.random.randn(n, m)
|
|
x_true = np.random.randn(m)
|
|
x_true[m//2:] = 0 # Sparse
|
|
b = A @ x_true + 0.1 * np.random.randn(n)
|
|
|
|
x = cp.Variable(m)
|
|
lambda_reg = 0.1
|
|
|
|
objective = cp.Minimize(
|
|
cp.sum_squares(A @ x - b) + lambda_reg * cp.norm1(x)
|
|
)
|
|
|
|
problem = cp.Problem(objective)
|
|
problem.solve()
|
|
|
|
print(f"Optimal value: {problem.value:.4f}")
|
|
print(f"Non-zeros in solution: {np.sum(np.abs(x.value) > 1e-3)}")</code></pre>
|
|
<h2>Patterns and Best Practices</h2>
|
|
<h3>Pattern 1: Algorithm Selection</h3>
|
|
<pre><code class="lang-python">def select_optimizer(problem_type, dim, has_gradient, has_hessian, constrained):
|
|
"""
|
|
Guide for selecting optimization algorithm.
|
|
"""
|
|
if constrained:
|
|
if problem_type == 'linear':
|
|
return 'linprog (simplex or interior-point)'
|
|
elif problem_type == 'quadratic':
|
|
return 'minimize with SLSQP or trust-constr'
|
|
elif problem_type == 'convex':
|
|
return 'CVXPY or trust-constr'
|
|
else:
|
|
return 'SLSQP or trust-constr with constraints'
|
|
else:
|
|
if dim < 10:
|
|
if has_hessian:
|
|
return 'Newton method'
|
|
elif has_gradient:
|
|
return 'BFGS'
|
|
else:
|
|
return 'Nelder-Mead'
|
|
elif dim < 1000:
|
|
if has_gradient:
|
|
return 'L-BFGS-B'
|
|
else:
|
|
return 'Powell or CG'
|
|
else: # High dimensional
|
|
if has_gradient:
|
|
return 'Adam or L-BFGS-B'
|
|
else:
|
|
return 'L-BFGS-B (numerical gradients)'</code></pre>
|
|
<h3>Pattern 2: Hyperparameter Tuning</h3>
|
|
<pre><code class="lang-python">from scipy.optimize import differential_evolution
|
|
|
|
# Global optimization for hyperparameter search
|
|
def objective(params):
|
|
lr, momentum = params
|
|
# Train model with these hyperparameters
|
|
# Return validation loss
|
|
return validation_loss
|
|
|
|
bounds = [(1e-4, 1e-1), (0.5, 0.99)] # [lr, momentum]
|
|
|
|
result = differential_evolution(
|
|
objective,
|
|
bounds,
|
|
maxiter=100,
|
|
seed=42,
|
|
workers=-1 # Parallel evaluation
|
|
)
|
|
|
|
best_lr, best_momentum = result.x</code></pre>
|
|
<h3>Pattern 3: Multi-Start Optimization</h3>
|
|
<pre><code class="lang-python">def multi_start_optimization(f, grad_f, bounds, n_starts=10):
|
|
"""
|
|
Run optimization from multiple random starting points.
|
|
Helps escape local minima.
|
|
"""
|
|
best_x = None
|
|
best_f = np.inf
|
|
|
|
for i in range(n_starts):
|
|
# Random starting point
|
|
x0 = np.random.uniform(bounds[:, 0], bounds[:, 1])
|
|
|
|
result = minimize(f, x0, method='L-BFGS-B', jac=grad_f, bounds=bounds)
|
|
|
|
if result.fun < best_f:
|
|
best_f = result.fun
|
|
best_x = result.x
|
|
|
|
return best_x, best_f</code></pre>
|
|
<h3>Pattern 4: Convergence Monitoring</h3>
|
|
<pre><code class="lang-python">class OptimizationLogger:
|
|
def __init__(self):
|
|
self.history = {'x': [], 'f': [], 'grad_norm': []}
|
|
|
|
def __call__(self, xk):
|
|
"""Callback for scipy.optimize.minimize"""
|
|
self.history['x'].append(xk.copy())
|
|
self.history['f'].append(f(xk))
|
|
self.history['grad_norm'].append(norm(grad_f(xk)))
|
|
|
|
logger = OptimizationLogger()
|
|
result = minimize(f, x0, method='BFGS', jac=grad_f, callback=logger)
|
|
|
|
# Plot convergence
|
|
import matplotlib.pyplot as plt
|
|
plt.semilogy(logger.history['grad_norm'])
|
|
plt.xlabel('Iteration')
|
|
plt.ylabel('Gradient Norm')
|
|
plt.title('Convergence History')</code></pre>
|
|
<h2>Quick Reference</h2>
|
|
<h3>SciPy Optimize Methods</h3>
|
|
<pre><code class="lang-python"># Unconstrained:
|
|
# - 'BFGS': General-purpose, needs gradient
|
|
# - 'L-BFGS-B': High-dimensional, supports bounds
|
|
# - 'Newton-CG': Needs Hessian or Hessian-vector product
|
|
# - 'trust-ncg': Trust region, needs Hessian
|
|
# - 'Nelder-Mead': Derivative-free, slow but robust
|
|
|
|
# Constrained:
|
|
# - 'SLSQP': Sequential Least Squares, general constraints
|
|
# - 'trust-constr': Interior point, very general
|
|
# - 'COBYLA': Derivative-free, only inequality constraints
|
|
|
|
# Global:
|
|
# - differential_evolution: Genetic algorithm
|
|
# - dual_annealing: Simulated annealing
|
|
# - shgo: Simplicial homology
|
|
# - basinhopping: Random perturbations + local search</code></pre>
|
|
<h3>Learning Rate Selection</h3>
|
|
<pre><code class="lang-python"># Rule of thumb for gradient descent:
|
|
# lr = 1 / L where L is Lipschitz constant of gradient
|
|
# For quadratic f(x) = 0.5 x^T A x: L = largest eigenvalue of A
|
|
|
|
def estimate_lipschitz_lr(grad_f, x0, n_samples=10):
|
|
"""Estimate safe learning rate"""
|
|
grads = []
|
|
for _ in range(n_samples):
|
|
x = x0 + 0.1 * np.random.randn(len(x0))
|
|
grads.append(grad_f(x))
|
|
|
|
# Estimate Lipschitz constant
|
|
L = max([norm(g) for g in grads]) / 0.1
|
|
return 1.0 / L if L > 0 else 0.01</code></pre>
|
|
<h2>Anti-Patterns</h2>
|
|
<h3>Anti-Pattern 1: Wrong Learning Rate</h3>
|
|
<pre><code class="lang-python"># WRONG: Fixed learning rate without tuning
|
|
x_opt = gradient_descent(f, grad_f, x0, lr=0.01) # May diverge or be too slow
|
|
|
|
# RIGHT: Use line search or adaptive method
|
|
result = minimize(f, x0, method='BFGS', jac=grad_f)
|
|
# Or use Adam for non-convex problems</code></pre>
|
|
<h3>Anti-Pattern 2: Ignoring Constraints</h3>
|
|
<pre><code class="lang-python"># WRONG: Projecting after unconstrained optimization
|
|
x_opt = minimize(f, x0, method='BFGS').x
|
|
x_opt = np.clip(x_opt, 0, 1) # Approximate projection
|
|
|
|
# RIGHT: Use constrained optimizer
|
|
result = minimize(f, x0, method='L-BFGS-B', bounds=[(0, 1)] * len(x0))</code></pre>
|
|
<h3>Anti-Pattern 3: Poor Initialization</h3>
|
|
<pre><code class="lang-python"># WRONG: Starting from zero or random
|
|
x0 = np.zeros(n) # May be saddle point
|
|
|
|
# RIGHT: Use domain knowledge or multiple starts
|
|
x0 = compute_reasonable_initial_guess()
|
|
# Or use multi-start strategy</code></pre>
|
|
<h3>Anti-Pattern 4: Not Checking Convergence</h3>
|
|
<pre><code class="lang-python"># WRONG: Assuming optimization succeeded
|
|
result = minimize(f, x0, method='BFGS')
|
|
x_opt = result.x # May not have converged!
|
|
|
|
# RIGHT: Check result status
|
|
if not result.success:
|
|
print(f"Optimization failed: {result.message}")
|
|
print(f"Gradient norm: {norm(grad_f(result.x))}")</code></pre>
|
|
<h2>Troubleshooting</h2>
|
|
<h3>Issue: Slow Convergence</h3>
|
|
<pre><code class="lang-python"># Check gradient computation
|
|
from scipy.optimize import check_grad
|
|
err = check_grad(f, grad_f, x0)
|
|
if err > 1e-5:
|
|
print("Gradient implementation may be incorrect!")
|
|
|
|
# Try different method
|
|
result = minimize(f, x0, method='L-BFGS-B', jac=grad_f)</code></pre>
|
|
<h3>Issue: Divergence</h3>
|
|
<pre><code class="lang-python"># Reduce learning rate or add line search
|
|
# Check if problem is convex
|
|
# Verify gradient correctness
|
|
# Add regularization</code></pre>
|
|
<h3>Issue: Getting Stuck in Local Minimum</h3>
|
|
<pre><code class="lang-python"># Use global optimization
|
|
from scipy.optimize import basinhopping
|
|
|
|
minimizer_kwargs = {"method": "BFGS", "jac": grad_f}
|
|
result = basinhopping(f, x0, minimizer_kwargs=minimizer_kwargs, niter=100)</code></pre>
|
|
<h2>Related Skills</h2>
|
|
<ul><li><code>linear-algebra-computation.md</code> - Matrix operations for optimization</li><li><code>numerical-methods.md</code> - Numerical differentiation, integration</li><li><code>probability-statistics.md</code> - Stochastic optimization, Bayesian optimization</li></ul>
|
|
<h2>Learning Resources</h2>
|
|
<ul><li>SciPy Optimize: https://docs.scipy.org/doc/scipy/reference/optimize.html</li><li>CVXPY: https://www.cvxpy.org/</li><li>Numerical Optimization (Nocedal & Wright)</li><li>Convex Optimization (Boyd & Vandenberghe)</li></ul>
|
|
<footer>
|
|
<div class="fmap">
|
|
<div><b>Build</b>
|
|
<a href="https://hanzo.app">hanzo.app</a> app builder
|
|
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
|
|
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
|
|
<div><b>Run</b>
|
|
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
|
|
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
|
|
<div><b>Account</b>
|
|
<a href="https://hanzo.id">hanzo.id</a> sign in
|
|
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
|
|
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
|
|
<div><b>Company</b>
|
|
<a href="https://hanzo.ai">hanzo.ai</a> canonical
|
|
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
|
|
</div>
|
|
<div class="fend"><a href="/math-optimization-algorithms.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
|
</footer>
|
|
</div></body></html> |