Este trabalho é focado num problema clássico das Ciências e Engenharia, que consiste em cobrir um objeto por esferas de mesmo raio, a ser minimizado. A abordagem prática usual conta com sérias desvantagens. Logo, faz-se necessário trabalhar com isto de forma diferenciada. A técnica proposta aqui envolve a utilização de resultados célebres da geometria algébrica real, que tem como peça central o positivstellensatz de Stengle e, fazendo a devida relação entre esses resultados e otimização com restrições envolvendo representações naturais por somas de quadrados, é possível reduzir o problema original a um de programação semidefinida não linear. Mas, por contar com particularidades que favorecem a aplicação do paradigma de restauração inexata, esta foi a técnica utilizada para resolvê-lo. A versatilidade da técnica e a possibilidade de generalização direta dos objetos envolvidos destacam-se como grandes vantagens desta abordagem, além da visão algébrica inovadora do problema. / This work is focused on a classic problem from Engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to nd a dierent way. Here, we explore some renowned results from real algebraic geometry, which has Stengle\'s positivstellensatz as one of its central pieces, and SOS optimization. Once the proper link is made, the original problem can be reduced to a nonlinear semidenite programming one, which has peculiarities that favours the application of an inexact restoration paradigm. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects.

This thesis consists of four independent papers concerningdifferent aspects of interior methods for optimization. Threeof the papers focus on theoretical aspects while the fourth oneconcerns some computational experiments. The systems of equations solved within an interior methodapplied to a convex quadratic program can be viewed as weightedlinear least-squares problems. In the first paper, it is shownthat the sequence of solutions to such problems is uniformlybounded. Further, boundedness of the solution to weightedlinear least-squares problems for more general classes ofweight matrices than the one in the convex quadraticprogramming application are obtained as a byproduct. In many linesearch interior methods for nonconvex nonlinearprogramming, the iterates can "falsely" converge to theboundary of the region defined by the inequality constraints insuch a way that the search directions do not converge to zero,but the step lengths do. In the sec ond paper, it is shown thatthe multiplier search directions then diverge. Furthermore, thedirection of divergence is characterized in terms of thegradients of the equality constraints along with theasymptotically active inequality constraints. The third paper gives a modification of the analytic centerproblem for the set of optimal solutions in linear semidefiniteprogramming. Unlike the normal analytic center problem, thesolution of the modified problem is the limit point of thecentral path, without any strict complementarity assumption.For the strict complementarity case, the modified problem isshown to coincide with the normal analytic center problem,which is known to give a correct characterization of the limitpoint of the central path in that case. The final paper describes of some computational experimentsconcerning possibilities of reusing previous information whensolving system of equations arising in interior methods forlinear programming. <b>Keywords:</b>Interior method, primal-dual interior method,linear programming, quadratic programming, nonlinearprogramming, semidefinite programming, weighted least-squaresproblems, central path. <b>Mathematics Subject Classification (2000):</b>Primary90C51, 90C22, 65F20, 90C26, 90C05; Secondary 65K05, 90C20,90C25, 90C30.

Finding an efficient method to detect counterfeit banknotes is imperative. In this study, we propose multiple kernel weighted support vector machine for counterfeit banknote recognition. A variation of SVM in optimizing false alarm rate, called FARSVM, is proposed which provide minimized false negative rate and false positive rate. Each banknote is divided into m ¡Ñ n partitions, and each partition comes with its own kernels. The optimal weight with each kernel matrix in the combination is obtained through the semidefinite programming (SDP) learning method. The amount of time and space required by the original SDP is very demanding. We focus on this framework and adopt two strategies to reduce the time and space requirements. The first strategy is to assume the non-negativity of kernel weights, and the second strategy is to set the sum of weights equal to 1. Experimental results show that regions with zero kernel weights are easy to imitate with today¡¦s digital imaging technology, and regions with nonzero kernel weights are difficult to imitate. In addition, these results show that the proposed approach outperforms single kernel SVM and standard SVM with SDP on Taiwanese banknotes.

