Constrained Convex Problems

Example

${\min }_{x}f(x)$ subject to $x\in C$

• $f(\cdot )$ is a convex function
• $C\subseteq R^n$

Example

Projected Gradient Descent

Projected Gradient Descent Algorithm

Franke-Wolfe

Duality and Lagrange Multipliers

Lagrangian

Consider general minimisation problem ${\min }_{x\in {\mathbb{R}}^n}{f}_0(x)$ subject to:

(does not need to be convex, but we pay attention to convex case)

We define Lagrangian as:

• Incorporate constraints into a new objective function
• ${\lambda }_i$ is Lagrange multiplier associated with $f_i(x)\le 0$, with ${\lambda }_i\ge 0$
• $v_i$ is Lagrange multiplier associated with $h_i(x)=0$
• Lagrange multipliers can be thought of as enforcing soft constraints

Example

Given ${\max }_{x,y\in \mathbb{R}}xy$ subject to $x+y=1$: $L(x,y,v_1)=-xy+v_1\cdot (1-x-y)$

Partial derivatives of the function:

$$\begin{array}{rlrl}\frac{\partial L}{x}& =-y-v_1& & =0\\ \frac{\partial L}{y}& =-x-v_1& & =0\\ \frac{\partial L}{v_1}& =1-x-y& & =0\end{array}$$

We have $x=y$, $x+y=1$, thus $x=y=0.5$ (only critical point of $L$).

Lagrange multiplier

Slides 28

Lagrange dual function

Lagrange dual function: $g:R^m\times R^p\to R$