Our aim in this research was to study monotone operators in Banach spaces. In particular, the most important concept in this theory, the maximal monotone operators. Here we make an attempt to describe most of the important results and concepts on maximal monotone operators and how they all tie together. We will take a brief look at subdifferentials, which generalize the notion of a derivative. The subdifferential is a maximal monotone operator and it has proved to be of fundamental importance for the study of maximal monotone operators. The theory of maximal monotone operators is somewhat complete in reflexive Banach spaces. However, in nonreflexive Banach spaces it is still to be developed fully. As such, here we will describe most of the important results about maximal monotone operators in Banach spaces and we will distinguish between the reflexive Banach spaces and nonreflexive Banach spaces when a property is known to hold only in reflexive Banach spaces. In the latter case, we will state what the corresponding situation is in nonreflexive Banach spaces and we will give counter examples whenever such a result is known to fail in nonreflexive Banach spaces. The representations of monotone operators by convex functions have found to be extremely useful for the study of maximal monotone operators and it has generated a lot of interest of late. We will discuss some of those key representations and their properties. We will also demonstrate how these representations could be utilized to obtain results about maximal monotone operators. We have included a discussion about the very important Rockafellar sum theorem and some its generalizations. This key result and its generalizations have only been proved in reflexive Banach spaces. We will also discuss several special cases where the Rockafellar sum theorem is known to be true in nonreflexive Banach spaces. The subclasses which provide a basis for the study of monotone operators in nonreflexive Banach spaces are also discussed here

No description available.

Includes bibliographical references (p. 55-57).

Alon 和Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) 證明了如果一個圖是ε -非二部圖，那麼階數為Ỡ(1/ε) 的隨機導出于圖以很大概率是非二部圖。我們進一步猜想，這個導出子圖以很大概率是Ω(ε)-非二部圖。Gonen 和Ron (RANDOM 2007) 證明了當圖的最大度不超過O (εn )時猜想成立。我們將對更一般的情形給出證明，對於任意d，所有d 正則(或幾乎d 正則)的圖猜想成立。 / 假設猜想成立的情況下，我們證明二分屬性是可以被單側誤差在O(1/ε^c ) 時間內檢驗的，其中c 是一個嚴格小於2 的常數，而這個結果也改進了Alon 和Krivelevich 的檢驗算法。由於己知對二分屬性的非適應性的檢驗算法需要Ω(1 /ε²) 的複雜性(Bogdanov 和Trevisan ， CCC 2004) ，我們的結果也得出，假設猜想成立，適應性對檢驗二分屬性是有幫助的。 / 另外一個有很多屬性檢驗問題被廣泛研究的領域是布爾函數。對布爾函數單調性的檢驗也是屬性檢驗的經典問題。給定對布爾函數f: {0,1}{U+207F} → {0,1} 的訪問，在[18]中，證明了檢驗算法複雜性的下界是Ω(√n) 。另一方面，在[21]中，作者們構造了一個複雜性為O(n) 的算法。在本文中，我們刻畫一些單調布爾函數的本質，設計算法并分析其對於一些困難例子的效果。最近，在[14] 中， 一個類似的算法被證明是非適應性，單側誤差，複雜性為Ỡ (n⁵/⁶ ε⁻⁵/³) 的算法。 / Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is ε-far from bipartite, then the subgraph induced by a random subset of Ỡ (1/ε) vertices is not bipartite with high probability. We conjecture that the induced subgraph is Ω(ε)-far from bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this conjecture in the case when the degrees of all vertices are at most O(εn). We give a more general proof that works for any d-regular (or almost d-regular) graph for arbitrary degree d. / Assuming this conjecture, we prove that bipartiteness is testable with one-sided error in time O(1=ε{U+1D9C}), where c is a constant strictly smaller than two, improving upon the tester of Alon and Krivelevich. As it is known that non-adaptive testers for bipartiteness require Ω(1/ε²) queries (Bogdanov and Trevisan, CCC2004), our result shows, assuming the conjecture, that adaptivity helps in testing bipartiteness. / The other area in which various properties have been well studied is boolean function. Testing monotonicity of Boolean functions is a classical question in property testing. Given oracle access to a Boolean function f : {0, 1}{U+207F} →{0, 1}, in [18], it is shown a lower bound of testing is Ω(√n). On the other hand, in [21], the authors introduced an algorithm to test monotonicity using O(n) queries. In this paper, we characterize some nature of monotone functions, design a tester and analyze the performance on some generalizations of the hard case. Recently, in [14], a similar tester is shown to be a non-adaptive, one-sided error tester making Ỡ (n⁵/⁶ ε⁻⁵/³) queries. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Fan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 76-79). / Abstracts also in Chinese. / Abstract --- p.i / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Property Testing --- p.1 / Chapter 1.2 --- Testing Bipartiteness --- p.4 / Chapter 1.3 --- Testing Monotonicity --- p.7 / Chapter 2 --- Testing Bipartiteness --- p.11 / Chapter 2.1 --- Background --- p.11 / Chapter 2.1.1 --- Our result --- p.11 / Chapter 2.1.2 --- The algorithms of Gonen and Ron --- p.13 / Chapter 2.1.3 --- Our proof --- p.16 / Chapter 2.1.4 --- Notation --- p.19 / Chapter 2.2 --- Splitting the vertices by degree --- p.19 / Chapter 2.3 --- The algorithm for high degree vertices --- p.20 / Chapter 2.4 --- Eliminating the high degree vertices --- p.22 / Chapter 2.5 --- From an XOR game to a bipartite graph --- p.33 / Chapter 2.6 --- Proof of the main theorem --- p.35 / Chapter 2.7 --- Proof of the conjecture for regular graphs --- p.37 / Chapter 3 --- Testing Monotonicity --- p.40 / Chapter 3.1 --- Towards an improved tester --- p.40 / Chapter 3.1.1 --- Properties of Distribution D --- p.42 / Chapter 3.1.2 --- An Alternative Representation of D --- p.46 / Chapter 3.1.3 --- Performance of D on Decreasing Functions --- p.51 / Chapter 3.1.4 --- Functions Containing Ω(2{U+207F}) Disjoint Violating Edges --- p.54 / Chapter 3.2 --- A o(n) Monotonicity Tester [14] and Some Improvements --- p.62 / Chapter 3.2.1 --- A o(n) Monotonicity Tester [14] --- p.62 / Chapter 3.2.2 --- An Alternative Proof of Theorem 3.2.2 --- p.65 / Chapter 4 --- Other Related Results --- p.67 / Chapter 4.1 --- Short Odd Cycles in Graphs that are Far From Bipartiteness --- p.67 / Chapter 4.2 --- Fourier Analysis on Boolean Functions --- p.69 / Bibliography --- p.76

