Spelling suggestions: "subject:"convex optimization"" "subject:"konvex optimization""
41 
Convex Optimization Methods for System IdentificationDautbegovic, Dino January 2014 (has links)
The extensive use of a leastsquares problem formulation in many fields is partly motivated by the existence of an analytic solution formula which makes the theory comprehensible and readily applicable, but also easily embedded in computeraided design or analysis tools. While the mathematics behind convex optimization has been studied for about a century, several recent researches have stimulated a new interest in the topic. Convex optimization, being a special class of mathematical optimization problems, can be considered as generalization of both leastsquares and linear programming. As in the case of a linear programming problem there is in general no simple analytical formula that can be used to find the solution of a convex optimization problem. There exists however efficient methods or software implementations for solving a large class of convex problems. The challenge and the state of the art in using convex optimization comes from the difficulty in recognizing and formulating the problem. The main goal of this thesis is to investigate the potential advantages and benefits of convex optimization techniques in the field of system identification. The primary work focuses on parametric discretetime system identification models in which we assume or choose a specific model structure and try to estimate the model parameters for best fit using experimental inputoutput (IO) data. By developing a working knowledge of convex optimization and treating the system identification problem as a convex optimization problem will allow us to reduce the uncertainties in the parameter estimation. This is achieved by reecting prior knowledge about the system in terms of constraint functions in the leastsquares formulation.

42 
Adaptive Load Management: MultiLayered And MultiTemporal Optimization Of The Demand Side In Electric Energy SystemsJoo, JhiYoung 01 September 2013 (has links)
Welldesigned demand response is expected to play a vital role in operatingpower systems by reducing economic and environmental costs. However,the current system is operated without much information on the benefits ofendusers, especially the small ones, who use electricity. This thesis proposes aframework of operating power systems with demand models including the diversityof endusers’ benefits, namely adaptive load management (ALM). Sincethere are a large number of endusers having different preferences and conditionsin energy consumption, the information on the endusers’ benefits needsto be aggregated at the system level. This leads us to model the system ina multilayered way, including endusers, load serving entities, and a systemoperator. On the other hand, the information of the endusers’ benefits can beuncertain even to the endusers themselves ahead of time. This information isdiscovered incrementally as the actual consumption approaches and occurs. Forthis reason ALM requires a multitemporal model of a system operation andendusers’ benefits within. Due to the different levels of uncertainty along thedecisionmaking time horizons, the risks from the uncertainty of informationon both the system and the endusers need to be managed. The methodologyof ALM is based on Lagrange dual decomposition that utilizes interactive communicationbetween the system, load serving entities, and endusers. We showthat under certain conditions, a power system with a large number of enduserscan balance at its optimum efficiently over the horizon of a day ahead of operationto near real time. Numerical examples include designing ALM for theright types of loads over different time horizons, and balancing a system with a large number of different loads on a congested network. We conclude thatwith the right information exchange by each entity in the system over differenttime horizons, a power system can reach its optimum including a variety ofendusers’ preferences and their values of consuming electricity.

43 
BEAMFORMING TECHNIQUES USING CONVEX OPTIMIZATION / Beamforming using CVXJangam, Ravindra nath vijay kumar January 2014 (has links)
The thesis analyses and validates Beamforming methods using Convex Optimization. CVX which is a Matlab supported tool for convex optimization has been used to develop this concept. An algorithm is designed by which an appropriate system has been identified by varying parameters such as number of antennas, passband width, and stopbands widths of a beamformer. We have observed the beamformer by minimizing the error for Leastsquare and Infinity norms. A graph obtained by the optimum values between leastsquare and infinity norms shows us a tradeoff between these two norms. We have observed convex optimization for double passband of a beamformer which has proven the flexibility of convex optimization. On extension for this, we designed a filter in which stopband is arbitrary. A constraint is used by which the stopband would be varying depending upon the upper boundary (limiting) line which varies w.r.t yaxis (dB). The beamformer has been observed for feasibility by varying parameters such as number of antennas, arbitrary upper boundaries, stopbands and passband. This proves that there is flexibility for designing a beamformer as desired.

