Alejandro Garcés Ruiz - Mathematical Programming for Power Systems Operation

The convergence of the algorithm can be visualized by using the module MatplotLib as follows:

importmatplotlib.pyplot asplt t = 0.5 conv = [] E = [10,10] for iter in range(50): E += - t*grad_f(E) conv += [np.linalg.norm(grad_f(E))] plt.semilogy(conv) plt.grid() plt.xlabel("Iteration") plt.ylabel("|Gradient|") plt.show()

The result of the script is shown in Figure 2.7. As expected, the convergence rate is linear; that is to say, the convergence plot describes almost a line in a semi-logarithmic scale. The value of ε can be used as convergence criteria (a gradient ‖∇ f ‖ ≤ 10 −4can be considered as the local optimum for this problem).

Figure 2.7 Convergence of the gradient method.

Notice that addition was simplified by the statement +=. In general, an statement such as x=x+1 is equivalent to x+=1. More details about this aspect are presented in Appendix C.

Reality imposes physical constraints into the problems and these constraints must be considered into the model. For example, an optimization model may include equality constraints, as presented below:

(2.39)

For solving this problem, a function called lagrangian is defined as follows:

(2.40)

This new function depends on the original decision variables x and a new variable λ , known as Lagrange multiplier or dual variable. By means of the lagrangian function, a constrained optimization problem was transformed into an unconstrained optimization problem that can be solved numerically, namely:

(2.41)

(2.42)

by a small abuse of notation, ∂ f / ∂ x is used instead of ∇ f , which is the formal representation for the n-dimentional case, (the same for L and g ). Notice that the optimal conditions of L imply optimal solution in f but also feasibility in terms of the constraint.

The first condition implies that the gradient of the objective function must be parallel to the gradient of the constraint and, the Lagrange multiplier is the proportionality constant. Besides this geometrical interpretation, Lagrange multipliers have another interesting interpretation. Suppose a local optimum x~ is found for a constrained optimization problem, and we want to know the sensibility of this optimum with respect to a . The following derivative can be calculated, relating the change of the objective function with respect to a change in the constrain:

(2.43)

(2.44)

(2.45)

The first two terms in the right-hand side of the equation vanishes, in view of the optimal conditions of x~; thus, the following expresion is obtained:

(2.46)

this means that λ is the variation of the lagrangian (and hence the objective function), for a small variation on the parameter a (see Chapter 3for more details about dual variables).

Consider the following optimization problem

(2.47)

If the problem were unconstrained, the solution would be x = 0, y = 0; however, the solution must fulfill the constraint x + y = 1. Therefore, a new function is defined as follows:

(2.48)

with the following optimal conditions

(2.49)

(2.50)

(2.51)

This is a linear system of equation with solution x = 1/2, y = 1/2, and λ = 1 that constitutes the optimum of the problem.

The optimal conditions for both constrained and unconstrained problems constitute a set of algebraic equations S ( x ) for the first case and S ( x , λ ) for the second case. This set can be solved using Newton’s method 4.

Consider a set of algebraic equations S ( x ) = 0 where S : n→ nis continuous and differentiable. Thus, the following approximation is made:

(2.52)

where is the Jacobian matrix of S and Δ x = x − x 0. This constitutes the first-order approximation of S around a point x 0; finding the zero of S means to approximate successively the solution by using the following iteration: