After introducing concepts from convex analysis, we study how to continuously transform one convex function into another. A natural choice is the arithmetic average, as it is pointwise continuous; however, this choice fails to average functions with different domains. On the contrary, the proximal average is not only continuous (in the epi-topology) but can actually average functions with disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic average) but also inherits smoothness and differentiability (unlike the arithmetic average). Then we introduce a computational framework for computer-aided convex analysis. Motivated by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope. As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit convex hull algorithm. Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions [5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12, p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can be formulated as shortest path problems.

Submitted by Mariana Rodrigues Barbosa dos Santos null (mariana.rsb@gmail.com) on 2016-08-03T17:28:29Z No. of bitstreams: 1 Mariana Rodrigues Barbosa dos Santos.pdf: 3047570 bytes, checksum: bd1b89dc57eeef6047e27fce6c4c698d (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-08-05T17:13:55Z (GMT) No. of bitstreams: 1 santos_mrb_me_bauru.pdf: 3047570 bytes, checksum: bd1b89dc57eeef6047e27fce6c4c698d (MD5) / Made available in DSpace on 2016-08-05T17:13:55Z (GMT). No. of bitstreams: 1 santos_mrb_me_bauru.pdf: 3047570 bytes, checksum: bd1b89dc57eeef6047e27fce6c4c698d (MD5) Previous issue date: 2016-06-08 / O problema multiobjetivo de despacho econômico e ambiental envolve a minimização de dois objetivos conflitantes: o custo de geração em uma unidade térmica e a emissão de poluentes. Quando a função objetivo custo de geração inclui os efeitos de pontos de carregamento de válvula, esta torna-se não convexa e, além disso, não diferenciável, pois termos modulares que envolvem a função seno são considerados, impossibilitando que métodos clássicos de otimização sejam diretamente empregados à resolução do problema. Neste trabalho é proposta uma nova metodologia de solução de problemas multiobjetivo que envolve o método de restrições canalizadas progressivas, o método de suavização arco tangente e o método primal-dual previsor-corretor de pontos interiores para a determinação de soluções do problema multiobjetivo de despacho econômico e ambiental. O método de restrições canalizadas progressivas transforma o problema multiobjetivo em um conjunto de subproblemas mono-objetivo, considerando a função custo de geração como função objetivo e a função custo de emissão de poluentes como restrição adicional do problema. O método de suavização arco tangente suaviza os termos modulares da função custo de geração quando são considerados os efeitos de pontos de carregamento de válvula e possibilita a utilização do método primal-dual previsor-corretor de pontos interiores à resolução dos subproblemas mono-objetivo determinados pelo método de restrições canalizadas progressivas. Para a aplicação deste método são consideradas as estratégias de pontos exteriores relacionada à função barreira logarítmica modificada e de correção de inércia, as quais permitem ao método, respectivamente, ser inicializado com pontos exteriores à região viável e determinar uma sequência de pontos que converge para mínimos locais dos subproblemas. A metodologia proposta foi implementada em MATLAB 2011a e aplicada aos problemas testes de despacho econômico e ambiental de três, seis, dez, dezenove e quarenta unidades geradoras. Os resultados obtidos demonstram o bom desempenho desta quando comparados aos resultados da literatura. / The multiobjective problem of economic and environmental order involves the minimization of two conflicting objectives: the cost of generation in a thermal unit and the emission of pollutants. When the generation cost objective function includes the effects of valve loading points, it becomes non-convex, and moreover, not differentiable, as modular terms involving the sine are considered to function, making it impossible classical optimization methods are directly employees to solving the problem. This paper proposes a new multi-objective problem-solving methodology that involves the method of progressive bounded constraints, the arctangent smoothing method and the primal-dual predictor-corrector interior point method for the determination of multi-objective solutions to the problem of economic dispatch and environmental. The method of progressive bounded constraints transforms the multi-objective problem into a set of mono-objective sub-problems, considering the role generation cost as objective function and the cost function of emissions as an additional restriction of the problem. The arctangent smoothing method smoothes modular terms of generation cost function when the valve points load effect are considered and enables the use of the primal-dual method predictor-corrector interior point the resolution of single-purpose subproblems determined by method of progressive bounded constraints. For the application of this method are considered the strategies of external points related to the modified logarithmic barrier function and inertia correction, which allow the method, respectively, be initialized with outside points to the feasible region and determine a sequence of points converging to minimum locations of sub-problems. The proposed methodology was implemented in MATLAB 2011a and applied to economic and environmental problems dispatch tests of three, six, ten, nineteen and forty generating units. The obtained results demonstrated the good performance of this compared to literature results.

After introducing concepts from convex analysis, we study how to continuously transform one convex function into another. A natural choice is the arithmetic average, as it is pointwise continuous; however, this choice fails to average functions with different domains. On the contrary, the proximal average is not only continuous (in the epi-topology) but can actually average functions with disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic average) but also inherits smoothness and differentiability (unlike the arithmetic average). Then we introduce a computational framework for computer-aided convex analysis. Motivated by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope. As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit convex hull algorithm. Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions [5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12, p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can be formulated as shortest path problems. / Graduate Studies, College of (Okanagan) / Graduate

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19122号 / 情博第568号 / 新制||情||100(附属図書館) / 32073 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 太田 快人, 教授 永持 仁 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

We consider a congestion control problem in computer networks. The problem is posed as an optimal control problem and reduced to a problem of finding solutions to delay differential equations. Systems involving time delays in the dynamics are actually very difficult to model and therefore very difficult to solve. We consider three approaches in our congestion control problem: an elastic queue approach leading to an optimal control problem with a state–dependent delay differential equation; three approaches in flow models (also leading to systems containing delay differential equations), precisely the dual control approach, the primal–dual control approach and the control approach based on queueing delay. The elastic queue approach is not explored due to the lack of software good enough to solve optimal control problems involving delay differential equations. In flow models, we consider the standard case, that is where the feedback from sources to links is exact and the network behaves perfectly well (without any unexpected event). We also consider some non–standard cases such as the case where this feedback contains errors (for example overestimation, underestimation or noise), and the case where one link breaks in the network. We numerically solve the delay differential equations obtained and use the results we get to determine all the considered dynamics in the network. This is followed by an analysis of the results. We also explore the stability of some simple cases in the dual control approach, with weaker conditions on some network parameters, and discuss some fairness conditions in some simple cases in all the flow model approaches. Non–standard cases are also solved numerically and the results can be compared with those obtained in the standard case.

Orientador: Antonio Roberto Balbo / Banca: Márcia Marcondes Altimari Samed / Banca: Edmea Cassia Baptista / Resumo: Este trabalho visa a investigação e implementação de métodos Primal - Dual Previsor-Corretor de Pontos Interiores com a estratégia de busca unidimensional, e a aplicação destes em problemas de Despacho Econômico e Ambiental. Objetiva-se utilizar estes métodos para determinar soluções aproximadas e consistentes dos problemas causados citados, que forneçam a solução de minimização dos custos dos combustíveis empregados na geração termoelétrica de energia, otimizando um processo de alocação da demanda de energia elétrica entre as unidades geradoras disponíveis, de tal forma que as restrições operacionais sejam atendidas e que o custo de geração é minimizado. Pretende-se também, analisar o problema de Despacho Ambiental com um objetivo único quando se acopla a este o Problema de Despacho Econômico e busca-se, simultaneamente, a minimização dos custos de geração e a redução da emissão de poluentes na natureza. Os métodos foram implementados, testados em Problemas de Despacho Econômico e Ambiental, e o seu desempenho foi comparado com outros métodos já utilizados, cujos resultados são encontrados na literatura / Abstract: This work aims the investigation and implementation of Primal-Dual Predictor-Corrector interior points methods, with the strategy of one-dimensional search, and its application in Economic and Environmental Dispatch Problems. It pretends to use these methods to determine approximate and consistent solutions of the mentioned problems, that provide the solution to minimize the fuel costs used in thermoelectric power generation, optimizing an allocations process of eletric power demand among available generation units, such that the operational constraints are attended and that generation cost is minimized. It too pretends to analyze the Environmental Dispatch Problem with the one objective when it is joined with the Dispatch Problems and it searchs, simultaneously, the minimization of the generation costs and the reduction of emission of the polluants in the nature. The methods were implemented, tested on the Economic and Environemental Dispatch Problems and its performance was compared with others method currently used, whose results are found in the literature / Mestre

Après une description de la méthode de Karmarkar, il est montré que la valeur du pas de déplacement peut être largement améliorée. Les principales difficultés pratiques de la méthode sont discutées. Plus particulièrement, l'hypothèse de connaitre, au départ, la valeur optimale de l'objectif. Diverses extensions et variantes sont étudiées dans le but de relaxer l'hypothèse ci-dessus

The Steiner Tree problem has appeared in the Karp's list of the first 21 NP-hard problems and is well known as one of the most fundamental problems in Network Design area. We study the Node-Weighted version of the Prize Collecting Steiner Tree problem. In this problem, we are given a simple graph with a cost and penalty value associated with each node. Our goal is to find a subtree T of the graph minimizing the cost of the nodes in T plus penalty of the nodes not in T. By a reduction from set cover problem it can be easily shown that the problem cannot be approximated in polynomial time within factor of (1-o(1))ln n unless NP has quasi-polynomial time algorithms, where n is the number of vertices of the graph. Moss and Rabani claimed an O(log n)-approximation algorithm for the problem using a Primal-Dual approach in their STOC'01 paper \cite{moss2001}. We show that their algorithm is incorrect by providing a counter example in which there is an O(n) gap between the dual solution constructed by their algorithm and the optimal solution. Further, evidence is given that their algorithm probably does not have a simple fix. We propose a new algorithm which is more involved and introduces novel ideas in primal dual approach for network design problems. Also, our algorithm is a Lagrangian Multiplier Preserving algorithm and we show how this property can be utilized to design an O(log n)-approximation algorithm for the Node-Weighted Quota Steiner Tree problem using the Lagrangian Relaxation method. We also show an application of the Node Weighted Quota Steiner Tree problem in designing algorithm with better approximation factor for Technology Diffusion problem, a problem proposed by Goldberg and Liu in \cite{goldberg2012} (SODA 2013). In Technology Diffusion, we are given a graph G and a threshold θ(v) associated with each vertex v and we are seeking a set of initial nodes called the seed set. Technology Diffusion is a dynamic process defined over time in which each vertex is either active or inactive. The vertices in the seed set are initially activated and each other vertex v gets activated whenever there are at least θ(v) active nodes connected to v through other active nodes. The Technology Diffusion problem asks to find the minimum seed set activating all nodes. Goldberg and Liu gave an O(rllog n)-approximation algorithm for the problem where r and l are the diameter of G and the number of distinct threshold values, respectively. We improve the approximation factor to O(min{r,l}log n) by establishing a close connection between the problem and the Node Weighted Quota Steiner Tree problem.

The Steiner Tree problem has appeared in the Karp's list of the first 21 NP-hard problems and is well known as one of the most fundamental problems in Network Design area. We study the Node-Weighted version of the Prize Collecting Steiner Tree problem. In this problem, we are given a simple graph with a cost and penalty value associated with each node. Our goal is to find a subtree T of the graph minimizing the cost of the nodes in T plus penalty of the nodes not in T. By a reduction from set cover problem it can be easily shown that the problem cannot be approximated in polynomial time within factor of (1-o(1))ln n unless NP has quasi-polynomial time algorithms, where n is the number of vertices of the graph. Moss and Rabani claimed an O(log n)-approximation algorithm for the problem using a Primal-Dual approach in their STOC'01 paper \cite{moss2001}. We show that their algorithm is incorrect by providing a counter example in which there is an O(n) gap between the dual solution constructed by their algorithm and the optimal solution. Further, evidence is given that their algorithm probably does not have a simple fix. We propose a new algorithm which is more involved and introduces novel ideas in primal dual approach for network design problems. Also, our algorithm is a Lagrangian Multiplier Preserving algorithm and we show how this property can be utilized to design an O(log n)-approximation algorithm for the Node-Weighted Quota Steiner Tree problem using the Lagrangian Relaxation method. We also show an application of the Node Weighted Quota Steiner Tree problem in designing algorithm with better approximation factor for Technology Diffusion problem, a problem proposed by Goldberg and Liu in \cite{goldberg2012} (SODA 2013). In Technology Diffusion, we are given a graph G and a threshold θ(v) associated with each vertex v and we are seeking a set of initial nodes called the seed set. Technology Diffusion is a dynamic process defined over time in which each vertex is either active or inactive. The vertices in the seed set are initially activated and each other vertex v gets activated whenever there are at least θ(v) active nodes connected to v through other active nodes. The Technology Diffusion problem asks to find the minimum seed set activating all nodes. Goldberg and Liu gave an O(rllog n)-approximation algorithm for the problem where r and l are the diameter of G and the number of distinct threshold values, respectively. We improve the approximation factor to O(min{r,l}log n) by establishing a close connection between the problem and the Node Weighted Quota Steiner Tree problem.

Cette thèse s’inscrit dans le cadre de la conception, l’analyse et la mise en œuvre d’algorithmes efficaces et fiables pour la résolution de problèmes d’optimisation non linéaire avec contraintes. Nous présentons trois nouveaux algorithmes fortement primaux-duaux pour résoudre ces problèmes. La première caractéristique de ces algorithmes est que le contrôle des itérés s’effectue dans l’espace primal-dual tout au long du processus de la minimisation, d’où l’appellation “fortement primaux-duaux”. En particulier, la globalisation est effectuée par une méthode de recherche linéaire qui utilise une fonction de mérite primale-duale. La deuxième caractéristique est l’introduction d’une régularisation naturelle du système linéaire qui est résolu à chaque itération pour calculer une direction de descente. Ceci permet à nos algorithmes de bien se comporter pour résoudre les problèmes dégénérés pour lesquels la jacobienne des contraintes n’est pas de plein rang. La troisième caractéristique est que le paramètre de pénalisation est autorisé à augmenter au cours des itérations internes, alors qu’il est généralement maintenu constant. Cela permet de réduire le nombre d’itérations internes. Une étude théorique détaillée incluant l’analyse de convergence globale des itérations internes et externes, ainsi qu’une analyse asymptotique a été présentée pour chaque algorithme. En particulier, nous montrons qu’ils jouissent d’un taux de convergence rapide, superlinéaire ou quadratique. Ces algorithmes sont implémentés dans un nouveau solveur d’optimisation non linéaire qui est appelé SPDOPT. Les bonnes performances de ce solveur ont été montrées en effectuant des comparaisons avec les codes de références IPOPT, ALGENCAN et LANCELOT sur une large collection de problèmes. / This thesis focuses on the design, analysis, and implementation of efficient and reliable algorithms for solving nonlinearly constrained optimization problems. We present three new strongly primal-dual algorithms to solve such problems. The first feature of these algorithms is that the control of the iterates is done in both primal and dual spaces during the whole minimization process, hence the name “strongly primal-dual”. In particular, the globalization is performed by applying a backtracking line search algorithm based on a primal-dual merit function. The second feature is the introduction of a natural regularization of the linear system solved at each iteration to compute a descent direction. This allows our algorithms to perform well when solving degenerate problems for which the Jacobian of constraints is rank deficient. The third feature is that the penalty parameter is allowed to increase along the inner iterations, while it is usually kept constant. This allows to reduce the number of inner iterations. A detailed theoretical study including the global convergence analysis of both inner and outer iterations, as well as an asymptotic convergence analysis is presented for each algorithm. In particular, we prove that these methods have a high rate of convergence : superlinear or quadratic. These algorithms have been implemented in a new solver for nonlinear optimization which is called SPDOPT. The good practical performances of this solver have been demonstrated by comparing it to the reference codes IPOPT, ALGENCAN and LANCELOT on a large collection of test problems.