# Optimization Problem
General optimization problem:
$minf_0(x)$: $x*$ is **optimal** if $f_0(x*) \le f_0(x)$ for all x satisfying the constraints
# Convex Sets and Convex Functions
## Convex Set
A set (C) is convex if all pairs of points $x_1, x_2 \in C$ and any $\theta \in [0,1]$ the point $\theta x_1 + (1 - \theta)x_2 \in C$
Every line segment joining two points inside the set remains entirely inside the set.
![[Screenshot 2026-08-26 at 11.31.04 AM.png|316]]
## Operations Preserving Convexity
$C' = {Ax+B|x \in C}$
$C'= {x|x \in C_1 \& x \in C_2}$
union do not preserve convexity
## Important Convex Sets
### Convex Hull
> [!info] Definition
> The **convex hull** of a set of points is the **smallest convex set** that contains all of the points.
>
> Equivalently, it is the set of **all convex combinations** of the given points.
Given points $x\_1\,x\_2\,\ldots\,x\_n$ their **convex hull** is $x=\theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n$ for $\theta_1 + \theta_2 + ... + \theta_n = 1, \theta_i \ge 0$
> [!tip]
> Imagine stretching a **rubber band** around all the points.
>
> When released, the rubber band encloses the **smallest convex region** containing every point.
>
> That enclosed region is the **convex hull**.
Examples:
- **2 points** → line segment
- **3 non-collinear points** → filled triangle
- **4 non-coplanar points** → filled tetrahedron
- **More points** → smallest convex polygon/polyhedron containing them
![[Screenshot 2026-08-26 at 11.43.07 AM.png|347]]
- ✅ The convex hull is always **convex**.
- ✅ It is the **smallest convex set** containing the original points.
- ✅ Every point in the convex hull is a **convex combination** of the given points.
- ❌ If the coefficients do **not** sum to 1, the combination is **not** necessarily in the convex hull.
- ❌ If some coefficients are **negative**, the point may lie outside the convex hull.
### Affine Combination
Given points $x\_1\,x\_2\,\ldots\,x\_n$, $x=\theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n$ , affine combination is a point, affine hull is a set of affine combination
Convex combination is stricter affine combination with all coefficients sum to 1 and convex hull is a set of convex combination
| Property | Affine Combination | Convex Combination |
|-----------|-------------------|--------------------|
| Coefficients sum to 1 | ✅ | ✅ |
| Coefficients must be nonnegative | ❌ | ✅ |
| May lie outside original points | ✅ | ❌ |
| Generates | Affine Hull | Convex Hull |
### Hyperplane
a flat surface that is one dimension lower than the surrounding space
${x|a_Tx = b}$ means $a_1x_1 + a_2 x_2 + ... + a_n x_n = b$ every points satisfying this equation lies exactly on the hyperplane
a is the normal vector, b is scalar constant, and x is any point on the hyperplane
Example: Consider $x+y=3$, This is a hyperplane. It is simply the line
```text
y
4 |
3 | /
2 | /
1 | /
0 |__/________ x
0 1 2 3
```
Every point on this line satisfies
### Halfspace
${x|a_Tx \le b}$
Hyperplane
```text
|
|
------|------
|
|
```
Halfspace
```text
██████|
██████|
██████|
------|------
|
|
```
### Conic Combination
> [!info] Definition
> A **conic combination** of a set of vectors is a linear combination where **all coefficients are nonnegative**.
>
> Unlike a convex combination, the coefficients **do not have to sum to 1**.
conic hull is a set of conic combination
| Type | Formula | Restrictions | Generated Set |
| ------------------ | ------------------- | ------------------------------------- | ----------------- |
| Linear Combination | $\sum \theta_i x_i$ | None | Vector space |
| Affine Combination | $\sum \theta_i x_i$ | $\sum\theta_i=1$ | Affine hull |
| Convex Combination | $\sum \theta_i x_i$ | $\sum\theta_i=1$ and $\theta_i \ge 0$ | Convex hull |
| Conic Combination | $\sum \theta_i x_i$ | $\theta_1 \ge 0$ | Conic hull (cone) |
### Ellipse
$(x - C)^T M (x-C) \le 1$, where M is positive semidefinite or $x| ||Ax - b||_2 \le 1$, A controls the stretching and rotation of the ellipse and b shifts its location, c is the center of the ellipse
Take any two points inside the ellipse. The straight line connecting them stays completely inside the ellipse.
![[Screenshot 2026-08-26 at 12.04.58 PM.png|317]]
### Polyhedron
intersection of half spaces and hyperplanes. $x: Ax \le b, Cx = d$ where A, C are matrices and b, d are vectors, $Ax \le b$ represents linear inequality constraints (half spaces) and $Cx=d$ represents linear equality constraints (hyperplanes)
triangle, square, rectangle, cube, pentagon are polyhedron, circle ellipse are not polyhedron because they are not linear
### Positive Semidefinite Cone
A symmetric matrix X is positive semidefinite if:
$z^TXz \ge 0$ for all vector z, which is an intersection of halfspaces
consider X = $\begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix}$
then we have $2z_1^2 + 3z_2^2 \ge 0$ so X is PSD
since X is positive, any positive scalar t $\ge 0$ is PSD
| Matrix | condition |
| --------------------- | ------------------------------- |
| positive semidefinite | $z^TXz \ge 0$ |
| positive definite | $z^TXz \ge 0 for \ all z \ne 0$ |
positive definite matrices are a subset of positive semidefinite matrices.
$X_1, X_2 \text{ is PSD}, \lambda \in [0,1], z^T(\lambda X_1 + (1-\lambda) X_2)z = \lambda z^T X_1 z + (1-\lambda)z^T X_2 z \ge 0$
### Norm Balls
a set of all points where distance from a center is less than or equal to a fixed radius. $x: ||x|| \le u$ where many different norms (different method to measure distance) could apply $||x||_2 = \sqrt{(x_1^2 + ... + x_d^2)}$, $||x||_p = (|x_1|^p + ... + |x_d|^p)^{\frac{1}{p}}$ for p $\ge$ 1, {$x: ||x_p|| \le u$} is convex, but not for p<1
Euclidean norm (L2 norm)
```text
*****
** **
* *
* ● *
* *
** **
*****
```
Manhattan norm (L1 norm)
```text
▲
/ \
/ \
\ /
\ /
▼
```
Infinity norm (maximum coordinate distance)
```text
+---------+
| |
| ● |
| |
+---------+
```
# Convex Functions
a function f is convex if every pair of points $x_1, x_2$ and any $\lambda \in [0,1]$, $f(\lambda x_1+(1-\lambda)x_2) \le \lambda f(x_1) + (1-\lambda) f(x_2)$
![[Screenshot 2026-08-26 at 12.50.51 PM.png|259]]
## common functions
- Linear $a^T x + b$
- Exponential $e^{a^T x}$
- Polynomial powers $x^p, p \ge 1$
- Negative entropy $x logx$
- p-norms for p $\ge 1, (|x_1|^p + ...+ |x_d|^p)^{\frac{1}{p}}$
- Spectral norm (maximum singular value of X)
- Log determinant $log det x$
- Log-Sum-Exp
## Operations Preserving Convexity
- Nonnegative Sum $f_1, f_2$ are convex, so is $a_1f_1(x)+a_2f2(x)$, $a_1, a_2 \ge 0$
- composition with linear f convex so is $g(x) = f(a^Tx+b)$
- pointwise max $g(x)=max{f_1(x),f_2(x)}$
- minimizing out a subset of variables $f(x,y) is a joint convex in x and y, $g(x) = min f(x,y)$ is convex
# Gradients
f is differentiable at a point x if the gradient $\nabla f(x) = (\frac{\partial f}{\partial x_1},...,\frac{\partial f}{\partial x_d})$ exists. f is differentiable if it is differentiable for all x, a convex function is differentiable almost everywhere
![[Screenshot 2026-08-26 at 1.02.12 PM.png|292]]
- Tangent plane always lies below the function.
- f is twice differentiable if $\nabla^2f(x)$ the Hessian exists for all x: $[\nabla^2f(x)]_{ij}=\frac{\partial^2f(x)}{\partial x_i\partial x_j} \ge 0$
- Hessian is always positive semidefinite
# Strict Convexity
f is strictly convex if:
$f(\lambda x_1 + (1-\lambda)x_2) < \lambda f(x_1) + (1-\lambda)f(x_2)$
for differentiable f, equivalent to $f(x_2)>f(x_1) + \nabla f(x_1)^T(x_2-x_1)$, if twice-differentiable, f strictly convex if $\partial ^2 f(x) >0$
# Strong Convexity
f is m-strongly convex (for m>0) if any of the following hold:
- $f(\lambda x_1 + (1-\lambda)x_2) \le \lambda f(x_1) + (1-\lambda)f(x_2) - \frac{1}{2}m\lambda (1-\lambda)||x_1-x_2||_2^2$
- $f(x_2) \ge f(x_1) + \nabla f(x_1)^T(x_2-x_1)+\frac{1}{2}||x_2-x_1||_2^2$
- equivalent hessian condition: $\partial ^2 f(x) \ge ml$
# Monotonicity
A differentiable function is convex iff:
$y(\nabla f(x) - \nabla f(y))^T(x-y) \ge 0$
I tis m-strongly convex if:
$y(\nabla f(x)-\nabla f(y))^T(x-y) \ge m||x-y||_2^2$
# Convex Programs
> [!info] Definition
> A **convex program** is an optimization problem where:
>
> - The objective function is **convex**
> - The feasible region is a **convex set**
Mathematically, $min f_o(x), x\in c$ is a convex program if $f_0$ is a convex function and $c$ is a convex set. x is the variable, $f_0$ is the objective function and $c$ is the constraint set
For general f, global optimality $\longrightarrow$ local optimality but reverse not true
For convex programs, global optimality $\longleftrightarrow$ local optimality, algorithms only need to look for locally optimal solutions
$
\begin{aligned}
\text{suppose y local opt, z global opt, and f(z)<f(y)} \\
f(w) = f(\lambda y + (1-\lambda)z) \le \lambda f(y) + (1-\lambda)f(z) < \lambda f(y)+(1-\lambda)f(y) = f(y)
\end{aligned}
$
**Standard form**: $min_x f_0(x)$ s.t $f_i(x) \le 0, i=1,...,m$ , $Ax = b$ is an intersection of many level sets and equalities
Level set $L_C = {x: f(x) \le c}$
$f(.)$ is a convex function $\longrightarrow$ any level set $L_C = {x: f(x) \le c}$ is a convex set
e.g.
$
f(x1,x2) = x_1^2 + x_2^2, {x:x_1^2+x_2^2<=2} \text{ is convex f convex} \longrightarrow \text{Level set convex}
$
Suppose $x_1, x_2 \in L$, let $y=\lambda x_1 + (1-\lambda) x_2$
$
\begin{aligned}
f(y) = f(\lambda x_1 + (1-\lambda) x_2) \\
\le \lambda f(x_1)+(1-\lambda) f(x_2) \\
\le \lambda c + (1-\lambda)c = c \\
\longrightarrow y \in L
\end{aligned}
$
![[Pasted image 20260901122742.png|303]]