Utah State University
Department of Electrical and Computer Engineering
ECE 6040 Convex Optimization - Fall 2018

Introduction

General optimization problem

\begin{align} \min_x. & \;\;f_0(x) \\ \text{s.t.} & \;\;f_i(x) \leq 0, \;\;i=0, 1, \cdots, m \\ & \;\;h_i(x) = 0, \;\;i=0, 1, \cdots, p \end{align}

Difficult to solve
Solution methods make compromises (e.g. global optimality, take a very long time to compute, etc.)

Watershed in optimization

"Convexity is a large subject which can hardly be addressed here, see [1], but much of the impetus for its growth in recent decades has come from applications in optimization. An importan treason is the fact that when a convex function is minimized over a convex set every locally optimal solution is global. Also, first-order necessary conditions for optimality tur out to be sufficient. A variety of other properties conducive to computation and interpretation of solutions ride on convexity as well. In fact the great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity. Even for problems that aren't themselves of convex type, convexity may enter for instance in setting up subproblems as part of an interative numerical scheme." --R. Tyrrell Rockafellar (SIAM Review, Vol. 35, No. 2, June 1993)

Convex optimization problem

\begin{align} \min_x. & \;\;f_0(x) \qquad \qquad \qquad \qquad \qquad \;\text{(convex objective function)}\\ \text{s.t.} & \;\;f_i(x) \leq 0, \;\;i=0, 1, \cdots, m \quad \;\text{(convex inequality constraint functions)}\\ & \;\;Ax+b = 0, \;\;i=0, 1, \cdots, p \quad \text{(affine equality constraint functions)} \end{align}

Usually no closed-form solution
Computation time depends on $n^3$ or $n^2m$ and cost of evaluating $f_i$ and its derivatives
Learn to formulate problems in convex form and recognize convex problems
Learn to write efficient and reliable algorithms for solving convex problems
Learn tricks to transfrom problems into convex form

A few examples

Least squares:

\min_x \|b-Ax\|_2

Constrained least squares:

\min_x \| b- Ax\|_2 \quad \text{s.t.} \quad Cx=d, \quad f_i(x) \leq 0, \;i=1, 2, \cdots, m

Linear programming:

\min_x c^T x \quad \text{s.t.} \quad Gx \leq h, \quad Ax=b

Signal and image denosing:

\min_x \| y - x \|_2 + \gamma \| D x \|_1 \\ \min_x \| y - x \|_2 \quad \text{s.t.} \quad \| D x \|_1 \leq \varepsilon

Image segmentation via graph cuts:

\min_X \text{tr}(CX) - \gamma \log(X)\quad \text{s.t.}\quad X=X^T \geq 0

Support vector machine (machine learning):

\text{maximize} \;\mathbf{1}^T\boldsymbol{\lambda} -\frac{1}{2} \boldsymbol{\lambda}^T \mathbf{M} \boldsymbol{\lambda} \quad \text{subject to} \quad \boldsymbol{\lambda}\geq \mathbf{0}, \quad \boldsymbol{\mu}\geq \mathbf{0}, \\ \boldsymbol{\lambda} + \boldsymbol{\mu} = \gamma\mathbf{1}, \quad \boldsymbol{\lambda}^T\mathbf{y} = 0

Filter design:

\min_r g^T r \quad \text{s.t.} \quad v(\omega)^T r \leq \xi_2, \omega \in [\pi/K,\pi] \\ v(\omega)^T r \leq \xi_3, \omega \in [0,\pi/K], \qquad \|S r\|_2 \leq \xi_4 \\ r(0) = K/M, \qquad v(\omega)^T r \geq 0, \omega \in [0,\pi]

Adaptive filtering and equalization

\min_w.\;\; w^T f\quad \text{s.t.} \quad |w^T g_i| \leq 1, \;\;i = 1, 2, \cdots, m

Optimal sell/buy order execution

