# Chapter 19 notebook: Optimization: Scale, Search, and Certify

**Goal:** Choose a step and stopping test that match the optimization problem's assumptions.

**Start with:** Rules 19.2.1, 19.3.1, 19.3.3. Use a calculator or the optional Python lab. Programming is optional for the workbook; the Jupyter version requires a Python 3 kernel. All lab numbers are constructed practice inputs, not observed data.

**Source:** [Finished Chapter 19](../skills/math-thumb-optimization/references/chapter.md) from *Mathematical Rules of Thumb*. Numbered rules, classifications, and the decision path come from the book. The lab, exercises, answer key, and worksheet prompts are companion additions.

## 1. Frame your decision

Write a question in which an answer would change something you do. Gather: Objective and constraints; units and variable scales; smoothness and convexity evidence; derivative access; noise; required optimality certificate.

- My question and intended decision:
- Known inputs and units:
- Required accuracy or threshold:
- What I expect before calculating:
- What I still need to find out:

Use the lab as a worked starting point if you do not yet have your own problem. For notation or prerequisites, ask the chapter skill to explain only the concept blocking the next step.

## 2. Choose a route

- **Does the problem mix units or characteristic magnitudes?** Nondimensionalize variables and constraints, then transform derivatives, bounds, penalties, and reported sensitivities consistently.
- **Can the objective be evaluated safely?** Stabilize exponentials, logarithms, and reductions before diagnosing optimizer behavior.
- **Is the objective smooth and convex?** Use a reciprocal smoothness step or backtracking; use condition number to judge whether scaling, acceleration, or curvature is needed.
- **Are gradients noisy?** Identify the batch-variance and constant-step floor before tightening tolerances or declaring a bug.
- **Is second-order information available?** Globalize Newton with a line search or trust region; use L-BFGS when only a small vector history fits.
- **Is the landscape nonconvex?** Treat every local solve as one basin sample and escalate to global methods when a certificate matters.
- **Have derivatives been independently checked?** Sweep centered directional differences across several steps before trusting convergence behavior.
- **What does optimality mean here?** Use a duality gap for valid convex bounds, a projected mapping for closed convex sets, or full scaled KKT blocks for general constraints.
- **Is the diagnostic algorithm-specific?** Keep Newton decrement, ADMM balancing, and penalty continuation attached to their required method and assumptions.
- **Will a multiplier drive a decision?** Verify the active set, units, signs, regularity, and locality before interpreting it as marginal value.

**Chapter-specific stop check:** Keep convergence claims attached to convexity, smoothness, scaling, and method conditions. Use constraint-aware optimality residuals at boundaries.

## 3. Work the lab

Minimize f(x,y)=(x^2+10 × y^2)/2. Its Hessian is diag(1,10), so L=10 and a safe smooth-convex gradient step is 1/L=0.1. Start at (2,2). The first step gives (1.8,0), and later x values shrink by 0.9 per step. Verify objective decrease and report the remaining gradient norm rather than declaring success merely because a step was accepted.

Predict the sign and scale before running the code. Then change one input and explain why the result moves. The code checks the constructed example; it does not prove the rule for every possible input. Code assertions may describe the example's chosen regime, so inspect them before changing that regime.

```python
import math
point = [2.0, 2.0]
step_size = 0.1
def objective(v):
    return (v[0]**2+10*v[1]**2)/2
values = [objective(point)]
for iteration in range(20):
    gradient = [point[0], 10*point[1]]
    point = [v-step_size*g for v, g in zip(point, gradient)]
    values.append(objective(point))
print(f"After 20 steps: x={point[0]:.6f}, y={point[1]:.6f}, objective={values[-1]:.8f}")
print(f"Gradient norm: {math.hypot(point[0], 10*point[1]):.8f}")
assert all(after <= before+1e-14 for before, after in zip(values, values[1:]))
```

**My prediction, observed result, and explanation:**

_Record your work here._

## 4. Practise without the answers

### Exercise 1

For f(x)=x^2/2, check the derivative at x=3 with centered differences using h=0.001.

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

### Exercise 2

Minimize f(x)=(x+1)^2 subject to x>=0. Does the nonzero ordinary gradient at x=0 disprove optimality?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

### Exercise 3

Ten starts of a nonconvex solver reach the same answer. Is that a global certificate?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

**Coaching prompt:** “Use the Chapter 19 skill to help me with Exercise 2. Ask for my attempt, give one useful hint if I need it, and help me check the assumptions before showing the answer.”

## 5. Answer key and reasoning

Read this after attempting the exercises, or use it immediately if you prefer a complete walkthrough. An answer is complete only when its assumptions and stopping point are clear.

### Answer 1