44 
Decentralized probabilistic density control of swarm of autonomous agents with conflict avoidance constraintsDemir, Nazlı 01 October 2014 (has links)
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 multiagent system density to a desired steadystate 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 timevarying 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

45 
Unifying LowRank Models for Visual LearningCabral, Ricardo da Silveira 01 February 2015 (has links)
Many problems in signal processing, machine learning and computer vision can be solved by learning low rank models from data. In computer vision, problems such as rigid structure from motion have been formulated as an optimization over subspaces with fixed rank. These hardrank constraints have traditionally been imposed by a factorization that parameterizes subspaces as a product of two matrices of fixed rank. Whilst factorization approaches lead to efficient and kernelizable optimization algorithms, they have been shown to be NPHard in presence of missing data. Inspired by recent work in compressed sensing, hardrank constraints have been replaced by softrank constraints, such as the nuclear norm regularizer. Visavis hardrank approaches, softrank models are convex even in presence of missing data: but how is convex optimization solving a NPHard problem? This thesis addresses this question by analyzing the relationship between hard and soft rank constraints in the unsupervised factorization with missing data problem. Moreover, we extend soft rank models to weakly supervised and fully supervised learning problems in computer vision. There are four main contributions of our work: (1) The analysis of a new unified lowrank model for matrix factorization with missing data. Our model subsumes soft and hardrank approaches and merges advantages from previous formulations, such as efficient algorithms and kernelization. It also provides justifications on the choice of algorithms and regions that guarantee convergence to global minima. (2) A deterministic \rank continuation" strategy for the NPhard unsupervised factorization with missing data problem, that is highly competitive with the stateoftheart and often achieves globally optimal solutions. In preliminary work, we show that this optimization strategy is applicable to other NPhard problems which are typically relaxed to convex semidentite programs (e.g., MAXCUT, quadratic assignment problem). (3) A new softrank fully supervised robust regression model. This convex model is able to deal with noise, outliers and missing data in the input variables. (4) A new softrank model for weakly supervised image classification and localization. Unlike existing multipleinstance approaches for this problem, our model is convex.

46 
Accelerating Convergence of Largescale Optimization AlgorithmsGhadimi, Euhanna January 2015 (has links)
Several recent engineering applications in multiagent systems, communication networks, and machine learning deal with decision problems that can be formulated as optimization problems. For many of these problems, new constraints limit the usefulness of traditional optimization algorithms. In some cases, the problem size is much larger than what can be conveniently dealt with using standard solvers. In other cases, the problems have to be solved in a distributed manner by several decisionmakers with limited computational and communication resources. By exploiting problem structure, however, it is possible to design computationally efficient algorithms that satisfy the implementation requirements of these emerging applications. In this thesis, we study a variety of techniques for improving the convergence times of optimization algorithms for largescale systems. In the first part of the thesis, we focus on multistep firstorder methods. These methods add memory to the classical gradient method and account for past iterates when computing the next one. The result is a computationally lightweight acceleration technique that can yield significant improvements over gradient descent. In particular, we focus on the Heavyball method introduced by Polyak. Previous studies have quantified the performance improvements over the gradient through a local convergence analysis of twice continuously differentiable objective functions. However, the convergence properties of the method on more general convex cost functions has not been known. The first contribution of this thesis is a global convergence analysis of the Heavy ball method for a variety of convex problems whose objective functions are strongly convex and have Lipschitz continuous gradient. The second contribution is to tailor the Heavy ball method to network optimization problems. In such problems, a collection of decision makers collaborate to find the decision vector that minimizes the total system cost. We derive the optimal stepsizes for the Heavyball method in this scenario, and show how the optimal convergence times depend on the individual cost functions and the structure of the underlying interaction graph. We present three engineering applications where our algorithm significantly outperform the tailormade stateoftheart algorithms. In the second part of the thesis, we consider the Alternating Direction Method of Multipliers (ADMM), an alternative powerful method for solving structured optimization problems. The method has recently attracted a large interest from several engineering communities. Despite its popularity, its optimal parameters have been unknown. The third contribution of this thesis is to derive optimal parameters for the ADMM algorithm when applied to quadratic programming problems. Our derivations quantify how the Hessian of the cost functions and constraint matrices affect the convergence times. By exploiting this information, we develop a preconditioning technique that allows to accelerate the performance even further. Numerical studies of modelpredictive control problems illustrate significant performance benefits of a welltuned ADMM algorithm. The fourth and final contribution of the thesis is to extend our results on optimal scaling and parameter tuning of the ADMM method to a distributed setting. We derive optimal algorithm parameters and suggest heuristic methods that can be executed by individual agents using local information. The resulting algorithm is applied to distributed averaging problem and shown to yield substantial performance improvements over the stateoftheart algorithms. / <p>QC 20150327</p>