<p>This thesis consists of four independent papers concerningdifferent aspects of interior methods for optimization. Threeof the papers focus on theoretical aspects while the fourth oneconcerns some computational experiments.</p><p>The systems of equations solved within an interior methodapplied to a convex quadratic program can be viewed as weightedlinear least-squares problems. In the first paper, it is shownthat the sequence of solutions to such problems is uniformlybounded. Further, boundedness of the solution to weightedlinear least-squares problems for more general classes ofweight matrices than the one in the convex quadraticprogramming application are obtained as a byproduct.</p><p>In many linesearch interior methods for nonconvex nonlinearprogramming, the iterates can "falsely" converge to theboundary of the region defined by the inequality constraints insuch a way that the search directions do not converge to zero,but the step lengths do. In the sec ond paper, it is shown thatthe multiplier search directions then diverge. Furthermore, thedirection of divergence is characterized in terms of thegradients of the equality constraints along with theasymptotically active inequality constraints.</p><p>The third paper gives a modification of the analytic centerproblem for the set of optimal solutions in linear semidefiniteprogramming. Unlike the normal analytic center problem, thesolution of the modified problem is the limit point of thecentral path, without any strict complementarity assumption.For the strict complementarity case, the modified problem isshown to coincide with the normal analytic center problem,which is known to give a correct characterization of the limitpoint of the central path in that case.</p><p>The final paper describes of some computational experimentsconcerning possibilities of reusing previous information whensolving system of equations arising in interior methods forlinear programming.</p><p><b>Keywords:</b>Interior method, primal-dual interior method,linear programming, quadratic programming, nonlinearprogramming, semidefinite programming, weighted least-squaresproblems, central path.</p><p><b>Mathematics Subject Classification (2000):</b>Primary90C51, 90C22, 65F20, 90C26, 90C05; Secondary 65K05, 90C20,90C25, 90C30.</p>

La présente thèse a pour objet d’explorer les potentialités d’une méthode prometteuse de l’optimisation conique, la programmation semi-définie positive (SDP), pour les problèmes de management d’énergie, à savoir relatifs à la satisfaction des équilibres offre-demande électrique et gazier.Nos travaux se déclinent selon deux axes. Tout d’abord nous nous intéressons à l’utilisation de la SDP pour produire des relaxations de problèmes combinatoires et quadratiques. Si une relaxation SDP dite « standard » peut être élaborée très simplement, il est généralement souhaitable de la renforcer par des coupes, pouvant être déterminées par l'étude de la structure du problème ou à l'aide de méthodes plus systématiques. Nous mettons en œuvre ces deux approches sur différentes modélisations du problème de planification des arrêts nucléaires, réputé pour sa difficulté combinatoire. Nous terminons sur ce sujet par une expérimentation de la hiérarchie de Lasserre, donnant lieu à une suite de SDP dont la valeur optimale tend vers la solution du problème initial.Le second axe de la thèse porte sur l'application de la SDP à la prise en compte de l'incertitude. Nous mettons en œuvre une approche originale dénommée « optimisation distributionnellement robuste », pouvant être vue comme un compromis entre optimisation stochastique et optimisation robuste et menant à des approximations sous forme de SDP. Nous nous appliquons à estimer l'apport de cette approche sur un problème d'équilibre offre-demande avec incertitude. Puis, nous présentons une relaxation SDP pour les problèmes MISOCP. Cette relaxation se révèle être de très bonne qualité, tout en ne nécessitant qu’un temps de calcul raisonnable. La SDP se confirme donc être une méthode d’optimisation prometteuse qui offre de nombreuses opportunités d'innovation en management d’énergie. / The present thesis aims at exploring the potentialities of a powerful optimization technique, namely Semidefinite Programming, for addressing some difficult problems of energy management. We pursue two main objectives. The first one consists of using SDP to provide tight relaxations of combinatorial and quadratic problems. A first relaxation, called “standard” can be derived in a generic way but it is generally desirable to reinforce them, by means of tailor-made tools or in a systematic fashion. These two approaches are implemented on different models of the Nuclear Outages Scheduling Problem, a famous combinatorial problem. We conclude this topic by experimenting the Lasserre's hierarchy on this problem, leading to a sequence of semidefinite relaxations whose optimal values tends to the optimal value of the initial problem.The second objective deals with the use of SDP for the treatment of uncertainty. We investigate an original approach called “distributionnally robust optimization”, that can be seen as a compromise between stochastic and robust optimization and admits approximations under the form of a SDP. We compare the benefits of this method w.r.t classical approaches on a demand/supply equilibrium problem. Finally, we propose a scheme for deriving SDP relaxations of MISOCP and we report promising computational results indicating that the semidefinite relaxation improves significantly the continuous relaxation, while requiring a reasonable computational effort.SDP therefore proves to be a promising optimization method that offers great opportunities for innovation in energy management.

