Necessary and Sufficient Conditions for Unrestricted Optimization Problems

In a previous post we have seen the conditions in which extremum values are guaranteed to exist. Nonetheless, there are cases in which the extremum values are there but the Weierstrass-Extremum value theorem didn’t tell us that much. The function x^2 has a global minimum on the interval (-1,1), for example. Further, the function

g(x) = \displaystyle \frac{1}{\sqrt{2 \pi}} e^{-(\frac{x^2}{2})} - \frac{1}{\sqrt{2\pi}}  e^{-(\frac{(x-2)^2}{2})}.

has a global maximum and a global minimum on the open interval (-5,5).


Continue reading


Conjugated Directions Methods – Part I

Let’s say we have the following unrestricted quadratic problem to solve:

\displaystyle \min_{x}{x^TQx - b^Tx} \quad \quad (P)

We further assume that Q \in \mathbb{R}^{n+1} is a symmetric positive definite matrix.

Let’s say that we have an iterative algorithm to find the solution x^\star of problem (P). The algorithm works by selecting a “good” direction d_k at iteration k and then walk some amount \alpha _k in that direction.

x_{k+1} = x_k + \alpha _k d_k.

Moreover, let’s say that we know how to compute \alpha _k in order to minimize the problem:

\displaystyle f(x_{k+1}) = \min_{\alpha _k}{f(x_k + \alpha _k d_k)}.

Continue reading