47 
On Distributed Optimization in Networked SystemsJohansson, Björn January 2008 (has links)
Numerous control and decision problems in networked systems can be posed as optimization problems. Examples include the framework of network utility maximization for resource allocation in communication networks, multiagent coordination in robotics, and collaborative estimation in wireless sensor networks (WSNs). In contrast to classical distributed optimization, which focuses on improving computational efficiency and scalability, these new applications require simple mechanisms that can operate under limited communication. In this thesis, we develop several novel mechanisms for distributed optimization under communication constraints, and apply these to several challenging engineering problems. In particular, we devise three tailored optimization algorithms relying only on nearest neighbor, also known as peertopeer, communication. Two of the algorithms are designed to minimize a nonsmooth convex additive objective function, in which each term corresponds to a node in a network. The first method is an extension of the randomized incremental subgradient method where the update order is given by a random walk on the underlying communication graph, resulting in a randomized peertopeer algorithm with guaranteed convergence properties. The second method combines local subgradient iterations with consensus steps to average local update directions. The resulting optimization method can be executed in a peertopeer fashion and analyzed using epsilonsubgradient methods. The third algorithm is a centerfree algorithm, which solves a nonsmooth resource allocation problem with a separable additive convex objective function subject to a constant sum constraint. Then we consider crosslayer optimization of communication networks, and demonstrate how optimization techniques allow us to engineer protocols that mimic the operation of distributed optimization algorithms to obtain an optimal resource allocation. We describe a novel use of decomposition methods for crosslayer optimization, and present a flowchart that can be used to categorize and visualize a large part of the current literature on this topic. In addition, we devise protocols that optimize the resource allocation in frequencydivision multiple access (FDMA) networks and spatial reuse timedivision multiple access (TDMA) networks, respectively. Next we investigate some variants of the consensus problem for multirobot coordination, for which it is usually standard to assume that agents should meet at the barycenter of the initial states. We propose a negotiation strategy to find an optimal meeting point in the sense that the agents' trajectories to the meeting point minimize a quadratic cost criterion. Furthermore, we also demonstrate how an augmented state vector can be used to boost the convergence rate of the standard linear distributed averaging iterations, and we present necessary and sufficient convergence conditions for a general version of these iterations. Finally, we devise a generic optimization software component for WSNs. To this end, we implement some of the most promising optimization algorithms developed by ourselves and others in our WSN testbed, and present experimental results, which show that the proposed algorithms work surprisingly well. / QC 20100813

48 
Spectrum Sharing in Cognitive Radio Systems Under Outage Probablility ConstraintCai, Pei Li 2009 December 1900 (has links)
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 underutilized. 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 (SUTx), the channel state information
(CSI) of the SU link is assumed to be perfectly known; while the interference
channel from the SUTx to the PU receiver (PURx) is not perfectly known due to
less cooperation between the SU and the PU. As such, the SUTx 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 nonconvex optimization
problem with a nonexplicit 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 particularlyconstructed
convex problem.

