Today’s Lesson

1. Convex Optimization
2. The Lagrangian
3. Some Examples

Reminder: Group Work

• Will be 60% of the final grade
• Computer graphics / optimization related small project
• To be done in groups of ideally 3 people
  • Individually is possible with prior consent
• Important Dates
  • Initial Report Due Date: June 17th (6月17日)
  • Presentation Slides Due Date: July 21rd (7月21日)
  • Presentation: July 22th (7月22日)
  • Final Report Due Date: July 29st (7月29日)

Descent Direction (Review)

• $p^k$ is required to be a descent direction such that $(p^k)^\intercal \nabla f(x^k) < 0$
  • This condition guarantees that $f$ can be reduced along the direction $p^k$
• Generally the search direction has the form: $$p^k = (-B^k)^{-1} \nabla f(x^k)$$
  • $B^k\in\mathbb{R}^{n\times n}$ is symmetric and non-singular matrix
• With $B^k$ being positive definite, we have $$(p^k)^\intercal \nabla f(x^k) = -\nabla f(x^k)^\intercal (B^k)^{-1} \nabla f(x^k) < 0$$

Search Directions (Review)

• Steepest-descent (最速降下)
  • $p^k = -\nabla f(x^k)$
  • Direction of most rapid decrease
• Newton direction (ニュートン方向)
  • $p^k = -(\nabla^2 f(x^k))^{-1} \nabla f(x^k)$
• Quasi-Newton (准ニュートン法)
  • $p^k = -(B^k)^{-1} \nabla f(x^k)$
  • $B^k$ approximates the hessian $\nabla^2 f(x^k)$
  • Symmetric Rank-One (SR1)
  • BFGS (Broyden-Fletcher-Goldfarb-Shannon)
• Non-linear Conjugate Gradient Methods (共役勾配法)
  • $p^k = - \nabla f(x^k) + \beta^k p^{k-1}$

Convex Program (Review)

An optimization problem is called a convex optimization problem (凸最適化問題) if the objective and constraint functions $f_0,\ldots,f_m$ satisfy

 $$f_i(\alpha x + \beta y) \leq \alpha f_i(x) + \beta f_i(y), \\
   \forall x,y\in\mathbb{R}^n \quad\text{and} \\
   \forall \alpha, \beta \in \mathbb{R} \;\; \text{s.t}\;\; \alpha+\beta=1,\,\alpha\geq 0,\,\beta\geq 0$$ 

Example: Hyperplane

• A hyperplane（超平面） is a set of the form $$\{\;x \;|\; a^\intercal x = b\;\}$$ where $\alpha \in \mathbb{R}^n$, $a \neq 0$, and $b \in \mathbb{R}$
  • It is the solution set of a non-trivial linear equation among the component of $x$ (and thus an affine set)
  • Can be interpreted as a hyperplane with normal vector $\alpha$ and offset from origin $b$
• A hyperplane divides $\mathbb{R}^n$ into two halfspaces（半空間） which have the form $$\{\;x \;|\; a^\intercal x \leq b\;\}$$
  • Halfspaces are convex, but not affine

Example: Euclidean Ball

• A (Euclidean) ball（球体） in $\mathbb{R}^n$ has the form

   $$\begin{align}
  B(x_c, r) &= \{\; x \;|\; \|x-x_c\|_2 \leq r\;\} \\
          &= \{\; x \;|\; (x-x_c)^\intercal (x-x_c) \leq r^2 \;\}
  \end{align}$$ 

  where $r>0$
  • Vector $x_c$ is the center of the ball
  • Scalar $r$ is the radius

Example: Polyhedra

• A polyhedron（多面体） is defined as the solution set of a finite number of linear equalities and inequalities:

   $$\begin{align}
  \mathcal{P} = \{\;x \;|\; & a_j^\intercal x - b_j \leq 0,\; j=1,\ldots,m, \\
   & c_j^\intercal x-d_j=0,\; j=1,\ldots,p\;\}
  \end{align}$$ 

  • Formed by the intersection of halfspaces
  • Halfspaces are convex, intersection conserves convexity

Operations that Preserve Convexity

