Convex Optimization Notes

Importance of Separation:
- Convex optimization significantly reduces task complexity.
- Non-convex optimization may not guarantee finding the global minimum/maximum and often relies on heuristics.

Objective function: The function being optimized (e.g., cost function, loss function).
- Example: Presidential candidates allocating resources (money $X1$ , states $X2$ , advertisement methods) to maximize votes.
Minimization vs. Maximization:
- Principles apply to both minimization and maximization problems.
- Convex functions guarantee that any local minimum found is also the global minimum.

Definition: The secant line between any two points on the function lies above the graph of the function.
Mathematical Representation:
- For $t$ between 0 and 1:
 f(t\cdot x1 + (1-t) \cdot x2) <= t \cdot f(x1) + (1-t) \cdot f(x2)
Explanation:
- $x1$ and $x2$ are two points on the x-axis.
- $f(x1)$ and $f(x2)$ are the corresponding function values.
- The line connecting $f(x1)$ and $f(x2)$ is the secant line.

Condition: If the second derivative of a function is greater than or equal to zero for all $x$ , the function is convex.
Mathematical Representation:
- f''(x) >= 0 for all $x$
Example:
- $f(x) = x^2$ is convex because f''(x) = 2 > 0.

Epigraph: The area above the function's graph.
Convex Set: A set where the line segment between any two points in the set is entirely contained within the set.
* Example: Imagine a rubber band stretched over a shape/layer. A convex shape is formed if the rubber band lies entirely within the shape.
* Non-example: If a line segment goes outside of the shape, then the shape isn't a convex set.
Convex Function: If the epigraph of a function is a convex set, then the function is a convex function.

Condition: A function $f(x)$ is convex if and only if all eigenvalues of its Hessian matrix are non-negative real numbers for all $x$ .
Hessian Matrix:
- Matrix of second partial derivatives of a function.
H(f(x)) = \begin{bmatrix}
\frac{\partial^2 f}{\partial x1^2} & \frac{\partial^2 f}{\partial x1 \partial x2} & \cdots & \frac{\partial^2 f}{\partial x1 \partial xn} \ \frac{\partial^2 f}{\partial x2 \partial x1} & \frac{\partial^2 f}{\partial x2^2} & \cdots & \frac{\partial^2 f}{\partial x2 \partial xn} \
\vdots & \vdots & \ddots & \vdots \
\frac{\partial^2 f}{\partial xn \partial x1} & \frac{\partial^2 f}{\partial xn \partial x2} & \cdots & \frac{\partial^2 f}{\partial x_n^2}
\end{bmatrix}

Process:
1. Calculate the gradient (first derivative) of the function.
2. Find the root(s) of the gradient by setting it to zero.
3. Solve for $x$ to find the point(s) where the minimum occurs.
Example:
- Given: Some convex function (e.g. a parabola)
  $f(x) = x^2$
  $\frac{d}{dx} f(x) = 2x$
  $2x = 0$ implies that $x = 0$
- Substituting $x = 0$ into the original function gives the value of $0$ :
  $f(0) = 0^2 = 0$

Nature-inspired methods: Used when convexity cannot be proven.
- Examples: Bracketing and Downhill Simplex.

Objective: Find a root for function $g(x)$
Process:
1. Find two points $x1$ and $x2$ with opposite signs:
 $g(x1) < 0$ and g(x2) > 0
2. Iteratively narrow the bracket:
 - Find a new point $x3$ such that g(x3) < 0
 - Replace $x1$ with $x3$
 - Continue until convergence.
Convergence Conditions:
- Maximum number of iterations reached. OR
- Difference between values in consecutive iterations is sufficiently small.
Bisection Search:
- Select the midpoint between $x1$ and $x2$ as new point to test.

Objective: Find a minimum or maximum for a non-convex function.
Process: Requires 3 points, two edges and one point between then. The value of the point between them must be lower than the edges to have a bracket.

The golden ratio is approximately 1.618 to 1. It is nature's perfect proportion for bringing parts together in a greater whole. It is present in the golden rectangle, the golden spiral and star, in the ratio between the numbers in the Fibonacci sequence.