Gradient descent and related algorithms are ubiquitously used to solve optimization problems arising in machine learning and signal processing. In many cases, these problems are nonconvex yet such simple algorithms are still effective. In an attempt to better understand this phenomenon, we study a number of nonconvex problems, proving that they can be solved efficiently with gradient descent. We will consider complete, orthogonal dictionary learning, and present a geometric analysis allowing us to obtain efficient convergence rate for gradient descent that hold with high probability. We also show that similar geometric structure is present in other nonconvex problems such as generalized phase retrieval. Turning next to neural networks, we will also calculate conditions on certain classes of networks under which signals and gradients propagate through the network in a stable manner during the initial stages of training. Initialization schemes derived using these calculations allow training recurrent networks on long sequence tasks, and in the case of networks with low precision activation functions they make explicit a tradeoff between the reduction in precision and the maximal depth of a model that can be trained with gradient descent. We finally consider manifold classification with a deep feed-forward neural network, for a particularly simple configuration of the manifolds. We provide an end-to-end analysis of the training process, proving that under certain conditions on the architectural hyperparameters of the network, it can successfully classify any point on the manifolds with high probability given a sufficient number of independent samples from the manifold, in a timely manner. Our analysis relates the depth and width of the network to its fitting capacity and statistical regularity respectively in early stages of training.

M. Tech. Electrical Engineering. / This study proposes a mathematical optimisation approach which invokes Genetic Algorithm (GA) for initialisation and application of Tabu Search (TS) algorithm in finding the sites of node Bs in the network to enable it have the potential to support an increased number of users requiring the increased number of services. The global optimisation can be obtained in terms of great probability as GA is applied to global search and TS is applied to the local search. The particular memory ability of TS can be integrated to GA and the prematurity of GA can be avoided by virtue of the hill-climbing ability of TS. The problem to be addressed is the determination of optimal locations of node Bs in the network based on the user distribution, while improving the QoS. The proposed approach considers the site selection as an integer problem and the site placement as a continuous problem. The two problems are focused on concurrently - finding the optimal number of node Bs that satisfies the capacity requirements in the network and hence QoS improvement. The proposed algorithm combines the strength of Genetic and Tabu Search algorithms in successive elimination of node Bs after their random distribution in the area of study. The results showed that the proposed approach produced fewer number of node Bs sites in the network that provided the required QoS. In addition, it exhibited high fitness function in the simulations meaning that it has the higher ability of achieving the objective function when it was compared to TS and GA.