\max_s.\;\; p^T s - s^T Q s \quad \text{s.t.} \quad 0 \leq s \leq S^\text{max}, \quad 1^T s = S

Real time minimum norm input transfer to a desired state $x^\text{desired}$

\begin{align} \underset{u_\tau}{\text{minimize}}& \;\;\sum_{\tau=t}^{T-1} \| u_\tau \|_2^2 \\ \text{subject to} & \;\; x_{\tau+1} = A x_\tau + B u_\tau, \quad \tau=t, \cdots, t+T-1 \\ &\;\; u^\text{min} \leq u_\tau \leq u^\text{max}, \quad \tau=t, \cdots, t+T-1 \\ &\;\; x^\text{min} \leq x_\tau \leq x^\text{max}, \quad \tau=t, \cdots, t+T-1 \\ &\;\; x_T = x^\text{desired} \end{align}

Model predictive control

\begin{align} \underset{v_t}{\text{minimize}}& \;\;\frac{1}{T} \sum_{t=1}^T\left(z_t^T Q z_t + v_t^T R v_t\right) + z_{T+1}^T Q_f z_{T+1} \\ \text{subject to} & \;\; z_{t+1} = A x_t + B v_t, \quad t=1, \cdots, T \\ &\;\; v \in \{u|\|u\|_\infty \leq U^\text{max}\}, \quad t=1, \cdots, T \\ &\;\; z_1 = x_t \end{align}

Optimal network flow rates

\begin{align} \underset{f}{\text{minimize}} & \;\; w^T f \\ \text{subject to} & \;\; Rf \leq c, \quad 0\leq f \leq s \end{align}

Colorization of grayscale images

\begin{align} \underset{U, \nu_i, \mu_i}{\text{minimize}} & \;\;\sum_i \nu_i + \mu_i \\ \text{subject to} & \;\; AU + \nu - \mu = b \\ &\;\; \nu_i, \mu_i, U_i, b_i \geq 0 \end{align}

Blind deconvolution

\begin{align} \underset{\lambda}{\text{maximize}} &\;\;\text{Re}\langle y, \lambda \rangle \\ \text{subject to} & \;\; \begin{bmatrix} I & \sum_{i=1}^L \lambda_i A_i \\ \sum_{i=1}^L \lambda_i A_i^T & I \end{bmatrix} \geq 0 \end{align}

\begin{align} \underset{W_1, W_2, X}{\text{minimize}} & \;\; \frac{1}{2} \text{trace}(W_1) + \frac{1}{2} \text{trace}(W_2) \\ \text{subject to} & \;\; \begin{bmatrix} W_1 & X \\ X & W_2 \end{bmatrix} \geq 0, \qquad y = {\cal A}(X) \end{align}

\begin{align} \underset{X}{\text{minimize}} &\;\;\| X \|_\ast \\ \text{subject to} & \;\; y={\cal A}(X) \end{align}

Total variation (TV) deblurring

\min \; \| {\cal A}(x) - b \|_F^2 + 2\lambda TV(x)

Source localization

\min_x \sum_{j=1}^M (\| x- a_j\|_2 - d_j)^2 \qquad \text{(non-convex)}

Maximum likelihood detector

\min \; \|y - H x\|_2^2 \quad \text{s.t.} \quad x_i \in \text{symbol alphabet}

\min \;\text{trace}(QZ) \quad \text{s.t.} \quad \text{diag}(Z) = 1, \quad Z \geq 0

Lots of applications

structural optimization
statistics
data fitting
signal processing
communications
image processing
computer vision
information theory
finance
portfolio optimization
advertising
circuit design
compressive sensing
tomography and medical imaging
seismology
radar waveform design
image inpainting
grayscale image colorization
colaborative filtering and recommender systems
filter design in digital signal processing
dimensionality reduction and data visualization
transportation systems
control and navigation
autonomous systems
machine learning
game theory
power generation and distribution
processor speed scheduling
object tracking in video
image segmentation
source localization
beamforming and spectral estimation
...