A function is said to belong to the class $f \in C^{k,p}_L (Q)$ if it $k$ times is continuously differentiable on $Q$ and the $p$th derivative has a Lipschitz constant $L$.
\[\|\nabla^p f(x) - \nabla^p f(y)\| \leq L \|x-y\|, \qquad \forall x,y \in Q\]The most commonly used $C_L^{1,1}, C_L^{2,2}$ on $\mathbb{R}^n$. Note that:
- $p \leq k$
- If $q \geq k$, then $C_L^{q,p} \subseteq C_L^{k,p}$. The higher the order of the derivative, the stronger the constraint (fewer functions belong to the class)
Prove that the function belongs to the class $C_L^{2,1} \subseteq C_L^{1,1}$ if and only if $\forall x \in \mathbb{R}^n$:
\[\||\nabla^2 f(x)\| \leq L\]Prove also that the last condition can be rewritten, without generality restriction, as follows:
\[-L I_n \preceq \nabla^2 f(x) \preceq L I_n\]Note: by default the Euclidean norm is used for vectors and the spectral norm is used for matrices.
- ΠΠΎΠΊΠ°ΠΆΠΈΡΠ΅, ΡΡΠΎ Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΡ
ΡΡΡΠ°ΡΠ΅Π³ΠΈΠΉ ΠΏΠΎΠ΄Π±ΠΎΡΠ° ΡΠ°Π³Π° Π² Π³ΡΠ°Π΄ΠΈΠ΅Π½ΡΠ½ΠΎΠΌΡ ΡΠΏΡΡΠΊΠ΅:
- ΠΠΎΡΡΠΎΡΠ½Π½ΡΠΉ ΡΠ°Π³ $h_k = \dfrac{1}{L}$
- Π£Π±ΡΠ²Π°ΡΡΠ°Ρ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ $h_k = \dfrac{\alpha_k}{L}, \quad \alpha_k \to 0$
ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡΡΠΈΡΡ ΠΎΡΠ΅Π½ΠΊΡ ΡΠ±ΡΠ²Π°Π½ΠΈΡ ΡΡΠ½ΠΊΡΠΈΠΈ Π½Π° ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ Π²ΠΈΠ΄Π°:
\[f(x_k) - f(x_{k+1}) \geq \dfrac{\omega}{L}\|\nabla f(x_k)\|^2\]$\omega > 0$ - Π½Π΅ΠΊΠΎΡΠΎΡΠ°Ρ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ°, $L$ - ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ° ΠΠΈΠΏΡΠΈΡΠ° Π³ΡΠ°Π΄ΠΈΠ΅Π½ΡΠ° ΡΡΠ½ΠΊΡΠΈΠΈ
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΡΡΠ½ΠΊΡΠΈΡ Π΄Π²ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ :
\[f(x_1, x_2) = x_1^2 + k x_2^2,\]Π³Π΄Π΅ $k$ - Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ. ΠΠΎΡΡΡΠΎΠΉΡΠ΅ Π³ΡΠ°ΡΠΈΠΊ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ, Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΡΡ Π΄Π»Ρ ΡΡ ΠΎΠ΄ΠΈΠΌΠΎΡΡΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π°ΠΈΡΠΊΠΎΡΠ΅ΠΉΡΠ΅Π³ΠΎ ΡΠΏΡΡΠΊΠ° (Π΄ΠΎ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΡΠ»ΠΎΠ²ΠΈΡ $|\nabla f(x_k)| \leq \varepsilon = 10^{-7}$) Π² Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ $k$. Π Π°ΡΡΠΌΠΎΡΡΠΈΡΠ΅ ΠΈΠ½ΡΠ΅ΡΠ²Π°Π» $k \in [10^{-3}; 10^3]$ (Π±ΡΠ΄Π΅Ρ ΡΠ΄ΠΎΠ±Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΡΠ½ΠΊΡΠΈΡ
ks = np.logspace(-3,3)
) ΠΈ ΡΡΡΠΎΠΈΡΡ Π³ΡΠ°ΡΠΈΠΊ ΠΏΠΎ ΠΎΡΠΈ Π°Π±ΡΡΠΈΡΡ Π² Π»ΠΎΠ³Π°ΡΠΈΡΠΌΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΌΠ°ΡΡΡΠ°Π±Π΅plt.semilogx()
ΠΈΠ»ΠΈplt.loglog()
Π΄Π»Ρ Π΄Π²ΠΎΠΉΠ½ΠΎΠ³ΠΎ Π»ΠΎΠ³. ΠΌΠ°ΡΡΡΠ°Π±Π°.Π‘Π΄Π΅Π»Π°ΠΉΡΠ΅ ΡΠ΅ ΠΆΠ΅ Π³ΡΠ°ΡΠΈΠΊΠΈ Π΄Π»Ρ ΡΡΠ½ΠΊΡΠΈΠΈ:
\[f(x) = \ln(1 + e^{x^\top A x}) + \mathbf{1}^\top x\]ΠΠ±ΡΡΡΠ½ΠΈΡΠ΅ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΡ Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΡ.
ΠΠ»Ρ Π½Π°Π³Π»ΡΠ΄Π½ΠΎΡΡΠΈ ΠΌΠΎΠΆΠ΅ΡΠ΅ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΠΊΠΎΠ΄ΠΎΠΌ ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΊΠ°ΡΡΠΈΠ½ΠΎΠΊ:
def f_6(x, *f_params): if len(f_params) == 0: k = 2 else: k = float(f_params[0]) x_1, x_2 = x return x_1**2 + k*x_2**2 def df_6(x, *f_params): if len(f_params) == 0: k = 2 else: k = float(f_params[0]) return np.array([2*x[0], 2*k*x[1]]) %matplotlib inline from mpl_toolkits.mplot3d import Axes3D from matplotlib import cm from matplotlib.ticker import LinearLocator, FormatStrFormatter import numpy as np def plot_3d_function(x1, x2, f, title, *f_params, minima = None, iterations = None): ''' ''' low_lim_1 = x1.min() low_lim_2 = x2.min() up_lim_1 = x1.max() up_lim_2 = x2.max() X1,X2 = np.meshgrid(x1, x2) # grid of point Z = f((X1, X2), *f_params) # evaluation of the function on the grid # set up a figure twice as wide as it is tall fig = plt.figure(figsize=(16,7)) fig.suptitle(title) #=============== # First subplot #=============== # set up the axes for the first plot ax = fig.add_subplot(1, 2, 1, projection='3d') # plot a 3D surface like in the example mplot3d/surface3d_demo surf = ax.plot_surface(X1, X2, Z, rstride=1, cstride=1, cmap=cm.RdBu,linewidth=0, antialiased=False) ax.zaxis.set_major_locator(LinearLocator(10)) ax.zaxis.set_major_formatter(FormatStrFormatter('%.02f')) if minima is not None: minima_ = np.array(minima).reshape(-1, 1) ax.plot(*minima_, f(minima_), 'r*', markersize=10) #=============== # Second subplot #=============== # set up the axes for the second plot ax = fig.add_subplot(1, 2, 2) # plot a 3D wireframe like in the example mplot3d/wire3d_demo im = ax.imshow(Z,cmap=plt.cm.RdBu, extent=[low_lim_1, up_lim_1, low_lim_2, up_lim_2]) cset = ax.contour(x1, x2,Z,linewidths=2,cmap=plt.cm.Set2) ax.clabel(cset,inline=True,fmt='%1.1f',fontsize=10) fig.colorbar(im) ax.set_xlabel(f'$x_1$') ax.set_ylabel(f'$x_2$') if minima is not None: minima_ = np.array(minima).reshape(-1, 1) ax.plot(*minima_, 'r*', markersize=10) if iterations is not None: for point in iterations: ax.plot(*point, 'go', markersize=3) iterations = np.array(iterations).T ax.quiver(iterations[0,:-1], iterations[1,:-1], iterations[0,1:]-iterations[0,:-1], iterations[1,1:]-iterations[1,:-1], scale_units='xy', angles='xy', scale=1, color='blue') plt.show() up_lim = 4 low_lim = -up_lim x1 = np.arange(low_lim, up_lim, 0.1) x2 = np.arange(low_lim, up_lim, 0.1) k=0.5 title = f'$f(x_1, x_2) = x_1^2 + k x_2^2, k = {k}$' plot_3d_function(x1, x2, f_6, title, k, minima=[0,0]) from scipy.optimize import minimize_scalar def steepest_descent(x_0, f, df, *f_params, df_eps = 1e-2, max_iter = 1000): iterations = [] x = np.array(x_0) iterations.append(x) while np.linalg.norm(df(x, *f_params)) > df_eps and len(iterations) <= max_iter: res = minimize_scalar(lambda alpha: f(x - alpha * df(x, *f_params), *f_params)) alpha_opt = res.x x = x - alpha_opt * df(x, *f_params) iterations.append(x) print(f'Finished with {len(iterations)} iterations') return iterations x_0 = [10,1] k = 30 iterations = steepest_descent(x_0, f_6, df_6, k, df_eps = 1e-9) title = f'$f(x_1, x_2) = x_1^2 + k x_2^2, k = {k}$' plot_3d_function(x1, x2, f_6, title, k, minima=[0,0], iterations = iterations)
Solve the Hobbit Village problem. Open In Colab
- Solve the problem of constrained optimization using projected gradient descent Open In Colab