In many applications nonsmooth nonconvex energy functions, which are Lipschitz continuous, appear quite naturally. Contact mechanics with friction is a classic example. A second example is the 1-Laplace operator and its eigenfunctions. In this work we will give an algorithm such that for every locally Lipschitz continuous function f and every sequence produced by this algorithm it holds that every accumulation point of the sequence is a critical point of f in the sense of Clarke. Here f is defined on a reflexive Banach space X, such that X and its dual space X' are strictly convex and Clarkson's inequalities hold. (E.g. Sobolev spaces and every closed subspace equipped with the Sobolev norm satisfy these assumptions for p>1.) This algorithm is designed primarily to solve variational problems or their high dimensional discretizations, but can be applied to a variety of locally Lipschitz functions. In elastic contact mechanics the strain energy is often smooth and nonconvex on a suitable domain, while the contact and the friction energy are nonsmooth and have a support on a subspace which has a substantially smaller dimension than the strain energy, since all points in the interior of the bodies only have effect on the strain energy. For such elastic contact problems we suggest a specialization of our algorithm, which treats the smooth part with Newton like methods. In the case that the gradient of the entire energy function is semismooth close to the minimizer, we can even prove superlinear convergence of this specialization of our algorithm. We test the algorithm and its specialization with a couple of benchmark problems. Moreover, we apply the algorithm to the 1-Laplace minimization problem restricted to finitely dimensional subspaces of piecewise affine, continuous functions. The algorithm developed here uses ideas of the bundle trust region method by Schramm, and a new generalization of the concept of gradients on a set. The basic idea behind this gradients on sets is that we want to find a stable descent direction, which is a descent direction on an entire neighborhood of an iteration point. This way we avoid oscillations of the gradients and very small descent steps (in the smooth and in the nonsmooth case). It turns out, that the norm smallest element of the gradient on a set provides a stable descent direction. The algorithm we present here is the first algorithm which can treat locally Lipschitz continuous functions in this generality, up to our knowledge. In particular, large finitely dimensional Banach spaces haven't been studied for nonsmooth nonconvex functions so far. We will show that the algorithm is very robust and often faster than common algorithms. Furthermore, we will see that with this algorithm it is possible to compute reliably the first eigenfunctions of the 1-Laplace operator up to disretization errors, for the first time. / In vielen Anwendungen tauchen nichtglatte, nichtkonvexe, Lipschitz-stetige Energie Funktionen in natuerlicher Weise auf. Ein klassische Beispiel bildet die Kontaktmechanik mit Reibung. Ein weiteres Beispiel ist der $1$-Laplace Operator und seine Eigenfunktionen. In dieser Dissertation werden wir ein Abstiegsverfahren angeben, so dass fuer jede lokal Lipschitz-stetige Funktion f jeder Haeufungspunkt einer durch dieses Verfahren erzeugten Folge ein kritischer Punkt von f im Sinne von Clarke ist. Hier ist f auf einem einem reflexiver, strikt konvexem Banachraum definierert, fuer den der Dualraum ebenfalls strikt konvex ist und die Clarkeson Ungleichungen gelten. (Z.B. Sobolevraeume und jeder abgeschlossene Unterraum mit der Sobolevnorm versehen, erfuellt diese Bedingung fuer p>1.) Dieser Algorithmus ist primaer entwickelt worden um Variationsprobleme, bzw. deren hochdimensionalen Diskretisierungen zu loesen. Er kann aber auch fuer eine Vielzahl anderer lokal Lipschitz stetige Funktionen eingesetzt werden. In der elastischen Kontaktmechanik ist die Spannungsenergie oft glatt und nichtkonvex auf einem geeignetem Definitionsbereich, waehrend der Kontakt und die Reibung durch nicht glatte Funktionen modelliert werden, deren Traeger ein Unterraum mit wesentlich kleineren Dimension ist, da alle Punkte im Inneren des Koerpers nur die Spannungsenergie beeinflussen. Fuer solche elastischen Kontaktprobleme schlagen wir eine Spezialisierung unseres Algorithmuses vor, der den glatten Teil mit Newton aehnlichen Methoden behandelt. Falls der Gradient der gesamten Energiefunktion semiglatt in der Naehe der Minimalstelle ist, koennen wir sogar beweisen, dass der Algorithmus superlinear konvergiert. Wir testen den Algorithmus und seine Spezialisierung an mehreren Benchmark Problemen. Ausserdem wenden wir den Algorithmus auf 1-Laplace Minimierungsproblem eingeschraenkt auf eine endlich dimensionalen Unterraum der stueckweise affinen, stetigen Funktionen an. Der hier entwickelte Algorithmus verwendet Ideen des Bundle-Trust-Region-Verfahrens von Schramm, und einen neu entwickelten Verallgemeinerung von Gradienten auf Mengen. Die zentrale Idee hinter den Gradienten auf Mengen ist die, dass wir stabile Abstiegsrichtungen auf einer ganzen Umgebung der Iterationspunkte finden wollen. Auf diese Weise vermeiden wir das Oszillieren der Gradienten und sehr kleine Abstiegsschritte (im glatten, wie im nichtglatten Fall.) Es stellt sich heraus, dass das normkleinste Element dieses Gradienten auf der Umgebung eine stabil Abstiegsrichtung bestimmt. So weit es uns bekannt ist, koennen die hier entwickelten Algorithmen zum ersten Mal lokal Lipschitz-stetige Funktionen in dieser Allgemeinheit behandeln. Insbesondere wurden nichtglatte, nichtkonvexe Funktionen auf derart hochdimensionale Banachraeume bis jetzt nicht behandelt. Wir werden zeigen, dass unser Algorithmus sehr robust und oft schneller als uebliche Algorithmen ist. Des Weiteren, werden wir sehen, dass es mit diesem Algorithmus das erste mal moeglich ist, zuverlaessig die erste Eigenfunktion des 1-Laplace Operators bis auf Diskretisierungsfehler zu bestimmen.

