# Optimization Visualizer — User Manual Interactive 2D minimization visualizer. Open `newton.html` directly in a browser (no server required). --- ## Quick Start 1. Open `newton.html` in a browser. 2. Pick a **Preset** from the drop-down, or type your own `f(x, y)` expression. 3. Click **Plot** to render the heatmap and contours. 4. **Left-click** on the canvas to set a starting point — optimization begins immediately. 5. Click **Step →** for one iteration, or **Auto** to run until convergence. --- ## Canvas Controls | Action | Effect | |---|---| | Left-click | Set start point; all active methods restart from here | | Ctrl+click | Add a polygon vertex (constraint drawing mode) | | Release Ctrl (≥ 3 vertices) | Close the polygon and activate the constraint | | Right-click drag | Pan the view | | Scroll wheel | Zoom in / out, centred on cursor | | ESC | Clear the polygon | --- ## Function Input Type any expression in `f(x, y) =`. No `=` sign; just the right-hand side. **Operators:** `+ - * / ^ **` (both `^` and `**` mean exponentiation) **Constants:** `PI` `E` **Available functions:** | | | | | |---|---|---|---| | `sin` | `cos` | `tan` | `asin` | | `acos` | `atan` | `atan2` | `sinh` | | `cosh` | `tanh` | `exp` | `log` `ln` | | `log2` | `log10` | `sqrt` | `cbrt` | | `abs` | `sign` | `floor` | `ceil` | | `round` | `pow` | `hypot` | `min` `max` | **Examples:** ``` x*x + 2*y*y elliptic bowl 100*(y - x*x)^2 + (1-x)^2 Rosenbrock (x*x + y - 11)^2 + (x + y*y - 7)^2 Himmelblau sin(x)*cos(y) oscillatory ``` --- ## Panel Controls ### Function - **f(x, y) =** — expression field. - **Contour step** — spacing between contour lines. `auto` picks a sensible value from the function range. Type a positive number and press **Apply** or Enter to override. - **Preset** — fills the function and view range then fires Plot automatically. ### View Range - **x / y min–max** — the world-coordinate window to display. - **Plot** — (re)compiles the expression, recomputes the grid, resets contours and optimizer state. Must be clicked after changing the function or range. ### Method Four toggle buttons; at least one must stay active. | Button | Method | |---|---| | Newton | Newton's method with Hessian | | Grad. Desc. | Steepest gradient descent | | BFGS | Broyden-Fletcher-Goldfarb-Shanno | | SR1 | Symmetric Rank-1 quasi-Newton | Toggling a method on mid-run catches it up to the current step headlessly. ### Optimization - **α₀** — initial step size passed to the line search (default 1). Reduce if steps overshoot; increase if progress is too slow. - **‖∇f‖ <** — convergence threshold on the gradient norm (default 1e-6). Iteration stops when the gradient is smaller than this. - **Line search** — choose **Armijo** (backtracking only) or **Strong Wolfe** (two-condition bracket-and-zoom). Takes effect for all active methods immediately. - **Step →** — advance every active method by one iteration. - **Auto** — runs one step every 350 ms; changes to **Stop** while running. Halts automatically when all active methods converge or reach 300 steps. - **Clear** — removes the start point and all trajectories; leaves the plot intact. ### Constraint Draw a polygon on the canvas with Ctrl+click, then release Ctrl to close it. The optimizer minimizes a penalized objective that pushes iterates toward the polygon interior. - **Convex / Non-convex** — selects the constraint mode (see below). Switching mode clears any existing polygon. - **Penalty weight μ** — logarithmic slider from 1 to 10 000. Larger μ enforces the constraint more strictly but stiffens the landscape. Adjusting it immediately re-runs the optimizer from the current start point. - **Clear constraint** — removes the polygon and returns to the unconstrained objective. Also triggered by ESC. --- ## Mathematical Methods ### Gradient Descent **Direction:** `d = −∇f(x)` Steepest-descent direction. Simple and robust; convergence rate is linear (geometric), controlled by the condition number of the Hessian. Works well on well-conditioned problems; very slow on elongated or curved valleys (e.g. Rosenbrock). ### Newton's Method **Direction:** `d = −H(x)⁻¹ · ∇f(x)` Uses the full 2×2 Hessian to scale and rotate the gradient. Achieves quadratic convergence near a strict local minimum. If the Hessian is not positive definite (saddle point or indefinite region), the smallest eigenvalue is identified and the diagonal is shifted by `−λ_min + 1e-6` before inversion, ensuring a descent direction at the cost of accuracy. ### BFGS **Direction:** `d = −Hᵢ · ∇f(x)` Quasi-Newton method. Maintains a 2×2 positive-definite approximation `Hᵢ` to the inverse Hessian (initialized to the identity). After each step, the approximation is updated by the rank-2 formula: ``` Hᵢ₊₁ = (I − ρ s yᵀ) Hᵢ (I − ρ y sᵀ) + ρ s sᵀ ``` where `s = x_new − x`, `y = ∇f_new − ∇f`, `ρ = 1 / (sᵀy)`. The update is skipped when `sᵀy ≤ 1e-12` (no curvature information). BFGS achieves superlinear convergence on smooth strongly-convex problems and is generally the most reliable quasi-Newton variant. ### SR1 **Direction:** `d = −Hᵢ · ∇f(x)` Like BFGS but uses a symmetric rank-1 update: ``` Hᵢ₊₁ = Hᵢ + (s − Hᵢy)(s − Hᵢy)ᵀ / ((s − Hᵢy)ᵀ y) ``` SR1 can better capture indefinite curvature (useful near saddle points or non-convex objectives) but does **not** guarantee that `Hᵢ` stays positive definite. The update is skipped when the denominator is too small relative to the vector norms. --- ## Line Search Every method uses a line search to choose the step length `α` along its direction `d`. ### Armijo (backtracking) Starts at `α₀` and halves until the **sufficient-decrease** (Armijo) condition holds: ``` f(x + α d) ≤ f(x) + 1e-4 · α · ∇f(x)ᵀd ``` Up to 50 halvings. Fast per step but may choose small α. ### Strong Wolfe Finds α satisfying both sufficient decrease **and** a curvature condition: ``` f(x + α d) ≤ f(x) + 1e-4 · α · ∇f(x)ᵀd (sufficient decrease) |∇f(x + α d)ᵀd| ≤ 0.9 · |∇f(x)ᵀd| (curvature / Wolfe) ``` Implementation: bracketing phase (expands up to `16·α₀`), then bisection zoom (up to 25 iterations). Returns a step that satisfies both conditions or the best bracket midpoint. More function evaluations per step, but provides better step quality — especially important for BFGS/SR1 to ensure positive `sᵀy`. **Safety:** if the computed direction is not a descent direction (can happen with SR1), the search falls back to `−∇f`. The initial step is also capped to 40% of the view span. --- ## Constraints (Quadratic Penalty) The constraint is a polygon drawn on the canvas. The optimizer minimizes a penalized objective `f_pen` instead of `f` directly — this is the **exterior quadratic penalty** approach, not a hard constraint. ### Convex Polygon The polygon must be convex (all interior angles < 180°). Each edge defines a half-plane `gᵢ(x,y) = aᵢx + bᵢy + cᵢ` oriented so that `gᵢ > 0` means infeasible (outside). ``` f_pen(x, y) = f(x, y) + (μ/2) · Σᵢ max(0, gᵢ(x, y))² ``` A non-convex polygon is rejected (red warning); the polygon stays open. ### Non-Convex Polygon The polygon may have any simple (non-self-intersecting) shape. Inside/outside is determined by the **winding-number** test. For exterior points, the penalty is: ``` f_pen(x, y) = f(x, y) + (μ/2) · d(x, y)² ``` where `d` is the Euclidean distance to the nearest polygon edge. Interior points pay no penalty. A self-intersecting polygon is rejected (red warning); the polygon stays open. **Effect of μ:** small μ → soft constraint (iterates may leave the polygon); large μ → stiff landscape (harder to optimize, but tighter feasibility). If the optimizer wanders outside, raise μ. --- ## Iterations Panel The panel on the bottom-left shows each method's trajectory: - **Step number** — 0 = start point - **Point (x, y)** — current position - **f value** — objective at this point - **‖∇f‖** — gradient norm The active (most recently advanced) step is highlighted. The step count label on the canvas marks the last point of each trajectory. --- ## Limitations | Limitation | Detail | |---|---| | Numerical derivatives only | Gradient uses h = 1e-5; Hessian uses h = 1e-4 central differences. Accuracy drops for near-zero or very large function values, or functions with rapid oscillations. | | 300-step hard cap | Each method stops after 300 iterations regardless of convergence. | | Penalty ≠ hard constraint | Feasibility is approximate. Increase μ if the trajectory leaves the polygon. | | Convex mode: polygon must be convex | L-shapes, star shapes, etc. are rejected. Use Non-convex mode instead. | | Non-convex mode: polygon must be simple | Self-intersecting polygons (figure-8, etc.) are rejected. | | Hessian regularization | Newton's method may behave like gradient descent near saddle points or indefinite regions where eigenvalue shifting is large. | | SR1: no positive-definiteness guarantee | `Hᵢ` can become indefinite; the fall-back to `−∇f` prevents non-descent steps but resets quasi-Newton progress. | | Slow convergence on ill-conditioned functions | Rosenbrock (condition number ~2500 near the minimum) is pathological for gradient descent; Newton/BFGS/SR1 handle it much better. | | Saddle points | All methods may stall if started exactly on a saddle (gradient ≈ 0). Perturb the start point or increase α₀. | | View range | Maximum 1×10⁶ in each dimension (guard against degenerate grids). | | `file://` security | Browser CSP blocks `eval`; the expression parser is a custom recursive-descent parser — not all mathematical notation is supported (e.g., implicit multiplication `2x` must be written `2*x`). |