Generalized differential calculus and applications to optimizatio

Portland State University PDXScholar Dissertations and Theses Dissertations and Theses Spring 6-1-2017 Generalized Differential Calculus and Applications to Optimization R. Blake Rector Portland State University Follow this and additional works at: https://pdxscholar.edu/open_access_etds Part of the Mathematics Commons, and the Power and Energy Commons Let us know how access to this document benefits you. Recommended Citation Rector, R. Blake, "Generalized Differential Calculus and Applications to Optimization" (2017).

Dissertations and Theses.5519 This Dissertation is brought to you for free and open access. It has been accepted for inclusion in Dissertations and Theses by an authorized administrator of PDXScholar. Please contact us if we can make this document more accessible: pdxscholar@pdx. Generalized Differential Calculus and Applications to Optimization by Robert Blake Hayden Rector A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Mathematical Sciences Dissertation Committee: Mau Nam Nguyen, Chair Robert Bass Gerardo Lafferriere Bin Jiang Tugrul Daim Portland State University 2017 © 2017 Robert Blake Hayden Rector Abstract This thesis contains contributions in three areas: the theory of generalized calcu- lus, numerical algorithms for operations research, and applications of optimization to problems in modern electric power systems.

A geometric approach is used to ad- vance the theory and tools used for studying generalized notions of derivatives for nonsmooth functions. These advances specifically pertain to methods for calculating subdifferentials and to expanding our understanding of a certain notion of derivative of set-valued maps, called the coderivative, in infinite dimensions. A strong understand- ing of the subdifferential is essential for numerical optimization algorithms, which are developed and applied to nonsmooth problems in operations research, including non- convex problems. Finally, an optimization framework is applied to solve a problem in electric power systems involving a smart solar inverter and battery storage system providing energy and ancillary services to the grid.

i This thesis is dedicated to my grandfather, Dr. Rector, who inspired me to—among other things—study mathematics. ii Table of Contents Abstract. ii List of Tables.

vi List of Figures .1 Convex Analysis, Nonsmooth Analysis, and Variational Analysis .3 Electric Power Systems .4 Overview of Research .1 Basic Tools of Convex Analysis and Optimization .2 Optimal Value Function. 9 2 Generalized Differential Calculus .1 A Geometric Approach to Subdifferential Calculus. 32 3 Applications to Facility Location Problems .1 Introduction to the Fermat-Torricelli Problem and Nesterov’s Method 41 iii 3.1 Nesterov’s Smoothing Technique .2 Nesterov’s Accelerated Gradient Method .2 Generalized Fermat-Torricelli Problems Involving Points .2 Additional Work: Location Problems involving Sets .3 Multifacility Location Problems and Non-convex Optimization .1 Introduction to Multifacility Location.2 Tools of DC Programming .3 The DCA for a Generalized Multifacility Location Problem .6 Additional Work: Set Clustering. 86 4 Applications to Electric Power Systems .1 Transactive Energy Systems .3 The Optimization Problem .3 Variables and Parameters .4 Objective Function Intuition .5 Details on the energy sales revenue function h.6 An analytic solution for h.8 Optimization Problem Statement.1 Significance of this Research.

128 v List of Tables Table 3.1 Results for Example 6.3, the performance of Algorithm 5 on real data sets. 85 vi List of Figures Figure 1.1 Electricity demand in California on a hot day.1 The set-valued map G.2 The objective function ψ.3 The resulting optimal value function µ.1 Polyellipses with three foci.2 Generalized Fermat-Torricelli problems with different norms.3 The first steps of an application of the MM principle for a generalized Fermat-Torricelli problem with sets. The initial guess x0 is projected onto the sets and the Fermat-Torricelli problem is solved using those points as the targets, resulting in the next iterate x1 .4 A generalized Fermat-Torricelli problem in R2. Each negative point has weight of -1000; each positive point has a weight of 1; the optimal solution is represented by • for the `1 norm.5 The objective function values for Algorithm 4 for the generalized Fermat-Torricelli problem under the `1 norm shown in Figure 3.6 The solution to the multifacility location problem with three centers and Euclidean distance to 1217 US Cities.

A line connects each city with its closest center.7 The fifty most populous US cities, approximated by a ball proportional to their area. Each city is assigned to the closest of five centroids (•), which are the optimal facilities.1 PV Panel, Battery, and Smart Solar Inverter diagram.2 The energy sales revenue function h is the maximum of f over the feasible region. The graph of f is shown with the example input values ai = 15 ($/MWh), bi = 2.3 Typical charge and discharge behavior can be seen over the 3-day period June 20-22, 2015.4 Battery charge, solar irradiance, and energy purchased over the 3-day period June 20-22, 2015.5 Price of energy and spinning reserve over the 3-day period June 20-22, 2015. 115 viii 1 Introduction “Waste not, want not” goes the old saying.

If you use a resource wisely, you will never be in need. In this phrase lie the seeds of optimization. This thesis concerns generalized differential calculus and applications of optimization to location problems and electric power systems. Let us begin with a brief discussion of the key terms in this sentence.

Generalized differential calculus is a generalization of classical calculus. In particular, this includes the study of generalized notions of derivatives for nonsmooth functions and set-valued mappings. These topics generally fall under the subject of variational or nonsmooth analysis. The term convex analysis is used when such a study is restricted to functions that are convex.