In many applications nonsmooth nonconvex energy functions, which are Lipschitz continuous, appear quite naturally. Contact mechanics with friction is a classic example. A second example is the 1-Laplace operator and its eigenfunctions. In this work we will give an algorithm such that for every locally Lipschitz continuous function f and every sequence produced by this algorithm it holds that every accumulation point of the sequence is a critical point of f in the sense of Clarke. Here f is defined on a reflexive Banach space X, such that X and its dual space X' are strictly convex and Clarkson's inequalities hold. (E.g. Sobolev spaces and every closed subspace equipped with the Sobolev norm satisfy these assumptions for p>1.) This algorithm is designed primarily to solve variational problems or their high dimensional discretizations, but can be applied to a variety of locally Lipschitz functions. In elastic contact mechanics the strain energy is often smooth and nonconvex on a suitable domain, while the contact and the friction energy are nonsmooth and have a support on a subspace which has a substantially smaller dimension than the strain energy, since all points in the interior of the bodies only have effect on the strain energy. For such elastic contact problems we suggest a specialization of our algorithm, which treats the smooth part with Newton like methods. In the case that the gradient of the entire energy function is semismooth close to the minimizer, we can even prove superlinear convergence of this specialization of our algorithm. We test the algorithm and its specialization with a couple of benchmark problems. Moreover, we apply the algorithm to the 1-Laplace minimization problem restricted to finitely dimensional subspaces of piecewise affine, continuous functions. The algorithm developed here uses ideas of the bundle trust region method by Schramm, and a new generalization of the concept of gradients on a set. The basic idea behind this gradients on sets is that we want to find a stable descent direction, which is a descent direction on an entire neighborhood of an iteration point. This way we avoid oscillations of the gradients and very small descent steps (in the smooth and in the nonsmooth case). It turns out, that the norm smallest element of the gradient on a set provides a stable descent direction. The algorithm we present here is the first algorithm which can treat locally Lipschitz continuous functions in this generality, up to our knowledge. In particular, large finitely dimensional Banach spaces haven't been studied for nonsmooth nonconvex functions so far. We will show that the algorithm is very robust and often faster than common algorithms. Furthermore, we will see that with this algorithm it is possible to compute reliably the first eigenfunctions of the 1-Laplace operator up to disretization errors, for the first time. / In vielen Anwendungen tauchen nichtglatte, nichtkonvexe, Lipschitz-stetige Energie Funktionen in natuerlicher Weise auf. Ein klassische Beispiel bildet die Kontaktmechanik mit Reibung. Ein weiteres Beispiel ist der $1$-Laplace Operator und seine Eigenfunktionen. In dieser Dissertation werden wir ein Abstiegsverfahren angeben, so dass fuer jede lokal Lipschitz-stetige Funktion f jeder Haeufungspunkt einer durch dieses Verfahren erzeugten Folge ein kritischer Punkt von f im Sinne von Clarke ist. Hier ist f auf einem einem reflexiver, strikt konvexem Banachraum definierert, fuer den der Dualraum ebenfalls strikt konvex ist und die Clarkeson Ungleichungen gelten. (Z.B. Sobolevraeume und jeder abgeschlossene Unterraum mit der Sobolevnorm versehen, erfuellt diese Bedingung fuer p>1.) Dieser Algorithmus ist primaer entwickelt worden um Variationsprobleme, bzw. deren hochdimensionalen Diskretisierungen zu loesen. Er kann aber auch fuer eine Vielzahl anderer lokal Lipschitz stetige Funktionen eingesetzt werden. In der elastischen Kontaktmechanik ist die Spannungsenergie oft glatt und nichtkonvex auf einem geeignetem Definitionsbereich, waehrend der Kontakt und die Reibung durch nicht glatte Funktionen modelliert werden, deren Traeger ein Unterraum mit wesentlich kleineren Dimension ist, da alle Punkte im Inneren des Koerpers nur die Spannungsenergie beeinflussen. Fuer solche elastischen Kontaktprobleme schlagen wir eine Spezialisierung unseres Algorithmuses vor, der den glatten Teil mit Newton aehnlichen Methoden behandelt. Falls der Gradient der gesamten Energiefunktion semiglatt in der Naehe der Minimalstelle ist, koennen wir sogar beweisen, dass der Algorithmus superlinear konvergiert. Wir testen den Algorithmus und seine Spezialisierung an mehreren Benchmark Problemen. Ausserdem wenden wir den Algorithmus auf 1-Laplace Minimierungsproblem eingeschraenkt auf eine endlich dimensionalen Unterraum der stueckweise affinen, stetigen Funktionen an. Der hier entwickelte Algorithmus verwendet Ideen des Bundle-Trust-Region-Verfahrens von Schramm, und einen neu entwickelten Verallgemeinerung von Gradienten auf Mengen. Die zentrale Idee hinter den Gradienten auf Mengen ist die, dass wir stabile Abstiegsrichtungen auf einer ganzen Umgebung der Iterationspunkte finden wollen. Auf diese Weise vermeiden wir das Oszillieren der Gradienten und sehr kleine Abstiegsschritte (im glatten, wie im nichtglatten Fall.) Es stellt sich heraus, dass das normkleinste Element dieses Gradienten auf der Umgebung eine stabil Abstiegsrichtung bestimmt. So weit es uns bekannt ist, koennen die hier entwickelten Algorithmen zum ersten Mal lokal Lipschitz-stetige Funktionen in dieser Allgemeinheit behandeln. Insbesondere wurden nichtglatte, nichtkonvexe Funktionen auf derart hochdimensionale Banachraeume bis jetzt nicht behandelt. Wir werden zeigen, dass unser Algorithmus sehr robust und oft schneller als uebliche Algorithmen ist. Des Weiteren, werden wir sehen, dass es mit diesem Algorithmus das erste mal moeglich ist, zuverlaessig die erste Eigenfunktion des 1-Laplace Operators bis auf Diskretisierungsfehler zu bestimmen.