Traditionally, linear programming (LP) has been used to construct convex relaxations in the context of branch and bound for determining global optimal solutions to nonconvex optimization problems. As second-order cone programming (SOCP) and semidefinite programming (SDP) become better understood by optimization researchers, they become alternative choices for obtaining convex relaxations and producing bounds on the optimal values. In this thesis, we study the use of these convex optimization tools in constructing strong relaxations for several nonconvex problems, including 0-1 integer programming, nonconvex box-constrained quadratic programming (BoxQP), and general quadratic programming (QP). We first study a SOCP relaxation for 0-1 integer programs and a sequential relaxation technique based on this SOCP relaxation. We present desirable properties of this SOCP relaxation, for example, this relaxation cuts off all fractional extreme points of the regular LP relaxation. We further prove that the sequential relaxation technique generates the convex hull of 0-1 solutions asymptotically. We next explore nonconvex quadratic programming. We propose a SDP relaxation for BoxQP based on relaxing the first- and second-order KKT conditions, where the difficulty and contribution lie in relaxing the second-order KKT condition. We show that, although the relaxation we obtain this way is equivalent to an existing SDP relaxation at the root node, it is significantly stronger on the children nodes in a branch-and-bound setting. New advance in optimization theory allows one to express QP as optimizing a linear function over the convex cone of completely positive matrices subject to linear constraints, referred to as completely positive programming (CPP). CPP naturally admits strong semidefinite relaxations. We incorporate the first-order KKT conditions of QP into the constraints of QP, and then pose it in the form of CPP to obtain a strong relaxation. We employ the resulting SDP relaxation inside a finite branch-and-bound algorithm to solve the QP. Comparison of our algorithm with commercial global solvers shows potential as well as room for improvement. The remainder is devoted to new techniques for solving a class of large-scale linear programming problems. First order methods, although not as fast as second-order methods, are extremely memory efficient. We develop a first-order method based on Nesterov's smoothing technique and demonstrate the effectiveness of our method on two machine learning problems.

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

This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone. We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Benders' decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Benders' methodology for problems having 0-1 mixed-integer subproblems. We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach. / Ph. D.