[(3.001)^2/2-(2.999)^2/2]/0.002≈3. For this quadratic the centered formula is exact in real arithmetic; floating error remains.

### Answer 2

No. The constrained minimum is x=0; the gradient is 2. The projected-gradient mapping is zero because projection returns x=0 after a descent step outside the feasible set.

### Answer 3

No. They provide evidence about the sampled basins. A global claim requires a valid bound, exhaustive argument, or another suitable certificate.

## 6. Build the complete chapter toolkit

The new lab samples the chapter; the following checklist covers all 19 rules. Study one thematic group at a time. A large group can take several sessions.

- **Prepare the Landscape:** work with rules 19.1.1, 19.1.2, 19.1.3, 19.1.4, 19.1.5.
- **Choose a Search That Can Recover From Bad Steps:** work with rules 19.2.1, 19.2.2, 19.2.3, 19.2.4, 19.2.5, 19.2.6.
- **Verify the Derivatives and Certify the Stop:** work with rules 19.3.1, 19.3.2, 19.3.3, 19.3.4, 19.3.5, 19.3.6, 19.3.7, 19.3.8.

For each selected rule, read its equation, explanation, and worked use in the source. Reproduce that example; change one input; then change one assumption so the rule is no longer justified. Record the result and what check catches the failure. Historical examples remain labeled and qualified as in the source.

Read each complete numbered profile in the [chapter reference](../skills/math-thumb-optimization/references/chapter.md) before applying it. The cues below abbreviate the graph metadata; they are not complete conditions. Change the status only after doing the practice described below.

| Rule | Book role | First assumptions to inspect | Practice status |
|---|---|---|---|
| 19.1.1: Nondimensionalize optimization variables before tuning | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.1.2: Scale features before coordinate descent | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.1.3: Shift by the maximum in log-sum-exp and softmax | Workflow | finite nonempty input or defined edge convention;  floating point exponential | new |
| 19.1.4: Condition number predicts gradient-descent speed | Independent | well scaled objective;  reliable function evaluation | new |
| 19.1.5: Expect constant-step stochastic optimization to hit a noise floor | Independent | well scaled objective;  reliable function evaluation | new |
| 19.2.1: Start smooth convex gradient descent at step 1 over L | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.2.2: Use Armijo backtracking when the safe step is unknown | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.2.3: Damp Newton until the full step is trustworthy | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.2.4: Use the trust-region ratio to accept and resize steps | Specialized | meaningful local model;  positive predicted reduction | new |
| 19.2.5: Use L-BFGS when dense Hessian storage is impossible | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.2.6: Use multiple starts for nonconvex local optimization | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.3.1: Check gradients with directional differences, not every coordinate | Workflow | smooth objective;  reliable function evaluation | new |
| 19.3.2: Use the duality gap as a global convex certificate | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.3.3: Stop constrained gradient methods with a projected-gradient mapping | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.3.4: Scale every block of the KKT residual | Workflow | well scaled objective;  reliable function evaluation | new |
| 19.3.5: Use the Newton decrement as a convex stopping certificate | Specialized | well scaled objective;  reliable function evaluation | new |
| 19.3.6: Balance ADMM primal and dual residuals | Specialized | comparable residual scaling;  consistent dual rescaling | new |
| 19.3.7: Do not make penalty parameters enormous too early | Specialized | well scaled objective;  reliable function evaluation | new |
| 19.3.8: Read a Lagrange multiplier as marginal value | Workflow | optimal primal dual solution;  constraint qualification | new |

For a completed row, record: **rule number / my new input / mathematical claim type / verified assumptions / calculation / check / valid use / rejected use / next step**. “Practised” means you worked an example. “Demonstrated” means you can explain a valid use, transfer it, and reject a misuse without the answer key.

## 7. Apply it to your own problem

Return to your opening question. Choose the smallest rule set that can settle it. Use the book's independent/workflow/specialized classification separately from the claim type (exact, approximate, bound, diagnostic, or heuristic).

- Selected rule number(s) and reason:
- Assumptions that hold, fail, or remain uncertain:
- Substitution with units:
- Result and error, uncertainty, or bound:
- Independent check or limiting case:
- Decision this supports:
- Stop here, do a named next calculation, or gather missing information:

## 8. Transfer and continue

Useful nearby chapters: Chapter 7: linear algebra; Chapter 18: applied mathematics; Chapter 20: numerical methods. Bring the question, units, assumptions, result type, and uncertainty to the next chapter. Choose a bridge only when it supplies an operation you actually need.

**Completion check:** Explain this chapter's lab in your own words; solve one changed-input exercise; reject one invalid use; and produce a decision record for your own problem. If one check fails, revisit that part of the chapter rather than marking every rule complete.