Dissertations / Theses on the topic 'Convex constrained optimization'
To see the other types of publications on this topic, follow the link: Convex constrained optimization.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 40 dissertations / theses for your research on the topic 'Convex constrained optimization.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Shewchun, John Marc 1972. "Constrained control using convex optimization." Thesis, Massachusetts Institute of Technology, 1997. http://hdl.handle.net/1721.1/46471.
Full text
2
Yang, Yi. "Sequential convex approximations of chance constrained programming /." View abstract or full-text, 2008. http://library.ust.hk/cgi/db/thesis.pl?IELM%202008%20YANG.
Full text
3
Lintereur, Beau V. (Beau Vincent) 1973. "Constrained H̳₂ design via convex optimization with applications." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/50628.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 1998.In title on t.p., double-underscored "H" appears in script.
Includes bibliographical references (p. 133-138).
A convex optimization controller design method is presented which minimizes the closed-loop H2 norm, subject to constraints on the magnitude of closed-loop transfer functions and transient responses due to specified inputs. This method uses direct parameter optimization of the closed-loop Youla or Q-parameter where the variables are the coefficients of a stable orthogonal basis. The basis is constructed using the recently rediscovered Generalized Orthonormal Basis Functions (GOBF) that have found application in system identification. It is proposed that many typical control specifications including robustness to modeling error and gain and phase margins can be posed with two simple constraints in the frequency and time domain. With some approximation, this formulation allows the controller design problem to be cast as a quadratic program. Two example applications demonstrate the practical utility of this method for real systems. First this method is applied to the roll axis of the EOS-AM1 spacecraft attitude control system, with a set of performance and robustness specifications. The constrained H2 controller simultaneously meets the specifications where previous model-based control studies failed. Then a constrained H2 controller is designed for an active vibration isolation system for a spaceborne optical technology demonstration test stand. Mixed specifications are successfully incorporated into the design and the results are verified with experimental frequency data.
by Beau V. Lintereur.
S.M.
4
Roese-Koerner, Lutz [Verfasser]. "Convex Optimization for Inequality Constrained Adjustment Problems / Lutz Roese-Koerner." Bonn : Universitäts- und Landesbibliothek Bonn, 2015. http://d-nb.info/1078728534/34.
Full text
5
Oliveira, Rafael Massambone de. "String-averaging incremental subgradient methods for constrained convex optimization problems." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-14112017-150512/.
Full textAbstract:
In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems.Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.
6
Li, Yusong. "Stochastic maximum principle and dynamic convex duality in continuous-time constrained portfolio optimization." Thesis, Imperial College London, 2016. http://hdl.handle.net/10044/1/45536.
Full textAbstract:
This thesis seeks to gain further insight into the connection between stochastic optimal control and forward and backward stochastic differential equations and its applications in solving continuous-time constrained portfolio optimization problems. Three topics are studied in this thesis. In the first part of the thesis, we focus on stochastic maximum principle, which seeks to establish the connection between stochastic optimal control and backward stochastic differential differential equations coupled with static optimality condition on the Hamiltonian. We prove a weak neccessary and sufficient maximum principle for Markovian regime switching stochastic optimal control problems. Instead of insisting on the maxi- mum condition of the Hamiltonian, we show that 0 belongs to the sum of Clarkes generalized gradient of the Hamiltonian and Clarkes normal cone of the control constraint set at the optimal control. Under a joint concavity condition on the Hamiltonian and a convexity condition on the terminal objective function, the necessary condition becomes sufficient. We give four examples to demonstrate the weak stochastic maximum principle. In the second part of the thesis, we study a continuous-time stochastic linear quadratic control problem arising from mathematical finance. We model the asset dynamics with random market coefficients and portfolio strategies with convex constraints. Following the convex duality approach,we show that the necessary and sufficient optimality conditions for both the primal and dual problems can be written in terms of processes satisfying a system of FBSDEs together with other conditions. We characterise explicitly the optimal wealth and portfolio processes as functions of adjoint processes from the dual FBSDEs in a dynamic fashion and vice versa. We apply the results to solve quadratic risk minimization problems with cone-constraints and derive the explicit representations of solutions to the extended stochastic Riccati equations for such problems. In the final section of the thesis, we extend the previous result to utility maximization problems. After formulating the primal and dual problems, we construct the necessary and sufficient conditions for both the primal and dual problems in terms of FBSDEs plus additional conditions. Such formulation then allows us to explicitly characterize the primal optimal control as a function of the adjoint processes coming from the dual FBSDEs in a dynamic fashion and vice versa. Moreover, we also find that the optimal primal wealth process coincides with the optimal adjoint process of the dual problem and vice versa. Finally we solve three constrained utility maximization problems and contrasts the simplicity of the duality approach we propose with the technical complexity in solving the primal problem directly.
7
Kůdela, Jakub. "Advanced Decomposition Methods in Stochastic Convex Optimization." Doctoral thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2019. http://www.nusl.cz/ntk/nusl-403864.
Full textAbstract:
Při práci s úlohami stochastického programování se často setkáváme s optimalizačními problémy, které jsou příliš rozsáhlé na to, aby byly zpracovány pomocí rutinních metod matematického programování. Nicméně, v některých případech mají tyto problémy vhodnou strukturu, umožňující použití specializovaných dekompozičních metod, které lze použít při řešení rozsáhlých optimalizačních problémů. Tato práce se zabývá dvěma třídami úloh stochastického programování, které mají speciální strukturu, a to dvoustupňovými stochastickými úlohami a úlohami s pravděpodobnostním omezením, a pokročilými dekompozičními metodami, které lze použít k řešení problému v těchto dvou třídách. V práci popisujeme novou metodu pro tvorbu “warm-start” řezů pro metodu zvanou “Generalized Benders Decomposition”, která se používá při řešení dvoustupňových stochastických problémů. Pro třídu úloh s pravděpodobnostním omezením zde uvádíme originální dekompoziční metodu, kterou jsme nazvali “Pool & Discard algoritmus”. Užitečnost popsaných dekompozičních metod je ukázána na několika příkladech a inženýrských aplikacích.
8
Günther, Christian [Verfasser]. "On generalized-convex constrained multi-objective optimization and application in location theory / Christian Günther." Halle, 2018. http://d-nb.info/1175950602/34.
Full text
9
Wang, Guanglei. "Relaxations in mixed-integer quadratically constrained programming and robust programming." Thesis, Evry, Institut national des télécommunications, 2016. http://www.theses.fr/2016TELE0026/document.
Full textAbstract:
De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modéréesMany real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions
10
Blomqvist, Anders. "A convex optimization approach to complexity constrained analytic interpolation with applications to ARMA estimation and robust control." Doctoral thesis, Stockholm, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-117.
Full text
11
Sapankevych, Nicholas. "Constrained Motion Particle Swarm Optimization for Non-Linear Time Series Prediction." Scholar Commons, 2015. https://scholarcommons.usf.edu/etd/5569.
Full textAbstract:
Time series prediction techniques have been used in many real-world applications such as financial market prediction, electric utility load forecasting, weather and environmental state prediction, and reliability forecasting. The underlying system models and time series data generating processes are generally complex for these applications and the models for these systems are usually not known a priori. Accurate and unbiased estimation of time series data produced by these systems cannot always be achieved using well known linear techniques, and thus the estimation process requires more advanced time series prediction algorithms.
One type of time series interpolation and prediction algorithm that has been proven to be effective for these various types of applications is Support Vector Regression (SVR) [1], which is based on the Support Vector Machine (SVM) developed by Vapnik et al. [2, 3]. The underlying motivation for using SVMs is the ability of this methodology to accurately forecast time series data when the underlying system processes are typically nonlinear, non-stationary and not defined a-priori. SVMs have also been proven to outperform other non-linear techniques including neural-network based non-linear prediction techniques such as multi-layer perceptrons.
As with most time series prediction algorithms, there are typically challenges associated in applying a given heuristic to any general problem. One difficult challenge in using SVR to solve these types of problems is the selection of free parameters associated with the SVR algorithm. There is no given heuristic to select SVR free parameters and the user is left to adjust these parameters in an ad hoc manner.
The focus of this dissertation is to present an alternative to the typical ad hoc approach of tuning SVR for time series prediction problems by using Particle Swarm Optimization (PSO) to assist in the SVR free parameter selection process. Developed by Kennedy and Eberhart [4-8], PSO is a technique that emulates the process living creatures (such as birds or insects) use to discover food resources at a given geographic location. PSO has been proven to be an effective technique for many different kinds of optimization problems [9-11].
The focus of this dissertation is to present an alternative to the typical ad hoc approach of tuning SVR for time series prediction problems by using Particle Swarm Optimization (PSO) to assist in the SVR free parameter selection process. Developed by Kennedy and Eberhart [4-8], PSO is a technique that emulates the process living creatures (such as birds or insects) use to discover food resources at a given geographic location. PSO has been proven to be an effective technique for many different kinds of optimization problems [9-11].
12
Nguyen, Ngoc Anh. "Explicit robust constrained control for linear systems : analysis, implementation and design based on optimization." Thesis, Université Paris-Saclay (ComUE), 2015. http://www.theses.fr/2015SACLC012/document.
Full textAbstract:
Les lois de commande affines par morceaux ont attiré une grande attention de la communauté d'automatique de contrôle grâce à leur pertinence pour des systèmes contraints, systèmes hybrides; également pour l'approximation de commandes nonlinéaires. Pourtant, leur mise en oeuvre est soumise à quelques difficultés. Motivé par l'intérêt à cette classe de commandes, cette thèse porte sur leur analyse, mise en oeuvre et synthèse.La première partie de cette thèse a pour but le calcul de la marge de robustesse et de la marge de fragilité pour une loi de commande affine par morceaux donnée et un système linéaire discret. Plus précisément, la marge de robustesse est définie comme l'ensemble des systèmes linéaires à paramètres variants que la loi de commande donnée garde les trajectoires dans de la région faisable. D'ailleurs, la marge de fragilité comprend toutes les variations des coefficients de la commande donnée telle que l'invariance de la région faisable soit encore garantie. Il est montré que si la région faisable donnée est un polytope, ces marges sont aussi des polytopes.La deuxième partie de ce manuscrit est consacrée au problème de l'optimalité inverse pour la classe des fonctions affines par morceaux. C'est-à-dire, l'objective est de définir un problème d'optimisation pour lequel la solution optimale est équivalente à la fonction affine par morceaux donnée. La méthodologie est fondée sur le convex lifting, i.e., un variable auxiliaire, scalaire, qui permet de définir un ensemble convex à partir de la partition d'état de la fonction affine par morceaux donnée. Il est montré que si la fonction affine par morceaux donnée est continue, la solution optimale de ce problème redéfini sera unique. Par contre, si la continuité n'est pas satisfaite, cette fonction affine par morceaux sera une solution optimale parmi les autres du problème redéfini.En ce qui concerne l’application dans la commande prédictive, il sera montré que n'importe quelle loi de commande affine par morceaux continue peut être obtenue par un autre problème de commande prédictive avec l'horizon de prédiction au plus égal à 2. A côté de cet aspect théorique, ce résultat sera utile pour faciliter la mise en oeuvre des lois de commandes affines par morceaux en évitant l'enregistrement de la partition de l'espace d'état. Dans la dernière partie de ce rapport, une famille de convex liftings servira comme des fonctions de Lyapunov. En conséquence, ce "convex lifting" sera déployé pour synthétiser des lois de commande robustes pour des systèmes linéaires incertains, également en présence de perturbations additives bornées. Des lois implicites et explicites seront obtenues en même temps. Cette méthode permet de garantir la faisabilité récursive et la stabilité robuste. Cependant, cette fonction de Lyapunov est limitée à l'ensemble λ −contractive maximal avec une constante scalaire 0 ≤ λ < 1 qui est plus petit que l'ensemble contrôlable maximal. Pour cette raison, une extension de cette méthode pour l'ensemble contrôlable de N − pas, sera présentée. Cette méthode est fondée sur des convex liftings en cascade où une variable auxiliaire sera utilisée pour servir comme une fonction de Lyapunov. Plus précisément, cette variable est non-négative, strictement décroissante pour les N premiers pas et égale toujours à 0 − après. Par conséquent, la stabilité robuste est garantiePiecewise affine (PWA) feedback control laws have received significant attention due to their relevance for the control of constrained systems, hybrid systems; equally for the approximation of nonlinear control. However, they are associated with serious implementation issues. Motivated from the interest in this class of particular controllers, this thesis is mostly related to their analysis and design.The first part of this thesis aims to compute the robustness and fragility margins for a given PWA control law and a linear discrete-time system. More precisely, the robustness margin is defined as the set of linear time-varying systems such that the given PWA control law keeps the trajectories inside a given feasible set. On a different perspective, the fragility margin contains all the admissible variations of the control law coefficients such that the positive invariance of the given feasible set is still guaranteed. It will be shown that if the given feasible set is a polytope, then so are these robustness/fragility margins.The second part of this thesis focuses on inverse optimality problem for the class of PWA controllers. Namely, the goal is to construct an optimization problem whose optimal solution is equivalent to the given PWA function. The methodology is based on emph convex lifting: an auxiliary 1− dimensional variable which enhances the convexity characterization into recovered optimization problem. Accordingly, if the given PWA function is continuous, the optimal solution to this reconstructed optimization problem will be shown to be unique. Otherwise, if the continuity of this given PWA function is not fulfilled, this function will be shown to be one optimal solution to the recovered problem.In view of applications in linear model predictive control (MPC), it will be shown that any continuous PWA control law can be obtained by a linear MPC problem with the prediction horizon at most equal to 2 prediction steps. Aside from the theoretical meaning, this result can also be of help to facilitate implementation of PWA control laws by avoiding storing state space partition. Another utility of convex liftings will be shown in the last part of this thesis to be a control Lyapunov function. Accordingly, this convex lifting will be deployed in the so-called robust control design based on convex liftings for linear system affected by bounded additive disturbances and polytopic uncertainties. Both implicit and explicit controllers can be obtained. This method can also guarantee the recursive feasibility and robust stability. However, this control Lyapunov function is only defined over the maximal λ −contractive set for a given 0 ≤ λ < 1 which is known to be smaller than the maximal controllable set. Therefore, an extension of the above method to the N-steps controllable set will be presented. This method is based on a cascade of convex liftings where an auxiliary variable will be used to emulate a Lyapunov function. Namely, this variable will be shown to be non-negative, to strictly decrease for N first steps and to stay at 0 afterwards. Accordingly, robust stability is sought
13
Fleming, James. "Robust and stochastic MPC of uncertain-parameter systems." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:c19ff07c-0756-45f6-977b-9d54a5214310.
Full textAbstract:
Constraint handling is difficult in model predictive control (MPC) of linear differential inclusions (LDIs) and linear parameter varying (LPV) systems. The designer is faced with a choice of using conservative bounds that may give poor performance, or accurate ones that require heavy online computation. This thesis presents a framework to achieve a more flexible trade-off between these two extremes by using a state tube, a sequence of parametrised polyhedra that is guaranteed to contain the future state. To define controllers using a tube, one must ensure that the polyhedra are a sub-set of the region defined by constraints. Necessary and sufficient conditions for these subset relations follow from duality theory, and it is possible to apply these conditions to constrain predicted system states and inputs with only a little conservatism. This leads to a general method of MPC design for uncertain-parameter systems. The resulting controllers have strong theoretical properties, can be implemented using standard algorithms and outperform existing techniques. Crucially, the online optimisation used in the controller is a convex problem with a number of constraints and variables that increases only linearly with the length of the prediction horizon. This holds true for both LDI and LPV systems. For the latter it is possible to optimise over a class of gain-scheduled control policies to improve performance, with a similar linear increase in problem size. The framework extends to stochastic LDIs with chance constraints, for which there are efficient suboptimal methods using online sampling. Sample approximations of chance constraint-admissible sets are generally not positively invariant, which motivates the novel concept of âsample-admissible' sets with this property to ensure recursive feasibility when using sampling methods. The thesis concludes by introducing a simple, convex alternative to chance-constrained MPC that applies a robust bound to the time average of constraint violations in closed-loop.
14
Luedtke, James. "Integer Programming Approaches for Some Non-convex and Stochastic Optimization Problems." Diss., Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/19711.
Full textAbstract:
In this dissertation we study several non-convex and stochastic optimization problems. The common theme is the use of mixed-integer programming (MIP) techniques including valid inequalities and reformulation to solve these problems.
We first study a strategic capacity planning model which captures the trade-off between the incentive to delay capacity installation to wait for improved technology and the need for some capacity to be installed to meet current demands. This problem is naturally formulated as a MIP with a bilinear objective. We develop several linear MIP formulations, along with classes of strong valid inequalities. We also present a specialized branch-and-cut algorithm to solve a compact concave formulation. Computational results indicate that these formulations can be used to solve large-scale instances.
We next study methods for optimization with joint probabilistic constraints. These problems are challenging because evaluating solution feasibility requires multidimensional integration and the feasible region is not convex. We propose and analyze a Monte Carlo sampling scheme to simplify the probabilistic structure of such problems. Computational tests of the approach indicate that it can yield good feasible solutions and reasonable bounds on their quality. Next, we study a MIP formulation of the non-convex sample approximation problem. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. Computational results indicate that large-scale instances can be solved using the strengthened formulations.
Finally, we study optimization problems with stochastic dominance constraints. A stochastic dominance constraint states that a random outcome which depends on the decision variables should stochastically dominate a given random variable. We present new formulations for both first and second order stochastic dominance which are significantly more compact than existing formulations. Computational tests illustrate the benefits of the new formulations.
15
El, Gamal Mostafa. "Distributed Statistical Learning under Communication Constraints." Digital WPI, 2017. https://digitalcommons.wpi.edu/etd-dissertations/314.
Full textAbstract:
"In this thesis, we study distributed statistical learning, in which multiple terminals, connected by links with limited capacity, cooperate to perform a learning task. As the links connecting the terminals have limited capacity, the messages exchanged between the terminals have to be compressed. The goal of this thesis is to investigate how to compress the data observations at multiple terminals and how to use the compressed data for inference. We first focus on the distributed parameter estimation problem, in which terminals send messages related to their local observations using limited rates to a fusion center that will obtain an estimate of a parameter related to the observations of all terminals. It is well known that if the transmission rates are in the Slepian-Wolf region, the fusion center can fully recover all observations and hence can construct an estimator having the same performance as that of the centralized case. One natural question is whether Slepian-Wolf rates are necessary to achieve the same estimation performance as that of the centralized case. In this thesis, we show that the answer to this question is negative. We then examine the optimality of data dimensionality reduction via sufficient statistics compression in distributed parameter estimation problems. The data dimensionality reduction step is often needed especially if the data has a very high dimension and the communication rate is not as high as the one characterized above. We show that reducing the dimensionality by extracting sufficient statistics of the parameter to be estimated does not degrade the overall estimation performance in the presence of communication constraints. We further analyze the optimal estimation performance in the presence of communication constraints and we verify the derived bound using simulations. Finally, we study distributed optimization problems, for which we examine the randomized distributed coordinate descent algorithm with quantized updates. In the literature, the iteration complexity of the randomized distributed coordinate descent algorithm has been characterized under the assumption that machines can exchange updates with an infinite precision. We consider a practical scenario in which the messages exchange occurs over channels with finite capacity, and hence the updates have to be quantized. We derive sufficient conditions on the quantization error such that the algorithm with quantized update still converge."
16
Li, Nan. "Maximum Likelihood Identification of an Information Matrix Under Constraints in a Corresponding Graphical Model." Digital WPI, 2017. https://digitalcommons.wpi.edu/etd-theses/128.
Full textAbstract:
We address the problem of identifying the neighborhood structure of an undirected graph, whose nodes are labeled with the elements of a multivariate normal (MVN) random vector. A semi-definite program is given for estimating the information matrix under arbitrary constraints on its elements. More importantly, a closed-form expression is given for the maximum likelihood (ML) estimator of the information matrix, under the constraint that the information matrix has pre-specified elements in a given pattern (e.g., in a principal submatrix). The results apply to the identification of dependency labels in a graphical model with neighborhood constraints. This neighborhood structure excludes nodes which are conditionally independent of a given node and the graph is determined by the non- zero elements in the information matrix for the random vector. A cross-validation principle is given for determining whether the constrained information matrix returned from this procedure is an acceptable model for the information matrix, and as a consequence for the neighborhood structure of the Markov Random Field (MRF) that is identified with the MVN random vector.
17
Vonwirth, Christian [Verfasser], and Jörn [Akademischer Betreuer] Sass. "Continuous-Time Portfolio Optimization under Partial Information and Convex Constraints: Deriving Explicit Results / Christian Vonwirth ; Betreuer: Jörn Sass." Kaiserslautern : Technische Universität Kaiserslautern, 2017. http://d-nb.info/1137206500/34.
Full text
18
Heinrich, André. "Fenchel duality-based algorithms for convex optimization problems with applications in machine learning and image restoration." Doctoral thesis, Universitätsbibliothek Chemnitz, 2013. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-108923.
Full textAbstract:
The main contribution of this thesis is the concept of Fenchel duality with a focus on its application in the field of machine learning problems and image restoration tasks. We formulate a general optimization problem for modeling support vector machine tasks and assign a Fenchel dual problem to it, prove weak and strong duality statements as well as necessary and sufficient optimality conditions for that primal-dual pair. In addition, several special instances of the general optimization problem are derived for different choices of loss functions for both the regression and the classifification task. The convenience of these approaches is demonstrated by numerically solving several problems. We formulate a general nonsmooth optimization problem and assign a Fenchel dual problem to it. It is shown that the optimal objective values of the primal and the dual one coincide and that the primal problem has an optimal solution under certain assumptions. The dual problem turns out to be nonsmooth in general and therefore a regularization is performed twice to obtain an approximate dual problem that can be solved efficiently via a fast gradient algorithm. We show how an approximate optimal and feasible primal solution can be constructed by means of some sequences of proximal points closely related to the dual iterates. Furthermore, we show that the solution will indeed converge to the optimal solution of the primal for arbitrarily small accuracy. Finally, the support vector regression task is obtained to arise as a particular case of the general optimization problem and the theory is specialized to this problem. We calculate several proximal points occurring when using difffferent loss functions as well as for some regularization problems applied in image restoration tasks. Numerical experiments illustrate the applicability of our approach for these types of problems.
19
Stühmer, Jan [Verfasser], Daniel [Akademischer Betreuer] [Gutachter] Cremers, and William T. [Gutachter] Freeman. "A Convex Optimization Framework for Connectivity Constraints in Image Segmentation and 3D Reconstruction / Jan Stühmer ; Gutachter: Daniel Cremers, William T. Freeman ; Betreuer: Daniel Cremers." München : Universitätsbibliothek der TU München, 2016. http://d-nb.info/1131253671/34.
Full text
20
Nagamune, Ryozo. "Robust Control with Complexity Constraint : A Nevanlinna-Pick Interpolation Approach." Doctoral thesis, KTH, Mathematics, 2002. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-3394.
Full text
21
Fuentes, Marc. "Analyse et optimisation de problèmes sous contraintes d'autocorrélation." Phd thesis, Université Paul Sabatier - Toulouse III, 2007. http://tel.archives-ouvertes.fr/tel-00195013.
Full textAbstract:
Dans ce travail de thèse, nous étudions, dans un contexte d'analyse convexe et d'optimisation, la prise en compte des contraintes dites d'autocorrélation, c'est-à-dire : nous considérons les situations où les vecteurs représentant les variables à optimiser sont contraintes à être les coefficients d'autocorrélation d'un signal discret à support fini. Cet ensemble des vecteurs à composantes autocorrélées se trouve être un cône convexe ; nous essayons d'en établir le plus de propriétés possibles : concernant sa frontière (lisse/polyédrale), ses faces, l'acuité, l'expression du cône polaire, l'évaluation du cône normal en un point, etc. Ensuite, nous étudions divers algorithmes pour résoudre des problèmes d'optimisation où le cône des vecteurs à composantes autocorrélées entre en jeu. Notre principal objet d'étude est le problème de la projection sur ce cône, dont nous proposons la résolution par trois algorithmes différents : algorithmes dits de suivi de chemin, celui des projections alternées, et via une relaxation non-convexe. Enfin, nous abordons la généralisation de la situation d'autocorrélation au cas de signaux bi-dimensionnels, avec toute la complexité que cela engendre : multiples définitions possibles, non-convexité des problèmes résultants, et complexité calculatoire accrue pour les algorithmes.
22
Prodan, Ionela. "Control of Multi-Agent Dynamical Systems in the Presence of Constraints." Thesis, Supélec, 2012. http://www.theses.fr/2012SUPL0019/document.
Full textAbstract:
L'objectif de cette thèse est de proposer des solutions aux problèmes liés à la commande optimale de systèmes dynamiques multi-agents en présence de contraintes. Des éléments de la théorie de commande et d'optimisation sont appliqués à différents problèmes impliquant des formations de systèmes multi-agents. La thèse examine le cas d'agents soumis à des contraintes dynamiques. Pour faire face à ces problèmes, les concepts bien établis tels que la théorie des ensembles, la platitude différentielle, la commande prédictive (Model Predictive Control - MPC), la programmation mixte en nombres entiers (Mixed-Integer Programming - MIP) sont adaptés et améliorés. En utilisant ces notions théoriques, ce travail de thèse a porté sur les propriétés géométriques de la formation d'un groupe multi-agents et propose un cadre de synthèse original qui exploite cette structure. En particulier, le problème de conception de formation et les conditions d'évitement des collisions sont formulés comme des problèmes géométriques et d'optimisation pour lesquels il existe des procédures de résolution. En outre, des progrès considérables dans ce sens ont été obtenus en utilisant de façon efficace les techniques MIP (dans le but d'en déduire une description efficace des propriétés de non convexité et de non connexion d'une région de faisabilité résultant d'une collision de type multi-agents avec des contraintes d'évitement d'obstacles) et des propriétés de stabilité (afin d'analyser l'unicité et l'existence de configurations de formation de systèmes multi-agents). Enfin, certains résultats théoriques obtenus ont été appliqués dans un cas pratique très intéressant. On utilise une nouvelle combinaison de la commande prédictive et de platitude différentielle (pour la génération de référence) dans la commande et la navigation de véhicules aériens sans pilote (UAVs)The goal of this thesis is to propose solutions for the optimal control of multi-agent dynamical systems under constraints. Elements from control theory and optimization are merged together in order to provide useful tools which are further applied to different problems involving multi-agent formations. The thesis considers the challenging case of agents subject to dynamical constraints. To deal with these issues, well established concepts like set-theory, differential flatness, Model Predictive Control (MPC), Mixed-Integer Programming (MIP) are adapted and enhanced. Using these theoretical notions, the thesis concentrates on understanding the geometrical properties of the multi-agent group formation and on providing a novel synthesis framework which exploits the group structure. In particular, the formation design and the collision avoidance conditions are casted as geometrical problems and optimization-based procedures are developed to solve them. Moreover, considerable advances in this direction are obtained by efficiently using MIP techniques (in order to derive an efficient description of the non-convex, non-connected feasible region which results from multi-agent collision and obstacle avoidance constraints) and stability properties (in order to analyze the uniqueness and existence of formation configurations). Lastly, some of the obtained theoretical results are applied on a challenging practical application. A novel combination of MPC and differential flatness (for reference generation) is used for the flight control of Unmanned Aerial Vehicles (UAVs)
23
Flammarion, Nicolas. "Stochastic approximation and least-squares regression, with applications to machine learning." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLEE056/document.
Full textAbstract:
De multiples problèmes en apprentissage automatique consistent à minimiser une fonction lisse sur un espace euclidien. Pour l’apprentissage supervisé, cela inclut les régressions par moindres carrés et logistique. Si les problèmes de petite taille sont résolus efficacement avec de nombreux algorithmes d’optimisation, les problèmes de grande échelle nécessitent en revanche des méthodes du premier ordre issues de la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans une première partie, nous nous proposons de la minimiser grâce à un oracle stochastique. Dans une seconde partie, nous considérons deux de ses applications à l’apprentissage automatique : au partitionnement de données et à l’estimation sous contrainte de forme. La première contribution est un cadre unifié pour l’optimisation de fonctions quadratiques non-fortement convexes. Celui-ci comprend la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui combine les aspects positifs du moyennage et de l’accélération. La deuxième contribution est d’obtenir le taux optimal d’erreur de prédiction pour la régression par moindres carrés en fonction de la dépendance au bruit du problème et à l’oubli des conditions initiales. Notre nouvel algorithme est issu de la descente de gradient accélérée et moyennée. La troisième contribution traite de la minimisation de fonctions composites, somme de l’espérance de fonctions quadratiques et d’une régularisation convexe. Nous étendons les résultats existants pour les moindres carrés à toute régularisation et aux différentes géométries induites par une divergence de Bregman. Dans une quatrième contribution, nous considérons le problème du partitionnement discriminatif. Nous proposons sa première analyse théorique, une extension parcimonieuse, son extension au cas multi-labels et un nouvel algorithme ayant une meilleure complexité que les méthodes existantes. La dernière contribution de cette thèse considère le problème de la sériation. Nous adoptons une approche statistique où la matrice est observée avec du bruit et nous étudions les taux d’estimation minimax. Nous proposons aussi un estimateur computationellement efficaceMany problems in machine learning are naturally cast as the minimization of a smooth function defined on a Euclidean space. For supervised learning, this includes least-squares regression and logistic regression. While small problems are efficiently solved by classical optimization algorithms, large-scale problems are typically solved with first-order techniques based on gradient descent. In this manuscript, we consider the particular case of the quadratic loss. In the first part, we are interestedin its minimization when its gradients are only accessible through a stochastic oracle. In the second part, we consider two applications of the quadratic loss in machine learning: clustering and estimation with shape constraints. In the first main contribution, we provided a unified framework for optimizing non-strongly convex quadratic functions, which encompasses accelerated gradient descent and averaged gradient descent. This new framework suggests an alternative algorithm that exhibits the positive behavior of both averaging and acceleration. The second main contribution aims at obtaining the optimal prediction error rates for least-squares regression, both in terms of dependence on the noise of the problem and of forgetting the initial conditions. Our new algorithm rests upon averaged accelerated gradient descent. The third main contribution deals with minimization of composite objective functions composed of the expectation of quadratic functions and a convex function. Weextend earlier results on least-squares regression to any regularizer and any geometry represented by a Bregman divergence. As a fourth contribution, we consider the the discriminative clustering framework. We propose its first theoretical analysis, a novel sparse extension, a natural extension for the multi-label scenario and an efficient iterative algorithm with better running-time complexity than existing methods. The fifth main contribution deals with the seriation problem. We propose a statistical approach to this problem where the matrix is observed with noise and study the corresponding minimax rate of estimation. We also suggest a computationally efficient estimator whose performance is studied both theoretically and experimentally
24
Lorenz, Nicole. "Application of the Duality Theory." Doctoral thesis, Universitätsbibliothek Chemnitz, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-94108.
Full textAbstract:
The aim of this thesis is to present new results concerning duality in scalar optimization. We show how the theory can be applied to optimization problems arising in the theory of risk measures, portfolio optimization and machine learning.
First we give some notations and preliminaries we need within the thesis. After that we recall how the well-known Lagrange dual problem can be derived by using the general perturbation theory and give some generalized interior point regularity conditions used in the literature. Using these facts we consider some special scalar optimization problems having a composed objective function and geometric (and cone) constraints. We derive their duals, give strong duality results and optimality condition using some regularity conditions. Thus we complete and/or extend some results in the literature especially by using the mentioned regularity conditions, which are weaker than the classical ones. We further consider a scalar optimization problem having single chance constraints and a convex objective function. We also derive its dual, give a strong duality result and further consider a special case of this problem. Thus we show how the conjugate duality theory can be used for stochastic programming problems and extend some results given in the literature.
In the third chapter of this thesis we consider convex risk and deviation measures. We present some more general measures than the ones given in the literature and derive formulas for their conjugate functions. Using these we calculate some dual representation formulas for the risk and deviation measures and correct some formulas in the literature. Finally we proof some subdifferential formulas for measures and risk functions by using the facts above.
The generalized deviation measures we introduced in the previous chapter can be used to formulate some portfolio optimization problems we consider in the fourth chapter. Their duals, strong duality results and optimality conditions are derived by using the general theory and the conjugate functions, respectively, given in the second and third chapter. Analogous calculations are done for a portfolio optimization problem having single chance constraints using the general theory given in the second chapter. Thus we give an application of the duality theory in the well-developed field of portfolio optimization.
We close this thesis by considering a general Support Vector Machines problem and derive its dual using the conjugate duality theory. We give a strong duality result and necessary as well as sufficient optimality conditions. By considering different cost functions we get problems for Support Vector Regression and Support Vector Classification. We extend the results given in the literature by dropping the assumption of invertibility of the kernel matrix. We use a cost function that generalizes the well-known Vapnik's ε-insensitive loss and consider the optimization problems that arise by using this. We show how the general theory can be applied for a real data set, especially we predict the concrete compressive strength by using a special Support Vector Regression problem.
25
Tall, Abdoulaye. "Optimisation et Auto-Optimisation dans les réseaux LTE." Thesis, Avignon, 2015. http://www.theses.fr/2015AVIG0208/document.
Full textAbstract:
Le réseau mobile d’Orange France comprend plus de 100 000 antennes 2G, 3G et 4G sur plusieurs bandes de fréquences sans compter les nombreuses femto-cells fournies aux clients pour résoudre les problèmes de couverture. Ces chiffres ne feront que s’accroître pour répondre à la demande sans cesse croissante des clients pour les données mobiles. Cela illustre le défi énorme que rencontrent les opérateurs de téléphonie mobile en général à savoir gérer un réseau aussi complexe tout en limitant les coûts d’opération pour rester compétitifs. Cette thèse s’attache à utiliser le concept SON (réseaux auto-organisants) pour réduire cette complexité en automatisant les tâches répétitives ou complexes. Plus spécifiquement, nous proposons des algorithmes d’optimisation automatique pour des scénarios liés à la densification par les small cells ou les antennes actives. Nous abordons les problèmes classiques d’équilibrage de charge mais avec un lien backhaul à capacité limitée et de coordination d’interférence que ce soit dans le domaine temporel (notamment avec le eICIC) ou le domaine fréquentiel. Nous proposons aussi des algorithmes d’activation optimale de certaines fonctionnalités lorsque cette activation n’est pas toujours bénéfique. Pour la formulation mathématique et la résolution de tous ces algorithmes, nous nous appuyons sur les résultats de l’approximation stochastique et de l’optimisation convexe. Nous proposons aussi une méthodologie systématique pour la coordination de multiples fonctionnalités SON qui seraient exécutées en parallèle. Cette méthodologie est basée sur les jeux concaves et l’optimisation convexe avec comme contraintes des inégalités matricielles linéairesThe mobile network of Orange in France comprises more than 100 000 2G, 3G and 4G antennas with severalfrequency bands, not to mention many femto-cells for deep-indoor coverage. These numbers will continue toincrease in order to address the customers’ exponentially increasing need for mobile data. This is an illustrationof the challenge faced by the mobile operators for operating such a complex network with low OperationalExpenditures (OPEX) in order to stay competitive. This thesis is about leveraging the Self-Organizing Network(SON) concept to reduce this complexity by automating repetitive or complex tasks. We specifically proposeautomatic optimization algorithms for scenarios related to network densification using either small cells orActive Antenna Systems (AASs) used for Vertical Sectorization (VeSn), Virtual Sectorization (ViSn) and multilevelbeamforming. Problems such as load balancing with limited-capacity backhaul and interference coordination eitherin time-domain (eICIC) or in frequency-domain are tackled. We also propose optimal activation algorithms forVeSn and ViSn when their activation is not always beneficial. We make use of results from stochastic approximationand convex optimization for the mathematical formulation of the problems and their solutions. We also proposea generic methodology for the coordination of multiple SON algorithms running in parallel using results fromconcave game theory and Linear Matrix Inequality (LMI)-constrained optimization
26
Yen, Jou-An, and 顏柔安. "Projection Methods for Constrained Convex Optimization." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/73418791401906646487.
Full textAbstract:
碩士國立中山大學
應用數學系研究所
102
In this paper, we study the problem of finding a common minimizer of a finite family of constrained minimization problems. We convert this problem into an equivalent problem of finding a common fixed point of a finite family of nonexpansive mappings. Our methods are basically projection methods. We use three kinds of projection methods which are cyclic, parallel and successive, respectively. We prove that the sequence generated by each of these three projection methods weakly converges to an optimal solution of the problem.
27
Espinoza, Francisco. "A New Interpolation Approach for Linearly Constrained Convex Optimization." Thesis, 2012. http://hdl.handle.net/10754/244891.
Full textAbstract:
In this thesis we propose a new class of Linearly Constrained Convex Optimization
methods based on the use of a generalization of Shepard's interpolation formula. We
prove the properties of the surface such as the interpolation property at the boundary
of the feasible region and the convergence of the gradient to the null space of the
constraints at the boundary. We explore several descent techniques such as steepest
descent, two quasi-Newton methods and the Newton's method. Moreover, we implement
in the Matlab language several versions of the method, particularly for the
case of Quadratic Programming with bounded variables. Finally, we carry out performance
tests against Matab Optimization Toolbox methods for convex optimization
and implementations of the standard log-barrier and active-set methods. We conclude
that the steepest descent technique seems to be the best choice so far for our
method and that it is competitive with other standard methods both in performance
and empirical growth order.
28
"Approximation algorithms for Lp-ball and quadratically constrained polynomial optimization problems." 2013. http://library.cuhk.edu.hk/record=b6115682.
Full textAbstract:
本论文着重研究了带有Lp模球约束以及二次约束的多项式优化问题的计算复杂度以及关于此类问题的近似算法。在本论文中，利用张量对称化的技巧，我们首次证明了当P∈ [2 ，∞] ，任意高阶的带有Lp模球约束的多项式优化问题均为NP 困难。借助模的对偶性质，我们将这类优化问题转化为求解凸体半径的问题，从而使得我们获得了之前研究所无法使用的算法工具。具体来说，利用计算凸几何的算法工具，对于Lp模球约束的多项式优化问题，我们得到了近似比为[附圖]的确定性多项式时间近似算法，其中d为目标多项式的阶次， n 为问题的维度。使用随机算法，我们将近似比进一步提高为此类问题的己知最优值。[附圖]。此外，我们发展了计算凸几何当中对于凸体半径的计算方法，从而设计出了一种对二次约束多项式优化问题近似比为[附圖]的近似算法，其中m为问题的约束个数。我们的结果涵盖并提高了之前关于此类问题的研究结果。我们相信在本论文中使用的新的算法工具，将在今后的多项式优化问题研究中得到更广泛的应用。In this thesis, we present polynomial time approximation algorithms for solving various homogeneous polynomial optimization problems and their multilinear relaxations. Specifically, for the problems with Lp ball constraint, where P∈ [2 ，∞], by reducing them to that of determining the Lq-diameter of certain convex body, we show that they can be approximated to within a factor of [with formula] in deterministic polynomial time, where q = p=(p - 1) is the conjugate of p, n is the number of variables, and d is the degree of the polynomial. We further show that with the help of randomization, the approximation guarantee can be improved to [with formula], which is independent of p and is currently the best for the aforementioned problems. Moreover, we extend the argument of deterministic algorithm mentioned above to solve the quadratically constrained polynomial optimization problems. In particular, for any intersection of ellipsoids K, we can, in polynomial time, construct a random polytope P, which satisfies [with formula]. Then, by reducing the problem to that of evaluating the maximum polytopal norm [with formula] induced by P, over certain convex body, we can approximate the quadratically constrained problem within a factor of [with formula] in polynomial time. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where [with formula]. We believe that the wide array of tools used in this thesis will have further applications in the study of polynomial optimization problems.
Detailed summary in vernacular field only.
Hou, Ke.
On title page "p" is subscript.
Thesis (Ph.D.) Chinese University of Hong Kong, 2013.
Includes bibliographical references (leaves 106-111).
Abstracts also in Chinese.
29
"A value estimation approach to Iri-Imai's method for constrained convex optimization." 2002. http://library.cuhk.edu.hk/record=b5891236.
Full textAbstract:
Lam Sze Wan.Thesis (M.Phil.)--Chinese University of Hong Kong, 2002.
Includes bibliographical references (leaves 93-95).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Background --- p.4
Chapter 3 --- Review of Iri-Imai Algorithm for Convex Programming Prob- lems --- p.10
Chapter 3.1 --- Iri-Imai Algorithm for Convex Programming --- p.11
Chapter 3.2 --- Numerical Results --- p.14
Chapter 3.2.1 --- Linear Programming Problems --- p.15
Chapter 3.2.2 --- Convex Quadratic Programming Problems with Linear Inequality Constraints --- p.17
Chapter 3.2.3 --- Convex Quadratic Programming Problems with Con- vex Quadratic Inequality Constraints --- p.18
Chapter 3.2.4 --- Summary of Numerical Results --- p.21
Chapter 3.3 --- Chapter Summary --- p.22
Chapter 4 --- Value Estimation Approach to Iri-Imai Method for Con- strained Optimization --- p.23
Chapter 4.1 --- Value Estimation Function Method --- p.24
Chapter 4.1.1 --- Formulation and Properties --- p.24
Chapter 4.1.2 --- Value Estimation Approach to Iri-Imai Method --- p.33
Chapter 4.2 --- "A New Smooth Multiplicative Barrier Function Φθ+,u" --- p.35
Chapter 4.2.1 --- Formulation and Properties --- p.35
Chapter 4.2.2 --- "Value Estimation Approach to Iri-Imai Method by Us- ing Φθ+,u" --- p.41
Chapter 4.3 --- Convergence Analysis --- p.43
Chapter 4.4 --- Numerical Results --- p.46
Chapter 4.4.1 --- Numerical Results Based on Algorithm 4.1 --- p.46
Chapter 4.4.2 --- Numerical Results Based on Algorithm 4.2 --- p.50
Chapter 4.4.3 --- Summary of Numerical Results --- p.59
Chapter 4.5 --- Chapter Summary --- p.60
Chapter 5 --- Extension of Value Estimation Approach to Iri-Imai Method for More General Constrained Optimization --- p.61
Chapter 5.1 --- Extension of Iri-Imai Algorithm 3.1 for More General Con- strained Optimization --- p.62
Chapter 5.1.1 --- Formulation and Properties --- p.62
Chapter 5.1.2 --- Extension of Iri-Imai Algorithm 3.1 --- p.63
Chapter 5.2 --- Extension of Value Estimation Approach to Iri-Imai Algo- rithm 4.1 for More General Constrained Optimization --- p.64
Chapter 5.2.1 --- Formulation and Properties --- p.64
Chapter 5.2.2 --- Value Estimation Approach to Iri-Imai Method --- p.67
Chapter 5.3 --- Extension of Value Estimation Approach to Iri-Imai Algo- rithm 4.2 for More General Constrained Optimization --- p.69
Chapter 5.3.1 --- Formulation and Properties --- p.69
Chapter 5.3.2 --- Value Estimation Approach to Iri-Imai Method --- p.71
Chapter 5.4 --- Numerical Results --- p.72
Chapter 5.4.1 --- Numerical Results Based on Algorithm 5.1 --- p.73
Chapter 5.4.2 --- Numerical Results Based on Algorithm 5.2 --- p.76
Chapter 5.4.3 --- Numerical Results Based on Algorithm 5.3 --- p.78
Chapter 5.4.4 --- Summary of Numerical Results --- p.86
Chapter 5.5 --- Chapter Summary --- p.87
Chapter 6 --- Conclusion --- p.88
Bibliography --- p.93
Chapter A --- Search Directions --- p.96
Chapter A.1 --- Newton's Method --- p.97
Chapter A.1.1 --- Golden Section Method --- p.99
Chapter A.2 --- Gradients and Hessian Matrices --- p.100
Chapter A.2.1 --- Gradient of Φθ(x) --- p.100
Chapter A.2.2 --- Hessian Matrix of Φθ(x) --- p.101
Chapter A.2.3 --- Gradient of Φθ(x) --- p.101
Chapter A.2.4 --- Hessian Matrix of φθ (x) --- p.102
Chapter A.2.5 --- Gradient and Hessian Matrix of Φθ(x) in Terms of ∇xφθ (x) and∇2xxφθ (x) --- p.102
Chapter A.2.6 --- "Gradient of φθ+,u(x)" --- p.102
Chapter A.2.7 --- "Hessian Matrix of φθ+,u(x)" --- p.103
Chapter A.2.8 --- "Gradient and Hessian Matrix of Φθ+,u(x) in Terms of ∇xφθ+,u(x)and ∇2xxφθ+,u(x)" --- p.103
Chapter A.3 --- Newton's Directions --- p.103
Chapter A.3.1 --- Newton Direction of Φθ (x) in Terms of ∇xφθ (x) and ∇2xxφθ(x) --- p.104
Chapter A.3.2 --- "Newton Direction of Φθ+,u(x) in Terms of ∇xφθ+,u(x) and ∇2xxφθ,u(x)" --- p.104
Chapter A.4 --- Feasible Descent Directions for the Minimization Problems (Pθ) and (Pθ+) --- p.105
Chapter A.4.1 --- Feasible Descent Direction for the Minimization Prob- lems (Pθ) --- p.105
Chapter A.4.2 --- Feasible Descent Direction for the Minimization Prob- lems (Pθ+) --- p.107
Chapter B --- Randomly Generated Test Problems for Positive Definite Quadratic Programming --- p.109
Chapter B.l --- Convex Quadratic Programming Problems with Linear Con- straints --- p.110
Chapter B.l.1 --- General Description of Test Problems --- p.110
Chapter B.l.2 --- The Objective Function --- p.112
Chapter B.l.3 --- The Linear Constraints --- p.113
Chapter B.2 --- Convex Quadratic Programming Problems with Quadratic In- equality Constraints --- p.116
Chapter B.2.1 --- The Quadratic Constraints --- p.117
30
Donnelly, Catherine. "Convex duality in constrained mean-variance portfolio optimization under a regime-switching model." Thesis, 2008. http://hdl.handle.net/10012/4004.
Full textAbstract:
In this thesis, we solve a mean-variance portfolio optimization problem with portfolio constraints under a regime-switching model. Specifically, we seek a portfolio process which minimizes the variance of the terminal wealth, subject to a terminal wealth constraint and convex portfolio constraints. The regime-switching is modeled using a finite state space, continuous-time Markov chain and the market parameters are allowed to be random processes. The solution to this problem is of interest to investors in financial markets, such as pension funds, insurance companies and individuals.
We establish the existence and characterization of the solution to the given problem using a convex duality method. We encode the constraints on the given problem as static penalty functions in order to derive the primal problem. Next, we synthesize the dual problem from the primal problem using convex conjugate functions. We show that the solution to the dual problem exists. From the construction of the dual problem, we find a set of necessary and sufficient conditions for the primal and dual problems to each have a solution. Using these conditions, we can show the existence of the solution to the given problem and characterize it in terms of the market parameters and the solution to the dual problem.
The results of the thesis lay the foundation to find an actual solution to the given problem, by looking at specific examples. If we can find the solution to the dual problem for a specific example, then, using the characterization of the solution to the given problem, we may be able to find the actual solution to the specific example.
In order to use the convex duality method, we have to prove a martingale representation theorem for processes which are locally square-integrable martingales with respect to the filtration generated by a Brownian motion and a finite state space, continuous-time Markov chain. This result may be of interest in problems involving regime-switching models which require a martingale representation theorem.
31
Li, Zhuo. "Distributed model predictive control based consensus of general linear multi-agent systems with input constraints." Thesis, 2020. http://hdl.handle.net/1828/11683.
Full textAbstract:
In the study of multi-agent systems (MASs), cooperative control is one of the most fundamental issues. As it covers a broad spectrum of applications in many industrial areas, there is a desire to design cooperative control protocols for different system and network setups.
Motivated by this fact, in this thesis we focus on elaborating consensus protocol design, via model predictive control (MPC), under two different scenarios: (1) general constrained linear MASs with bounded additive disturbance; (2) linear MASs with input constraints underlying distributed communication networks.
In Chapter 2, a tube-based robust MPC consensus protocol for constrained linear MASs is proposed. For undisturbed linear MASs without constraints, the results on designing a centralized linear consensus protocol are first developed by a suboptimal linear quadratic approach. In order to evaluate the control performance of the suboptimal consensus protocol, we use an infinite horizon linear quadratic objective function to penalize the disagreement among agents and the size of control inputs. Due to the non-convexity of the performance function, an optimal controller gain is difficult or even impossible to find, thus a suboptimal consensus protocol is derived. In the presence of disturbance, the original MASs may not maintain certain properties such as stability and cooperative performance. To this end, a tube-based robust MPC framework is introduced. When disturbance is involved, the original constraints in nominal prediction should be tightened so as to achieve robust constraint satisfaction, as the predicted states and the actual states are not necessarily the same. Moreover, the corresponding robust constraint sets can be determined offline, requiring no extra iterative online computation in implementation.
In Chapter 3, a novel distributed MPC-based consensus protocol is proposed for general linear MASs with input constraints. For the linear MAS without constraints, a pre-stabilizing distributed linear consensus protocol is developed by an inverse optimal approach, such that the corresponding closed-loop system is asymptotically stable with respect to a consensus set. Implementing this pre-stabilizing controller in a distributed digital setting is however not possible, as it requires every local decision maker to continuously access the state of their neighbors simultaneously when updating the control input. To relax these requirements, the assumed neighboring state, instead of the actual state of neighbors, is used. In our distributed MPC scheme, each local controller minimizes a group of control variables to generate control input. Moreover, an additional state constraint is proposed to bound deviation between the actual and the assumed state. In this way, consistency is enforced between intended behaviors of an agent and what its neighbors believe it will behave. We later show that the closed-loop system converges to a neighboring set of the consensus set thanks to the bounded state deviation in prediction.
In Chapter 4, conclusions are made and some research topics for future exploring are presented.Graduate
2021-03-31
32
Alsaif, Muhanned. "New Algorithms to Solve the Positioning Problem of Outdoor Localization Using Constrained and Unconstrained Optimization Techniques." Thesis, 2021. http://hdl.handle.net/10754/670250.
Full textAbstract:
The demand for outdoor precise location is increasing with the development of new applications such as autonomous vehicles, exploration robots and wireless sensor networks. Global Navigation Satellite System (GNSS) is the go-to system for outdoor localization. This thesis focuses on developing new methods for GNSS single-point positioning (SPP) model, where no access to a reference station or precise GNSS parameters is needed. We investigated the limitations of the standard method, least- squares adjustment (LSA), and we derived the Cramer-Rao bounds for the SPP estimation problem. We also investigated different techniques to formulate the positioning problem with the goal to increase the accuracy. A new method is developed by reformulating the problem as difference-of-convex program (DC program) and utilizing convex-concave procedure (CCCP) to solve the positioning problem without linearizing the observation equations. In addition, we examined the potential of multiple-receiver systems in increasing the accuracy. We formulated the multiple- receiver SPP estimation problem, and we proposed to configure the multiple receivers in a fixed equilateral triangle to exploit the symmetry and the geometrical constraints of the configuration. We extended the use of LSA in multiple-receiver system. We also developed a modification of LSA algorithm, named least-squares adjustment extension
(LSAE), that utilizes attitude information and the constraints of the multiple-receiver system. In addition, we developed a new algorithm to optimizes the SPP estimates over the equilateral triangles Riemannian manifold, which enforces the geometrical constraints of the multiple-receiver system. Furthermore, we derived the constrained and the unconstrained Cramer-Rao bounds (CRB and CCRB) for the multiple-receiver SPP problem. Moreover, we investigated the influence of both attitude information and the equilateral triangle baseline length on the algorithms’ performances and the derived CCRB. Finally, we carried out a numerical analysis by implementing the algorithms and the bounds in MATLAB, where we tested the algorithms on simulated GNSS scenarios. The proposed multiple-receiver methods provide more precise estimates for the SPP
problem in comparison to the single receiver methods.
33
Hung, Hsi, and 洪勗. "UFO: Unified Convex Optimization Algorithms for Fixed-Outline Floorplanning with Pre-placed Constraint." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/38042143644804472665.
Full textAbstract:
碩士國立成功大學
電機工程學系碩博士班
97
Fixed-outline floorplanning has attracted more attention for the real requirement in current IC design flow. In addition, there may exist several pre-placed modules in the specified region. In order to get a feasible foorplan, a floorplanner should have the ability to consider these constraints, which makes foorplanning a more difficult problem. In this thesis, we propose a it first work to consider pre-placed modules in a fixed-outline floorplan. Two-stages unified convex optimization methods, called UFO, are used in a global distribution and a local legalization stages, respectively. In the first stage, a pull-push model is used to distribute modules over a fixed outline under the wirelength consideration. In the second stage, the geometrical relations between modules are extracted by applying the Delaunay triangulation method on the result of the first stage. Then, a quadratic function as well as the constraint graphs are used to determine the locations and shapes of modules so that no module overlaps and all modules are in the outline. Experimental results have demonstrated that UFO clearly outperforms the results reported in the literature on the GSRC benchmarks.
34
Deng, Huizhong. "Shape Clustering and Spatial-temporal Constraint for Non-rigid Structure from Motion." Master's thesis, 2017. http://hdl.handle.net/1885/113634.
Full textAbstract:
Non-rigid Structure-from-Motion (NRSfM) is an active research eld in computer
vision. The task of NRSfM is to simultaneously recover camera motion and 3D
structure from 2D tracks of a deformable object. This problem is generally categorized
into sparse and dense cases in terms of scale, where sparse NRSfM deals with
a few feature tracks and dense NRSfM recovers the 3D position of each pixel in
an image
ow. As NRSfM is essentially an under-constrained problem, recent research
has focused on enforcing priors to reliably solve the problem. In this thesis,
we propose a shape clustering method for sparse NRSfM and a spatial-temporal
constraint for dense NRSfM.
For sparse NRSfM, we rst revisit the concept of \reconstructability", which
indicates the possibility of reconstructing a 3D shape, given 2D feature tracks and
camera motion. We give an extension to it and de ne \reconstructability" from
3D shape complexity and motion complexity. To increase global reconstructability,
we then propose an iterative shape clustering method to divide a sequence into
several sub-sequences, thus decreasing the shape complexity of each sub-sequence,
which is much easier to solve individually. Our method aims at solving the longterm,
complex motions, which have been a di cult task for previous methods.
Experimental results show that our method outperforms the current state-of-theart
methods by a margin, thus pushing the limit of sparse NRSfM.
For dense NRSfM, we rst revisit the temporal smoothness utilized in sparse
NRSfM and demonstrate that it can be employed for dense case directly. Secondly,
we propose a spatial smoothness constraint by enforcing a Laplacian lter to the
shape matrix. Finally, to handle real world noise and outliers in measurements,
we robustify the data term by using the L1 norm. Our method gives a simple
yet elegant convex least-squares optimization, which can be e ectively solved by
gradient descent. Experimental results on both synthetic and real images show
that the proposed method achieves state-of-the-art performance in dense NRSfM.
35
Demir, Nazlı. "Decentralized probabilistic density control of swarm of autonomous agents with conflict avoidance constraints." Thesis, 2014. http://hdl.handle.net/2152/26210.
Full textAbstract:
This report describes a method to control the density distribution of a large number of autonomous agents. The approach is based on the fact that there are a large number of agents in the system, and hence the time evolution of the probabilistic density distribution of agents can be described as a Markov chain. The main contribution of this paper is the synthesis of a Markov matrix which will guide the multi-agent system density to a desired steady-state density distribution, in a probabilistic sense, while satisfying some motion and safety constraints. Also, an adaptive density control method based on real time density feedback is introduced to synthesize a time-varying Markov ma- trix, which leads to better convergence to the desired density distribution. Finally, a decentralized density computation method is described. This method guarantees that all agents will have a best, and common, density estimate in a finite, with an explicit bound, number of communication updates.text
36
Cai, Pei Li. "Spectrum Sharing in Cognitive Radio Systems Under Outage Probablility Constraint." 2009. http://hdl.handle.net/1969.1/ETD-TAMU-2009-12-7463.
Full textAbstract:
For traditional wireless communication systems, static spectrum allocation is
the major spectrum allocation methodology. However, according to the recent investigations
by the FCC, this has led to more than 70 percent of the allocated spectrum in the
United States being under-utilized. Cognitive radio (CR) technology, which supports
opportunistic spectrum sharing, is one idea that is proposed to improve the overall
utilization efficiency of the radio spectrum.
In this thesis we consider a CR communication system based on spectrum sharing
schemes, where we have a secondary user (SU) link with multiple transmitting antennas
and a single receiving antenna, coexisting with a primary user (PU) link with
a single receiving antenna. At the SU transmitter (SU-Tx), the channel state information
(CSI) of the SU link is assumed to be perfectly known; while the interference
channel from the SU-Tx to the PU receiver (PU-Rx) is not perfectly known due to
less cooperation between the SU and the PU. As such, the SU-Tx is only assumed to
know that the interference channel gain can take values from a finite set with certain
probabilities. Considering a SU transmit power constraint, our design objective is to
determine the transmit covariance matrix that maximizes the SU rate, while we protect
the PU by enforcing both a PU average interference constraint and a PU outage
probability constraint. This problem is first formulated as a non-convex optimization
problem with a non-explicit probabilistic constraint, which is then approximated as
a mixed binary integer programming (MBIP) problem and solved with the Branch and Bound (BB) algorithm. The complexity of the BB algorithm is analyzed and numerical
results are presented to validate the eff ectiveness of the proposed algorithm.
A key result proved in this thesis is that the rank of the optimal transmit covariance
matrix is one, i.e., CR beamforming is optimal under PU outage constraints.
Finally, a heuristic algorithm is proposed to provide a suboptimal solution to our
MBIP problem by efficiently (in polynomial time) solving a particularly-constructed
convex problem.
37
Heinrich, André. "Fenchel duality-based algorithms for convex optimization problems with applications in machine learning and image restoration." Doctoral thesis, 2012. https://monarch.qucosa.de/id/qucosa%3A19869.
Full textAbstract:
The main contribution of this thesis is the concept of Fenchel duality with a focus on its application in the field of machine learning problems and image restoration tasks. We formulate a general optimization problem for modeling support vector machine tasks and assign a Fenchel dual problem to it, prove weak and strong duality statements as well as necessary and sufficient optimality conditions for that primal-dual pair. In addition, several special instances of the general optimization problem are derived for different choices of loss functions for both the regression and the classifification task. The convenience of these approaches is demonstrated by numerically solving several problems. We formulate a general nonsmooth optimization problem and assign a Fenchel dual problem to it. It is shown that the optimal objective values of the primal and the dual one coincide and that the primal problem has an optimal solution under certain assumptions. The dual problem turns out to be nonsmooth in general and therefore a regularization is performed twice to obtain an approximate dual problem that can be solved efficiently via a fast gradient algorithm. We show how an approximate optimal and feasible primal solution can be constructed by means of some sequences of proximal points closely related to the dual iterates. Furthermore, we show that the solution will indeed converge to the optimal solution of the primal for arbitrarily small accuracy. Finally, the support vector regression task is obtained to arise as a particular case of the general optimization problem and the theory is specialized to this problem. We calculate several proximal points occurring when using difffferent loss functions as well as for some regularization problems applied in image restoration tasks. Numerical experiments illustrate the applicability of our approach for these types of problems.
38
Lorenz, Nicole. "Application of the Duality Theory: New Possibilities within the Theory of Risk Measures, Portfolio Optimization and Machine Learning." Doctoral thesis, 2011. https://monarch.qucosa.de/id/qucosa%3A19760.
Full textAbstract:
The aim of this thesis is to present new results concerning duality in scalar optimization. We show how the theory can be applied to optimization problems arising in the theory of risk measures, portfolio optimization and machine learning.
First we give some notations and preliminaries we need within the thesis. After that we recall how the well-known Lagrange dual problem can be derived by using the general perturbation theory and give some generalized interior point regularity conditions used in the literature. Using these facts we consider some special scalar optimization problems having a composed objective function and geometric (and cone) constraints. We derive their duals, give strong duality results and optimality condition using some regularity conditions. Thus we complete and/or extend some results in the literature especially by using the mentioned regularity conditions, which are weaker than the classical ones. We further consider a scalar optimization problem having single chance constraints and a convex objective function. We also derive its dual, give a strong duality result and further consider a special case of this problem. Thus we show how the conjugate duality theory can be used for stochastic programming problems and extend some results given in the literature.
In the third chapter of this thesis we consider convex risk and deviation measures. We present some more general measures than the ones given in the literature and derive formulas for their conjugate functions. Using these we calculate some dual representation formulas for the risk and deviation measures and correct some formulas in the literature. Finally we proof some subdifferential formulas for measures and risk functions by using the facts above.
The generalized deviation measures we introduced in the previous chapter can be used to formulate some portfolio optimization problems we consider in the fourth chapter. Their duals, strong duality results and optimality conditions are derived by using the general theory and the conjugate functions, respectively, given in the second and third chapter. Analogous calculations are done for a portfolio optimization problem having single chance constraints using the general theory given in the second chapter. Thus we give an application of the duality theory in the well-developed field of portfolio optimization.
We close this thesis by considering a general Support Vector Machines problem and derive its dual using the conjugate duality theory. We give a strong duality result and necessary as well as sufficient optimality conditions. By considering different cost functions we get problems for Support Vector Regression and Support Vector Classification. We extend the results given in the literature by dropping the assumption of invertibility of the kernel matrix. We use a cost function that generalizes the well-known Vapnik's ε-insensitive loss and consider the optimization problems that arise by using this. We show how the general theory can be applied for a real data set, especially we predict the concrete compressive strength by using a special Support Vector Regression problem.
39
Akhil, P. T. "Topics in Network Utility Maximization : Interior Point and Finite-step Methods." Thesis, 2017. http://hdl.handle.net/2005/3268.
Full textAbstract:
Network utility maximization has emerged as a powerful tool in studying flow control, resource allocation and other cross-layer optimization problems. In this work, we study a flow control problem in the optimization framework. The objective is to maximize the sum utility of the users subject to the flow constraints of the network. The utility maximization is solved in a distributed setting; the network operator does not know the user utility functions and the users know neither the rate choices of other users nor the flow constraints of the network.
We build upon a popular decomposition technique proposed by Kelly [Eur. Trans. Telecommun., 8(1), 1997] to solve the utility maximization problem in the aforementioned distributed setting. The technique decomposes the utility maximization problem into a user problem, solved by each user and a network problem solved by the network. We propose an iterative algorithm based on this decomposition technique. In each iteration, the users communicate to the network their willingness to pay for the network resources. The network allocates rates in a proportionally fair manner based on the prices communicated by the users. The new feature of the proposed algorithm is that the rates allocated by the network remains feasible at all times. We show that the iterates put out by the algorithm asymptotically tracks a differential inclusion. We also show that the solution to the differential inclusion converges to the system optimal point via Lyapunov theory. We use a popular benchmark algorithm due to Kelly et al. [J. of the Oper. Res. Soc., 49(3), 1998] that involves fast user updates coupled with slow network updates in the form of additive increase and multiplicative decrease of the user flows. The proposed algorithm may be viewed as one with fast user update and fast network update that keeps the iterates feasible at all times. Simulations suggest that our proposed algorithm converges faster than the aforementioned benchmark algorithm.
When the flows originate or terminate at a single node, the network problem is the maximization of a so-called d-separable objective function over the bases of a
polymatroid. The solution is the lexicographically optimal base of the
polymatroid. We map the problem of finding the lexicographically optimal base of
a polymatroid to the geometrical problem of finding the concave cover of a set of points on a two-dimensional plane. We also describe an algorithm that finds the concave cover in linear time.
Next, we consider the minimization of a more general objective function, i.e., a separable convex function, over the bases of a polymatroid with a special structure. We propose a novel decomposition algorithm and show the proof of correctness and optimality of the algorithm via the theory of polymatroids. Further, motivated by the need to handle piece-wise linear concave utility functions, we extend the decomposition algorithm to handle the case when the separable convex functions are not continuously differentiable or not strictly convex. We then provide a proof of its correctness and optimality.
40
Georgiou, Konstantinos. "Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations." Thesis, 2010. http://hdl.handle.net/1807/26271.
Full textAbstract:
The inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation.
Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems.
In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following:
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon.
The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull.
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations.
We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology.
Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution.
We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.