The main topic of this thesis is integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control methods is Model Predictive Control (MPC). In each sampling time, MPC requires the solution of a Quadratic Programming (QP) problem. To be able to use MPC for large systems, and at high sampling rates, optimization routines tailored for MPC are used. In recent years, the range of application of MPC has been extended to so-called hybrid systems. Hybrid systems are systems where continuous dynamics interact with logic. When this extension is made, binary variables are introduced in the problem. As a consequence, the QP problem has to be replaced by a far more challenging Mixed Integer Quadratic Programming (MIQP) problem, which is known to have a computational complexity which grows exponentially in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel. To estimate the information originally sent, a maximum likelihood problem involving binary variables can be solved. The process of simultaneously estimating the information sent by multiple users is called Multiuser Detection (MUD). In this thesis, the problem to efficiently solve MIQP problems originating from MPC and MUD is addressed. Four different algorithms are presented. First, a polynomial complexity preprocessing algorithm for binary quadratic programming problems is presented. By using the algorithm, some, or all, binary variables can be computed efficiently already in the preprocessing phase. In numerical experiments, the algorithm is applied to unconstrained MPC problems with a mixture of real valued and binary valued control signals, and the result shows that the performance gain can be significant compared to solving the problem using branch and bound. The preprocessing algorithm has also been applied to the MUD problem, where simulations have shown that the bit error rate can be significantly reduced compared to using common suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The algorithm uses a branch and bound method where the relaxed node problems are solved by a dual active set QP algorithm. In this QP algorithm, the KKT systems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the proposed QP solver and MIQP solver have lower computational complexity compared to corresponding generic solvers. Third, the dual active set QP algorithm is enhanced using ideas from gradient projection methods. The performance of this enhanced algorithm is shown to be comparable with the existing commercial state-of-the-art QP solver \cplex for some random linear MPC problems. Fourth, an algorithm for efficient computation of the search directions in an SDP solver for a proposed alternative SDP relaxation applicable to MPC problems with binary control signals is presented. The SDP relaxation considered has the potential to give a tighter lower bound on the optimal objective function value compared to the QP relaxation that is traditionally used in branch and bound for these problems, and its computational performance is better than the ordinary SDP relaxation for the problem. Furthermore, the tightness of the different relaxations is investigated both theoretically and in numerical experiments. / This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the Linköping University's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this material, you agree to all provisions of the copyright laws protecting it.

Este trabalho insere-se no contexto de métodos de multiplicadores para a resolução de problemas de programação convexa semidefinida e a análise de suas propriedades através do método proximal aplicado sobre o problema dual. Nosso foco será uma subclasse de problemas de programação convexa semidefinida com restrições afins, para a qual estudaremos relações de dualidade e condições para a existência de soluções dos problemas primal e dual. Em seguida, analisaremos dois métodos de multiplicadores para resolver essa classe de problemas e que são extensões de métodos conhecidos para programação não-linear. O primeiro, proposto por Doljansky e Teboulle, aborda um método de ponto proximal interior entrópico e sua conexão com um método de multiplicadores exponenciais. O segundo, apresentado por Mosheyev e Zibulevsky, estende para a classe de problemas de nosso interesse um método de lagrangianos aumentados suaves proposto por Ben-Tal e Zibulevsky. Por fim, apresentamos os resultados de testes numéricos feitos com o algoritmo proposto por Mosheyev e Zibulevsky, analisando diferentes escolhas de parâmetros, o aproveitamento do padrão de esparsidade das matrizes do problema e critérios para a resolução aproximada dos subproblemas irrestritos que devem ser resolvidos a cada iteração desse algoritmo de lagrangianos aumentados. / This work deals with multiplier methods to solve semidefinite convex programming problems and the analysis of their proprieties based on the proximal point method applied on the dual problem. We focus on a subclass of semidefinite programming problems with affine constraints, for which we study duality relations an conditions for the existence of solutions of the primal and dual problems. Afterwards, we analyze two multiplier methods to solve this class of problems which are extensions of known methods in nonlinear programming. The first one, introduced by Doljansky e Teboulle, approaches an entropic interior proximal algorithm and their relationship with an exponential multiplier method. The second one, presented by Mosheyev e Zibulevsky, extends a smooth augmented Lagrangian method proposed by Ben-Tal and Zibulevsky for the problems of our interest. Finally, we present the results of numerical experiments for the algorithm proposed by Mosheyev e Zibulevsky, analyzing some choices of parameters, the sparsity patterns of matrices of the problem and criteria to accept approximate solutions of the unconstrained subproblems that must be solved at each iteration of the augmented Lagrangian method.