# Conditional Gradient

Conditional Gradient\[Frank-Wolfe Method]

**The problem :**&#x20;

$$
minf(x) \ subject ; to \ x  \in P
$$

​Where $$f$$is convex on the bounded polygonal region $$P$$

How can we determine the search direction $$\mathbf{d}\_k$$in this problem? It is connected to a linear problem.

$$
Z\_k(y):=f(x\_k)+\nabla f(x\_k)^T(y-x\_k) \  min \ z\_k(y)=\nabla f(x\_k)^T(y-x\_k) \ subject ; to \ y \in P
$$

We first look into $$(y-x\_k)$$.&#x20;

Suppose $$y\_k$$is a solution of this problem.

* $$y\_k$$ is an extreme point of the polygon P and hence, since P is convex, the line joining $$y\_k$$and $$x\_k$$is contained in $$P$$and so the vector $$y\_k-x\_k$$is a feasible direction.
* Because of the convexity of $$f$$, $$\nabla f(\bar{x})^T(y-\bar{x}) \geq 0  ;; \forall y\in P$$. It implies that this direction is also a descent direction.
* $$z\_k(y\_k)\leq z(x\_k) = \nabla f(x\_k)^T(x\_k-x\_k)=0$$ , so $$z\_k(y\_k)=0 ; or ; z\_k(y\_k)<0$$