<p> This work focuses on solving the general optimal control problems with smart-learning-enabled and theory-supported optimal control (SET-OC) approaches. The proposed SET-OC includes two main directions. Firstly, according to the basic idea of the direct method, the smart-learning-enabled iterative optimization algorithm (SEIOA) is proposed for solving discrete optimal control problems. Via discretization and reformulation, the optimal control problem is converted into a general quadratically constrained quadratic programming (QCQP) problem. Then, the SEIOA is applied to solving QCQPs. To be specific, first, a structure-exploiting decomposition scheme is introduced to reduce the complexity of the original problem. Next, an iterative search, combined with an intersection-cutting plane, is developed to achieve global convergence. Furthermore, considering the implicit relationship between the algorithmic parameters and the convergence rate of the iterative search, deep learning is applied to design the algorithmic parameters from an appropriate amount of training data to improve convergence property. To demonstrate the effectiveness and improved computational performance of the proposed SEIOA, the developed algorithms have been implemented in extensive real-world application problems, including unmanned aerial vehicle path planning problems and general QCQP problems. According to the theoretical analysis of global convergence and the simulation results, the efficiency, robustness, and improved convergence rate of the optimization framework compared to the state-of-the-art optimization methods for solving general QCQP problems are analyzed and verified. Secondly, the onboard learning-based optimal control method (L-OCM) is proposed to solve the optimal control problems. Supported by the optimal control theory, the necessary conditions of optimality for optimal control of the optimal control problem can be derived, which leads to two two-point-boundary-value-problems (TPBVPs). Then, critical parameters are identified to approximate the complete solutions of the TPBVPs. To find the implicit relationship between the initial states and these critical parameters, deep neural networks are constructed to learn the values of these critical parameters in real-time with training data obtained from the offline solutions.  To demonstrate the effectiveness and improved computational performance of the proposed L-OCM approaches, the developed algorithms have been implemented in extensive real-world application problems, including two-dimensional human-Mars entry, powered-descent, landing guidance problems, and fuel-optimal powered descent guidance (PDG) problems. In addition, considering there is no thorough analysis of the properties of the optimal control profile for PDG when considering the state constraints, a rigid theoretical analysis of the fuel-optimal PDG problem with state constraints is further provided. According to the theoretical analysis and simulation results, the optimality, robustness, and real-time performance of the proposed L-OCM are analyzed and verified, which indicates the potential for onboard implementation. </p>