../

2026-10-15 CVXOPT Scribe

$\newcommand{\qq}{\quad\quad}$ $\newcommand{\R}{\mathbb{R}}$

Quiz topics

  • Definition of a convex problem
  • Transformations
    • Change of variables
    • Transform objective and or constraints
    • Eliminating affine equality constraints
    • Optimizing out some of the variables
  • Key facts about convex optimization problems
    • Local optimum is the global optimum
      • This isn’t based on differentiation
      • $f(x) \le f(x')\qq \forall x' \in B_{x, r}, r> 0$
    • $\nabla f_0 (x) = 0 \implies x$ is the global minimum
    • If $x^*$ is an optimum, then $\forall y\text{ (feasible) , } \nabla f_0(x^*)^T (y - x)\ge 0$
      • This is essentially what the Lagrange multipliers tell us
      • $\nabla f_0(x^*)$ is then a separating hyperplane
  • Linear Programming
  • Quadratic Programming

Chapter 6. Approximation and Fitting

Linear Regression (Ordinary Least Square)

Suppose you have to fit a line to some data. How do we determine the best line? We want the line to be “close” to data points. That means that we want the norm of the vectors from the line to the point to be small. Since working with square roots is a pain in the ass, we just square it. The problem is still the same. This looks like

$$\text{minimize } \|ax + b -y \|_2^2$$

Here $x$ and $y$ are just numbers. If we gather up all the $x$-s and the $y$-s and put them into a vector then

$$ x = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} ,\qq y= \begin{bmatrix} y_1\\ \vdots \\ y_n \end{bmatrix}\\ \text{minimize } \| ax + b\mathbf{1} - y \|_2^2 $$

We call this difference as a residual. So this can be equivalently written as

$$ \text{minimize}\qq \|r\|_2^2 $$

The key thing to note is that fitting/approximation/estimation all just look like a norm minimization problem which is just a convex optimization problem.

Multivariate Case

Suppose $y = \beta_1 x_1 + \beta_2 x_2 + \ldots \beta_k x_k$

Then we create a $n\times k$ matrix $X$ and restate the problem as

$$ \text{minimize}\qq\|X\beta - y\|_2^2 $$

The optimal is found at

$$ \beta^* = (X^TX)^\dagger X^Ty $$

You can add a column of just 1s to get an intercept

The above notation is most prevalent in the statistic circles. You might have noticed that we are trying to find the $\beta$s rather than the $x$-s. In optimization we usually denote this problem as

$$ \text{minimize}\qq\|Ax -b\|_2^2 $$

Here we solve for $x$

Geometric Intuition

The most obvious intuition is the we are trying to create a hyperplane that reduces the distance between the points and itself. But there is another view:

Suppose you have the range $\mathcal{R}(A)$, then we are trying the find the closest point to the projection of $b$ onto this subspace.

Examples of different norms

$\ell^2$ norm

This is our regular Euclidean norm. We usually square this to make our life easier. The solution to $\|Ax-b\|_2^2$ is $X^* = \{A^\dagger b + (I - A^\dagger A)w : w \in \R^n\}$

Sum of absolutes approximation $\ell^1$

$$\sum_1|a_i^Tx - b_1|$$

You can solve this using Linear Programming

$$ \text{minimize}\qq \mathbf{1}^Tz \\ \text{subject to }-z \preceq Ax - b \preceq z $$

Chebyshev Approximation

We know that the $\ell^\infty$ norm is the max over all the coords. We want to minimize this maximum. Hence this is also called as minimax approximation.

$$ (\|\cdot\|_\infty) $$