49 
Optimization in multirelay wireless networksNguyen, Huu Ngoc Duy 08 June 2009
The concept of cooperation in communications has drawn a lot of research attention in recent years due to its potential to improve the efficiency of wireless networks. This new form of communications allows some users to act as relays
and assist the transmission of other users' information signals. The aim of this thesis is to apply optimization techniques in the design of multirelay wireless networks employing cooperative communications. In general, the thesis is organized into two parts: ``Distributed spacetime coding' (DSTC) and ``Distributed beamforming', which cover two main approaches in cooperative communications over multirelay networks.
<br><br>
In Part I of the thesis, various aspects of distributed implementation of spacetime coding in a wireless relay network are treated. First, the thesis proposes a new fullydiverse distributed code which allows noncoherent reception at the destination. Second, the problem of coordinating the power allocation (PA) between source and relays to achieve the optimal performance of DSTC is studied and a novel PA scheme is developed. It is shown that the proposed PA scheme can obtain the maximum diversity order of DSTC and significantly outperform other suboptimal PA schemes. Third, the thesis presents the optimal PA scheme to minimize the meansquare error (MSE) in channel estimation during training phase of DSTC. The effect of imperfect channel estimation to the performance of DSTC is also thoroughly studied.
<br><br>
In Part II of the thesis, optimal distributed beamforming designs are developed for a wireless multiuser multirelay network. Two design criteria for the optimal distributed beamforming at the relays are considered: (i) minimizing the total relay power subject to a guaranteed Quality of Service (QoS) measured in terms of signaltonoiseratio (SNR) at the destinations, and (ii) jointly maximizing the SNR margin at the destinations subject to power constraints at the relays. Based on convex optimization techniques,
it is shown that these problems can be formulated and solved via secondorder conic programming (SOCP). In addition, this part also proposes simple and fast iterative algorithms to directly solve these optimization problems.

50 
New Convex Relaxations for the Maximum Cut and VLSI Layout ProblemsFerreira Fialho dos Anjos, Miguel Nuno January 2001 (has links)
It is well known that many of the optimization problems which arise in applications are <I>hard</I>, which usually means that they are NPhard. Hence much research has been devoted to finding <I>good</I> relaxations for these hard problems. Usually a <I>good</I> relaxation is one which can be solved (either exactly or within a prescribed numerical tolerance) in polynomialtime. Nesterov and Nemirovskii showed that by this criterion, many convex optimization problems are good relaxations. This thesis presents new convex relaxations for two such hard problems, namely the MaximumCut (MaxCut) problem and the VLSI (Very Large Scale Integration of electronic circuits) layout problem. We derive and study the properties of two new strengthened semidefinite programming relaxations for the MaxCut problem. Our theoretical results hold for every instance of MaxCut; in particular, we make no assumptions about the edge weights. The first relaxation provides a strengthening of the wellknown GoemansWilliamson relaxation, and the second relaxation is a further tightening of the first. We prove that the tighter relaxation automatically enforces the wellknown triangle inequalities, and in fact is stronger than the simple addition of these inequalities to the GoemansWilliamson relaxation. We further prove that the tighter relaxation fully characterizes some low dimensional faces of the cut polytope via the rank of its feasible matrices. We also address some practical issues arising in the solution of these relaxations and present numerical results showing the remarkably good bounds computed by the tighter relaxation. For the VLSI layout problem, we derive a new relaxation by extending the <I>target distance</I> concept recently introduced by Etawil and Vannelli. The resulting AR (AttractorRepeller) model improves on the NLT (Nonlinear optimization Layout Technique) method of van Camp et al. by efficiently finding a good initial point for the NLT solver. Because the AR model is not a convex optimization problem, we isolate the source of the nonconvexity and thereby derive a convex version of the model. This derivation leads to the definition of certain generalized target distances with an interesting practical interpretation. Finally, we present numerical results that demonstrate the potential of the AR model.

Page generated in 0.1613 seconds