• Intersection. If $S_1$ and $S_2$ are convex, then $S_1 \cap S_2$ is convex.
• Affine functions $f(x) = Ax+b$ where $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$.
  • Suppose $S\subseteq \mathbb{R}^n$ is convex and $f \colon \mathbb{R}^n \to \mathbb{R}^m$ is an affine function. Then the image of $S$ under $f$, $$f(S) = \{ f(x) \;|\; x\in S \}$$ is convex.
• Perspective function $P\colon \mathbb{R}^{n+1} \to \mathbb{R}^n$, with domain $\dom{P}=\mathbb{R}^n \times \mathbb{R}_{++}$ ($\mathbb{R}_{++}=\{x\in\mathbb{R} \;|\; x>0\}$). If $C\subseteq \dom{P}$ is convex, then its image $$P(C)= \{P(x) \;|\; x\in C \}$$ is convex.

Extended-value Extensions

• It is often convenient to extend a convex function to all of $\mathbb{R}^n$ by defining the value to be $\infty$ outside of its domain. If $f$ is convex, we define its extended-value extension $f\colon \mathbb{R}^n \rightarrow \mathbb{R}\cup\{\infty\}$ by

$$\tilde{f}= \left\{\begin{array}{lr} f(x) & x\in\dom{f} \\ \infty & x\notin\dom{f} \\ \end{array}\right.$$

• This allows us to manipulate functions without having to worry about the domains
• We will always assume we are using the extended functions when applicable

First-Order Conditions

• Suppose $f$ is differentiable. Then $f$ is convex if and only if $\dom{f}$ is convex and $$f(y) \geq f(x) + \nabla f(x)^\intercal (y-x)$$ holds for all $x, y\in\dom{f}$.

Second-Order Conditions

• Assuming $f$ is twice differentiable, then $f$ is convex if and only if $\dom{f}$ is convex and its Hessian is positive semi-definite: for all $x\in\dom{f}$, $$\nabla^2f(x) \succeq 0$$
  • $X\succeq Y$ denotes matrix inequality between symmetric matrices $X$ and $Y$
  • For a function on $\mathbb{R}$, this reduces to $f''(x)\geq 0$ (and $\dom{f}$ being convex)

Example: Max Function

• Max function. $f(x) = \max\{x_1,\ldots,x_n\}$ satisfies, for $0 \leq \theta \leq 1$ ,

$$\begin{align} f(\theta\,x + (1-\theta)\,y) &= \max_i (\theta\,x_i + (1-\theta)\,y_i) \\ &\leq \theta \max_i x_i + (1-\theta)\max_i y_i \\ &= \theta f(x) + (1-\theta)f(y) \end{align}$$

Operations that Preserve Convexity

• Non-negative weighted sum. $f = w_1 f_1 + \cdots + w_m f_m$ is convex when $w_i > 0$ and $f_i$ are convex.
• Composition with an affine mapping. Suppose $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$, $A\in\mathbb{R}^{n\times m}$, and $b\in\mathbb{R}^n$. Define $g \colon \mathbb{R}^m \rightarrow \mathbb{R}$ by $$g(x) = f(Ax+b)$$ with $\dom{g} = \{\,x \;|\; Ax+b\in\dom{f}\,\}$. Then if $f$ is convex, so is $g$.
• Pointwise maximum and supremum. If $f_1$ and $f_2$ are convex functions, then their pointwise maximum $f$, defined by $$f(x) = \max\{\,f_1(x),\,f_2(x)\,\}$$ is also convex.

Example: Binary Hinge loss

• The binary hinge loss（ヒンジ損失） is defined as: $$L(y) = \max( 0,\;1-t\; y )$$ where
  • $y$: is the output of a model (e.g., $y = w^\intercal x + b$)
  • $t$: is either +1 or -1 depending on the true class of the example
• For a given dataset, we can write the training loss of linear SVM with $$\sum_{i=0}^N \max(0,\;1-t_i\;w^\intercal x)$$
  • Is this convex?

Optimal and Locally Optimal Points

• The optimal value $p^\star$ is defined as

   $$\begin{align}
  p^\star = \inf \{\, f_0(x) \;|\; &f_i(x) \leq 0,\,i=1,\ldots,m\, \\
  &h_i(x)=0,\,i=1,\ldots,p\}
  \end{align}$$ 

  • If $p^\star$ is infeasible it will have the extended value $+\infty$
  • If $p^\star=-\infty$, we say it is unbounded below
• We say $x^\star$ is an optimal point or solution if it is feasible and $f_0(x^\star)=p^\star$.

$$\begin{align} X_{opt} = \{\, x \;|\; &f_i(x) \leq 0, i=1,\ldots,m, \\ &h_i(x)=0, i=1,\ldots,p,\; f_0(x)=p^\star \,\} \end{align}$$

Feasibility Problem

• Sometimes it is important to know if the problem is feasible
• This can be formulated by the following optimization problem:

   $$\begin{align}
  \text{find}   \quad & x \\
  \text{subject to} \quad & f_i(x) \leq 0, \quad i=1,\ldots,m \\
  & h_i(x) = 0, \quad i=1,\ldots,p
  \end{align}$$ 

  • If a solution $x^\star \neq \infty$ is found, we say that the problem is feasible

Lagrange Dual Function

• We define the Lagrange dual function $g \colon \mathbb{R}^m \times \mathbb{R}^p \rightarrow \mathbb{R}$ as the minimum value of the Lagrangian over x: for $\lambda \in \mathbb{R}^m$ and $v \in \mathbb{R}^p$,

   $$\begin{align}
  g(\lambda,v) &= \inf_{x\in \mathcal{D}} L(x,\lambda,v) \\
  &= \inf_{x\in\mathcal{D}} \left( f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p v_i h_i(x) \right)
  \end{align}$$ 

  • When unbounded below, it takes the value of $\infty$
  • $g(\lambda,v)$ is concave even when the original problem is not convex

Lower Bounds on Optimal Value

• The dual function yields lower bounds on the optimal value $p^\star$
• For any $\lambda \succeq 0$ and any $v$ we have $$g(\lambda,v) \leq p^\star = f_0(x^\star)$$
• This can be seen as for a feasible point $\tilde{x}$, $$\sum_{i=1}^m \lambda_i f_i(\tilde{x}) + \sum_{i=1}^p v_i h_i(\tilde{x}) \leq 0$$ Therefore

   $$\begin{align}
  g(\lambda,v) &= \inf_{x\in\mathcal{D}} L(x,\lambda,v) \leq L(\tilde{x},\lambda,v) \\
  &= f_0(\tilde{x}) + \sum_{i=1}^m \lambda_i f_i(\tilde{x}) + \sum_{i=1}^p v_i h_i(\tilde{x}) \leq f_0(\tilde{x})
  \end{align}$$ 

Simple Example: Least-Squares

• We can write the problem as

   $$\begin{align}
  \text{minimize}   \quad& x^\intercal x \\
  \text{subject to} \quad& Ax = b
  \end{align}$$ 

  where $A \in \mathbb{R}^{p \times n}$
• The Lagrangian is then $L(x,v) = x^\intercal x + v^\intercal(Ax - b)$
  • Optimality condition $\nabla_x L(x,v) = 2x + A^\intercal v = 0$ with solution $x = -(1/2)A^\intercal v$
• The dual function is:

   $$\begin{align}
  g(v) = \inf_x L(x,v) &= L(-(1/2)A^\intercal v, v) \\
  &= -(1/4) v^\intercal A A^\intercal v - b^\intercal v
  \end{align}$$ 

• This lower bounds the original function with $$-(1/4)v^\intercal A A^\intercal v - b^\intercal v \leq \inf\{\,x^\intercal x \;|\; Ax = b\,\}$$

Weak Duality

• The optimal value of the dual problem $d^\star$ is the best lower bound on $p^\star$ $$g(\lambda^\star, v^\star)=d^\star \leq p^\star=f_0(x^\star)$$
  • This holds when the primal problem is not convex
  • Also holds when unbounded (the dual problem becomes unfeasible)
• The gap $p^\star - d^\star$ is called the optimal duality gap of the original problem

Strong Duality And Slater’s Condition

• When $d^\star = p^\star$, we say that strong duality holds
  • This does not hold in general
  • If the primal problem is convex, there is usually strong duality
• For a convex problem of the form

   $$\begin{align}
  \text{minimize}   \quad & f_0(x) \\
  \text{subject to} \quad & f_i(x) \leq 0, \quad i=1,\ldots,m \\
  & Ax = b
  \end{align}$$ 

  if there exists an $x \in \relint{\mathcal{D}}$ such that $$f_i(x)<0,\quad i=1,\ldots,m,\quad Ax=b$$ then strong duality holds (Slater’s Condition).
  • $\relint{\mathcal{D}} = \{\, x\in\mathcal{D} \;|\; B(x,r) \cap \aff{\mathcal{D}} \subseteq \mathcal{D} \;\text{for some}\; r>0 \,\}$ where $B(x,r) = \{\, y \;|\; \|x-y\| \leq r \,\}$

Example: Non-Convex Problem (1)

• We want to optimize the following problem

   $$\begin{align}
  \text{minimize}   \quad & x^\intercal A x + 2b^\intercal x \\
  \text{subject to} \quad & x^\intercal x \leq 1 \\
  \end{align}$$ 

  where $A\in \mathcal{S}^n$ (symmetric matrix), $A \not\succeq 0$, and $b\in\mathbb{R}^n$.
  • Since $A \not\succeq 0$, this is not a convex problem
  • This problem is called the trust region problem
• The Lagrangian is

   $$\begin{align}
  L(x,\lambda) &= x^\intercal A x + 2b^\intercal x + \lambda(x^\intercal x-1 ) \\
  &= x^\intercal (A+\lambda I)x + 2b^\intercal x - \lambda
  \end{align}$$ 

Example: Non-Convex Problem (2)

• Find the infimum of the Lagrangian

   $$\nabla_x L(x,\lambda) = 2 (A+\lambda I) x + 2 b^\intercal \\
  \nabla_x L(x,\lambda) = 0 \implies x = -(A+\lambda I)^\dagger b^\intercal$$ 

• Replacing the $x$ in $L(x,\lambda)$ with the expression above, we obtain the dual function

   $$g(\lambda) = \begin{cases}
   -b^\intercal (A+\lambda I)^\dagger b - \lambda & A+\lambda I \succeq 0, \; b\in \mathcal{R}(A+ \lambda I) \\
   -\infty & \text{otherwise} \\
  \end{cases}$$ 

  • $A^\dagger$ indicates pseudo-inverse
  • $\mathcal{R}(A) = \{\, Ax \;|\; x\in \mathbb{R}^n \,\}$ is the range of the matrix $A\in\mathbb{R}^{m\times n}$

Example: Non-Convex Problem (3)

• The problem can finally be written as

   $$\begin{align}
  \text{maximize}   \quad& -b^\intercal (A+\lambda I)^\dagger b - \lambda \\
  \text{subject to} \quad& A+\lambda I\succeq 0,\quad b\in\mathcal{R}(A+\lambda I)
  \end{align}$$ 

  with variable $\lambda\in\mathbb{R}$
  • This problem is convex
  • Duality gap is 0

KKT Optimality Conditions (1)

• Assuming $f_0,\ldots,f_m,h_1,\ldots,h_p$ are differentiable (not necessarily convex). Let $x^\star$ and $(\lambda^\star, v^\star)$ be any primal and dual optimal points with zero duality gap. Thus,

   $$\begin{align}
  \nabla L(x^\star,\lambda^\star,v^\star) =&
  \nabla f_0(x^\star) + \sum_{i=1}^m \lambda_i^\star \nabla f_i(x^\star) \\
  &+ \sum_{i=1}^p v_i^\star \nabla h_i(x^\star) = 0
  \end{align}$$ 

KKT Optimality Conditions (2)

• We then obtain

   $$\begin{align}
  f_i(x^\star) &\leq 0, \quad i=1,\ldots,m \\
  h_i(x^\star) & =   0, \quad i=1,\ldots,p \\
  \lambda_i^\star &\geq 0, \quad i=1,\ldots,m \\
  \lambda_i^\star f_i(x^\star) &= 0, \quad i=1,\ldots,m \\
  \nabla L(x^\star,\lambda^\star,v^\star) &= 0
  \end{align}$$ 

  which are called the Karush-Kuhn-Tucker (KKT)（カルーシュ・キューン・タッカー条件） conditions.
  • When the primal problem is convex, these conditions are sufficient for the points to be primal and dual optimal

Solving the Primal via the Dual

• If strong duality holds, and a dual optimal solution $(\lambda^\star, v^\star)$ is known. Suppose the solution of

   $$\text{minimize} \quad f_0(x) + \sum_{i=1}^m \lambda_i^\star f_i(x) + \sum_{i=1}^p v_i^\star h_i(x)$$ 

  is unique. Then,
  • If the solution is primal feasible, it must be primal optimal
  • If the solution is not primal feasible, no primal optimal point can exist
• This allows us to solve the dual instead of the primal, when it is easier

Video

Video

Procrustes Alignment

• Formulation of Procrustes Alignment

   $$\begin{align}
  \text{minimize}_{X,R}   \quad & \| RP - QX \|_F^2 \\
  \text{subject to}       \quad & X \in \Pi_n \\
  & R \in \mathcal{O_d}
  \end{align}$$ 

  • $\Pi_n$ is a permutation of $n$ elements
  • $\mathcal{O}_d$ is an orthogonal projection matrix
  • Quadratic program and thus not necessary convex
• Rewritten as

   $$\begin{align}
  \text{minimize}_{X,R}  \quad & \| RP - QX \|_F^2 \\
  \text{subject to}      \quad & X 1 = 1, \quad 1^\intercal X = 1^\intercal \\
  & X_j X_j^\intercal = \text{diag}(X_j), \; j=1,\ldots,n \\
  & R R^\intercal = R^\intercal R = I \\
  \end{align}$$ 

Relaxation

• Given quadratic program:

   $$\begin{align}
  \text{minimize}   \quad & f_0(x) \\
  \text{subject to} \quad & f_i(x) \leq 0, \quad i=1,\ldots,m \\
  & h_i(x) = 0, \quad i=1,\ldots,p \\
  \end{align}$$ 

• Introduce new variables to replace quadratic monomials, e.g., $Y_{i,j}$, $1 \leq i$, $j \leq n$ to replace $x_i x_j$

   $$\begin{align}
  \text{minimize}   \quad & \mathcal{L}[f_0(x)] \\
  \text{subject to} \quad & \mathcal{L}[f_i(x)] \leq 0, \quad i=1,\ldots,m \\
  & \mathcal{L}[h_i(x)] = 0, \quad i=1,\ldots,p \\
  Y = x x^\intercal
  \end{align}$$ 

  • Make the new formulation be a linear polynomial
  • Replace last constraint with $Y \succeq x x^\intercal$

Video

Formulation

 $$\begin{align}
\text{minimize}_{X,R}   \quad & \| G(x-u_t) \|^2 + \| W(x-u_c) \|^2 \\
\text{subject to}       \quad & x \in C_{DIV}
\end{align}$$ 

• $x$ is guided velocity field
• $C_{DIV}$ is the space of divergence-free velocity fields
• $u_c$ and $u_t$ are the current and target velocity fields
• $W$ is the guiding weights matrix
• $G$ is the Gaussian blur matrix

Video

Optimization Problem

 $$\text{minimize} \sum_{\{p,q\}\in\mathcal{N}} V_{p,q}(c_p,c_q) + \sum_{p\in P} D_p(c_p) \\
V_{p,q} \propto \begin{cases}
I_p & \text{for}\; c_p \neq c_q \\
0 & \text{otherwise}
\end{cases} \\
D_p(c_p) = \lambda K$$ 

• $c_p$ color of pixel $p$
• $I_p$ grayscale value of pixel $p$
• $\mathcal{N}$ neighborhood
• $\lambda \in [0,1]$
• $K$ is energy of discontinuity

Tangent Research: Relighting

Generating Digital Painting Lighting Effects via RGB-space Geometry. Lvmin Zhang, Edgar Simo-Serra, Yi Ji, and Chunping Liu. ACM Transactions on Graphics (Presented at SIGGRAPH), 2020.

Next Class

1. Unconstrained Minimization
   1. Descent Methods
   2. Gradient Descent Methods
   3. Steepest Descent Methods
   4. Newton’s Method