Optimization problems ask for the best solution from a given set of feasible solutions; such problems are ubiquitous in applied science, business, engineering, economics, social sciences and everyday life. Optimization is the process by which solutions to optimization problems are found. Recently, nonsmooth analysis and optimization have become increasingly important for applications to many new fields such as computational statistics, machine learning, and sparse optimization. The work in this dissertation provides a more complete pic- ture of generalized differentiation and develops nonsmooth optimization methods to solve facility location problems.

The optimization techniques and methods developed significantly contribute to the field of variational analysis and nonsmooth optimiza- tion as well as their applications. In addition, the applications of optimization to 1 electric power systems developed here will play an important role in the evolution of modern energy markets and responsive electric grids. Collectively, this work develops theory, numerical methods, and a practical solution, all related to optimization. Convex Analysis, Nonsmooth Analysis, and Variational Analysis.

Inspired by Fenchel [18], in the 1960’s Rockafellar [66] and Moreau [45] independently laid the groundwork for the field of convex analysis with their development of the idea of the subdifferential. The subdifferential generalizes the idea of the derivative in classical calculus from differentiable functions to functions that are convex but not necessarily differentiable. The subdifferential of a convex function is a set, rather than a single value as in the classical case. Related to the subdifferential, the geometric idea of the normal cone to a convex set goes back to Minkowski [37].

Before Rockafellar and Moreau, generalized differentiation ideas had been discussed in mathematics and applied sciences, for example by Saks [70] and Sobelev [75]. However, these generalized derivatives “ignore sets of measure zero” and hence are not useful in optimization theory, where the behavior of functions at individual points is of critical importance. Convex analysis contains the theoretical framework for the numerical methods of convex optimization. The presence of convexity makes it possible not only to comprehensively investigate qualitative properties of optimal solutions and derive necessary and sufficient conditions for optimality but also to develop effective numerical algorithms for solving convex optimization problems, even with nondifferentiable objective functions.

Convex analysis and convex optimization have an increasing impact on many areas of mathematics and applications including automatic control systems, estimation and signal processing, communications and networks, electronic circuit design, data analysis and modeling, statistics, machine learning, economics and finance. 2 The beauty and applications of convex analysis motivated the search for a new theory to deal with broader classes of functions and sets where convexity is not assumed. This search has been the inspiration for the devel- opments of variational analysis, also known Variational Analysis / Nonsmooth Analysis as nonsmooth analysis, initiated in the early 1970’s. Variational analysis has now become a well-developed field with many applications, Convex Analysis especially to optimization theory; see the cor- nerstone references [9, 38, 64, 65] for more history and recent developments of the field.

Optimization is the process by which solutions to opti- mization problems are found. In mathematics, an optimization problem includes three things: an objective function, a constraint set, and a desired outcome. For example, if f : Rn → R, then an optimization problem can be stated as: minimize f (x) subject to x ∈ C ⊂ Rn. This means: find the function input x̄ ∈ C such that f (x̄) ≤ f (x) for all x ∈ C.

Such an x̄ would be called a solution to the optimization problem. If f is a convex function and C is a convex set, then the optimization problem is a convex optimization problem. Optimization problems may be further delineated by the nature of the objective function as differentiable (smooth) or non-differentiable (nonsmooth). The latter types of objective functions are of particular interest in convex optimization.

In practice, optimization problems are often so complicated that they cannot be solved exactly with analytic methods. In these cases, a computer program can be written 3 to employ an optimization algorithm to find an approximate solution. Optimization algorithms are typically iterative procedures that start with an initial guess x0 for the solution and update that guess based on the logic provided by the algorithm. In this way, a sequence of function inputs x0 , x1 , x2 ,.

is derived that converges to the solution x̄. The optimization algorithms developed in this thesis utilize the theory from convex, nonsmooth or variational analysis. The field of operations research applies optimization to solve practical problems from industry or logistics. Location problems are among the oldest class of problems studied in operations research, and are discussed in detail in this dissertation.

Electric Power Systems. The generation, transmission, distribution and consumption of electric power has shown itself to be an essential part of modern life. Despite some incremental improvements, the electric power system in the year 2000 was essen- tially the same as the electric power system originally built in the early 1900s. The opera- tion of this historical legacy sys- tem was straight forward: build large enough generation, trans- LBNL mission and distribution facili- ties so that consumer peak de- Figure 1.

Electricity demand in California on mand can be met by increas- a hot day. ing or decreasing generation as needed. Consumer demand for electricity varies throughout the day; it is not uncom- mon for peak demand to be twice that of minimum demand over a 24 hour period. 4 In recent decades, two major advances have caused system planners and operators to rethink this legacy electric power system.

These advances are (1) the significant (and rapidly increasing) presence of “variable generation” such as wind and solar, and (2) the advent of distributed energy resources, including rooftop solar, storage, and “controllable loads”, that is, devices that have some flexibility in how much and when they consume power, such as smart appliances, thermostats, heating and cooling systems, other types of demand response, and electric vehicles. This new paradigm provides a natural opportunity for optimization, including the minimization of system cost, the maximization of revenue for individual participants, or the minimization of emissions. Overview of Research. The research presented in this thesis is generally organized into Chapters 2, 3, and 4 as follows: • Chapter 2: Use the optimal value function and coderivatives to establish subdifferential formulas in locally convex topological vector spaces.

Develop formulas for coderivatives in infinite dimensions. • Chapter 3: Apply nonsmooth optimization techniques to location problems: – Apply Nesterov’s smoothing technique and accelerated gradient method to facility location problems.