Mean-field games (MFGs) model the behavior of large populations of rational agents. Each agent seeks to minimize an individual cost that depends on the statistical distribution of the population. Roughly speaking, MFGs are given by the limit of differential games with N agents as N goes to infinity. This limit describes an average effect of the population’s behavior. Instead of modeling large systems for all agents, we consider two coupled equations: the Hamilton–Jacobi equation and the Fokker–Planck equation. A solution to MFGs is given by two functions: a value function and a population density. From the point of view of mathematics, monotonicity conditions for MFGs are a natural way to obtain the uniqueness of solutions and the stability of systems. In this thesis, we develop a new framework to establish the existence of solutions to MFGs through monotonicity. First, we study first-order stationary monotone MFGs with Dirichlet boundary conditions. In MFGs, boundary conditions arise when agents can leave the domain. There are exit costs for agents given by Dirichlet boundary conditions. Here, we establish the existence of solutions to MFGs that fulfill those boundary conditions in the trace sense. In particular, our solution is continuous up to the boundary in the one-dimensional case. Second, we consider time-dependent monotone MFGs with space-periodic boundary conditions. To solve the time-dependent monotone MFG, we introduce a mono- tone high-order regularized elliptic problem in Rn+1, although the original MFG is a parabolic type. To preserve monotonicity, we need to determine the specific boundary conditions for the time variable. Then, we can apply our method of stationary MFGs to this regularization. In particular, we prove that a solution to the problem exists for any terminal time. Third, we investigate stationary MFGs with hypoelliptic operators that are degenerate differential operators. Those models arise from stochastic control problems with the Stratonovich integration. We study a hypoelliptic MFG with the standard quadratic Hamiltonian. Under standard assumptions, although there is no uniform elliptic condition in hypoelliptic operators, we verify that there is a unique solution to our hypoelliptic MFG.

In this thesis, we report recent results on existence for complementarity problems in infinite-dimensional spaces under generalized monotonicity are reported.

Doctor of Philosophy / Department of Mathematics / Alexander G. Ramm / Several methods for a stable solution to the equation $F(u)=f$ have been developed. Here $F:H\to H$ is an operator in a Hilbert space $H$, and we assume that noisy data $f_\delta$, $\|f_\delta-f\|\le \delta$, are given in place of the exact data $f$. When $F$ is a linear bounded operator, two versions of the Dynamical Systems Method (DSM) with stopping rules of Discrepancy Principle type are proposed and justified mathematically. When $F$ is a non-linear monotone operator, various versions of the DSM are studied. A Discrepancy Principle for solving the equation is formulated and justified. Several versions of the DSM for solving the equation are formulated. These methods consist of a Newton-type method, a gradient-type method, and a simple iteration method. A priori and a posteriori choices of stopping rules for these methods are proposed and justified. Convergence of the solutions, obtained by these methods, to the minimal norm solution to the equation $F(u)=f$ is proved. Iterative schemes with a posteriori choices of stopping rule corresponding to the proposed DSM are formulated. Convergence of these iterative schemes to a solution to the equation $F(u)=f$ is proved. This dissertation consists of six chapters which are based on joint papers by the author and his advisor Prof. Alexander G. Ramm. These papers are published in different journals. The first two chapters deal with equations with linear and bounded operators and the last four chapters deal with non-linear equations with monotone operators.

The aim of this work is to present several new results concerning duality in scalar convex optimization, the formulation of sequential optimality conditions and some applications of the duality to the theory of maximal monotone operators. After recalling some properties of the classical generalized interiority notions which exist in the literature, we give some properties of the quasi interior and quasi-relative interior, respectively. By means of these notions we introduce several generalized interior-point regularity conditions which guarantee Fenchel duality. By using an approach due to Magnanti, we derive corresponding regularity conditions expressed via the quasi interior and quasi-relative interior which ensure Lagrange duality. These conditions have the advantage to be applicable in situations when other classical regularity conditions fail. Moreover, we notice that several duality results given in the literature on this topic have either superfluous or contradictory assumptions, the investigations we make offering in this sense an alternative. Necessary and sufficient sequential optimality conditions for a general convex optimization problem are established via perturbation theory. These results are applicable even in the absence of regularity conditions. In particular, we show that several results from the literature dealing with sequential optimality conditions are rediscovered and even improved. The second part of the thesis is devoted to applications of the duality theory to enlargements of maximal monotone operators in Banach spaces. After establishing a necessary and sufficient condition for a bivariate infimal convolution formula, by employing it we equivalently characterize the $\varepsilon$-enlargement of the sum of two maximal monotone operators. We generalize in this way a classical result concerning the formula for the $\varepsilon$-subdifferential of the sum of two proper, convex and lower semicontinuous functions. A characterization of fully enlargeable monotone operators is also provided, offering an answer to an open problem stated in the literature. Further, we give a regularity condition for the weak$^*$-closedness of the sum of the images of enlargements of two maximal monotone operators. The last part of this work deals with enlargements of positive sets in SSD spaces. It is shown that many results from the literature concerning enlargements of maximal monotone operators can be generalized to the setting of Banach SSD spaces.

Thesis (Ph. D.)--University of Washington, 1999. / Vita. Includes bibliographical references (p. 85-91).

[pt] Diversos problemas em engenharia, aprendizado de máquina e economia podem ser resolvidos através de Programação Semidefinida (SDP). Potenciais aplicações podem ser encontradas em telecomunicações, fluxo de potência e teoria dos jogos. Além disso, como SDP é uma subclasse de otimização convexa, temos uma série de propriedades e garantias que fazem da SDP uma tecnologia muito poderosa. Entretanto, dentre as diferentes subclasses de otimização convexa, SDP ainda permanece como uma das mais desafiadoras. Instancias de larga escala ainda não podem ser resolvidas pelos atuais softwares disponíveis. Nesse sentido, esta tese porpõe um novo algoritmo para resolver problemas de SDP. A principal contribuição deste novo algoritmo é explorar a propriedade de posto baixo presente em diversas instancias. A convergência desta nova metodologia é provada ao mostrar que o algoritmo proposto é um caso particular do Approximate Proximal Point Algorithm. Adicionalmente, as variáveis ótimas duais são disponibilizadas como uma consequência do algoritmo proposto. Além disso, disponibilizamos um software para resolver problemas de SDP, chamado ProxSDP. Três estudos de caso são utilizados para avaliar a performance do algoritmo proposto. / [en] Many problems of interest can be solved by means of Semidefinite Programming (SDP). The potential applications range from telecommunications, electrical power systems, game theory and many more fields. Additionally, the fact that SDP is a subclass of convex optimization brings a set of theoretical guarantees that makes SDP very appealing. However, among all sub-classes of convex optimization, SDP remains one of the most challenging in practice. State-of-the-art semidefinite programming solvers still do not efficiently solve large scale instances. In this regard, this thesis proposes a novel algorithm for solving SDP problems. The main contribution of this novel algorithm is to achieve a substantial speedup by exploiting the low-rank property inherent to several SDP problems. The convergence of the new methodology is proved by showing that the novel algorithm reduces to a particular case of the Approximated Proximal Point Algorithm. Along with the theoretical contributions, an open source numerical solver, called ProxSDP, is made available with this work. The performance of ProxSDP in comparison to state-of-the-art SDP solvers is evaluated on three case studies.