Spelling suggestions: "subject:"semidefinite erogramming"" "subject:"semidefinite grogramming""
21 
Optimization problems of electricity market under modern power gridLei, Ming 22 February 2016 (has links)
Nowadays, electricity markets are becoming more deregulated, especially development of smart grid and introduction of renewable energy promote regulations of energy markets. On the other hand, the uncertainties of new energy sources and market participants’ bidding bring more challenges to power system operation and transmission system planning. These problems motivate us to study spot price (also called locational marginal pricing) of electricity markets, the strategic bidding of wind power producer as an independent power producer into power market, transmission expansion planning considering wind power investment, and analysis of the maximum loadability of a power grid.
The work on probabilistic spot pricing for a utility grid includes renewable wind power
generation in a deregulated environment, taking into account both the uncertainty of load
forecasting and the randomness of wind speed. Based on the forecasted normaldistributed load and Weibulldistributed wind speed, probabilistic optimal power flow is formulated by including spinning reserve cost associated with wind power plants and emission cost in addition to conventional thermal power plant cost model. Simulations show that the integration of wind power can effectively decrease spot price, also increase the risk of overvoltage.
Based on the concept of loacational marginal pricing which is determined by a marketclearing algorithm, further research is conducted on optimal offering strategies for wind power producers participating in a dayahead market employing a stochastic marketclearing algoivrithm. The proposed procedure to drive strategic offers relies on a stochastic bilevel model: the upper level problem represents the profit maximization of the strategic wind power producer, while the lower level one represents the marketing clearing and the corresponding price formulation aiming to cooptimize both energy and reserve.
Thirdly, to improve wind power integration, we propose a bilevel problem incorporating
twostage stochastic programming for transmission expansion planning to accommodate
largescale wind power investments in electricity markets. The model integrates cooptimizations of energy and reserve to deal with uncertainties of wind power production. In the upper level problem, the objective of independent system operator (ISO) modelling transmission investments under uncertain environments is to minimize the transmission and wind power investment cost, and the expected load shedding cost. The lower level problem is composed of a two stage stochastic programming problem for energy schedule and reserve dispatch simultaneously. Case studies are carried out for illustrating the effectiveness of the proposed model.
The above marketclearing or power system operation is based on direct current optimal
power flow (DCOPF) model which is a linear problem without reactive power constraints.
Power system maximum loadability is a crucial index to determine voltage stability. The
fourth work in this thesis proposes a Lagrange semidefinite programming (SDP) method
to solve the nonlinear and nonconvex optimization alternating current (AC) problem of
the maximum loadability of security constrained power system. Simulation results from
the IEEE threebus system and IEEE 24bus Reliability Test System (RTS) show that the
proposed method is able to obtain the global optimal solution for the maximum loadability
problem.
Lastly, we summarize the conclusions from studies on the above mentioned optimization
problems of electric power market under modern grid, as well as the influence of wind power integration on power system reliability, and transmission expansion planning, as well as the operations of electricity markets. Meanwhile, we also present some open questions on the related research, such as nonconvex constraints in the lowerlevel problem of a bilevel problem, and integrating N1 security criterion of transmission planning. / Graduate / lei.ming296@gmail.com

22 
Limitantes de programação semidefinida para o número de contato / Semidefinite programming bounds for the kissing numberMachado, Fabrício Caluza 21 February 2017 (has links)
O número de contato do Rn (em inglês, kissing number) é o maior número de esferas de raio unitário e interiores doisadois disjuntos que podem tocar simultaneamente uma esfera de raio unitário central. Nesta dissertação estudamos métodos que limitam o tamanho de tais configurações através de técnicas de otimização, como dualidade e programação semidefinida. O principal resultado obtido foi o cálculo de melhores limitantes para o número de contato nas dimensões 9 a 23; o que foi possível graças à exploração de simetrias dos polinômios presentes no limitante proposto por Bachoc e Vallentin (2008), levando à consideração de programas semidefinidos menores. Por fim, o limitante estudado é estendido para uma classe mais geral de problemas. / The kissing number of Rn is the maximum number of pairwisenonoverlapping unit spheres that can simultaneously touch a central unit sphere. In this thesis we study methods to bound from above the size of such configurations using optimization techniques, like duality and semidefinite programming. The main result achieved is the computation of better bounds for the kissing number in dimensions 9 to 23; a result possible due to the exploitation of symmetries in the polynomials present in the bound proposed by Bachoc and Vallentin (2008), leading to the consideration of smaller semidefinite programs. Finally, the studied bound is extended to a bigger class of problems.

23 
Distributed and LargeScale OptimizationAli Younis Kalbat, Abdulrahman Younis January 2016 (has links)
This dissertation is motivated by the pressing need for solving realworld largescale optimization problems with the main objective of developing scalable algorithms that are capable of solving such problems efficiently. Largescale optimization problems naturally appear in complex systems such as power networks and distributed control systems, which are the main systems of interest in this work. This dissertation aims to address four problems with regards to the theory and application of largescale optimization problems, which are explained below:
Chapter 2: In this chapter, a fast and parallelizable algorithm is developed for an arbitrary decomposable semidefinite program (SDP). Based on the alternating direction method of multipliers, we design a numerical algorithm that has a guaranteed convergence under very mild assumptions. We show that each iteration of this algorithm has a simple closedform solution, consisting of matrix multiplications and eigenvalue decompositions performed by individual agents as well as information exchanges between neighboring agents. The cheap iterations of the proposed algorithm enable solving a wide spectrum of realworld largescale conic optimization problems that could be reformulated as SDP.
Chapter 3: Motivated by the application of sparse SDPs to power networks, the objective of this chapter is to design a fast and parallelizable algorithm for solving the SDP relaxation of a largescale optimal power flow (OPF) problem. OPF is fundamental problem used for the operation and planning of power networks, which is nonconvex and NPhard in the worst case. The proposed algorithm would enable a realtime power network management and improve the system's reliability. In particular, this algorithm helps with the realization of Smart Grid by allowing to make optimal decisions very fast in response to the stochastic nature of renewable energy. The proposed algorithm is evaluated on IEEE benchmark systems.
Chapter 4: The design of an optimal distributed controller using an efficient computational method is one of the most fundamental problems in the area of control systems, which remains as an open problem due to its NPhardness in the worst case. In this chapter, we first study the infinitehorizon optimal distributed control (ODC) problem (for deterministic systems) and then generalize the results to a stochastic ODC problem (for stochastic systems). Our approach rests on formulating each of these problems as a rankconstrained optimization from which an SDP relaxation can be derived. We show that both problems admit sparse SDP relaxations with solutions of rank at most~3. Since a rank1 SDP matrix can be mapped back into a globallyoptimal controller, the rank3 solution may be deployed to retrieve a nearglobal controller. We also propose computationally cheap SDP relaxation for each problem and then develop effective heuristic methods to recover a nearoptimal controller from the lowrank SDP solution. The design of several nearoptimal structured controllers with global optimality degrees above 99\% will be demonstrated.
Chapter 5: The frequency control problem in power networks aims to control the global frequency of the system within a tight range by adjusting the output of generators in response to the uncertain and stochastic demand. The intermittent nature of distributed power generation in smart grid makes the traditional decentralized frequency controllers less efficient and demands distributed controllers that are able to deal with the uncertainty in the system introduced by nondispatchable supplies (such as renewable energy), fluctuating loads, and measurement noise. Motivated by this need, we study the frequency control problem using the results developed in Chapter 4. In particular, we formulate the problem and then conduct a case study on the IEEE 39Bus New England system. The objective is to design a nearglobal optimal distributed frequency controller for the New England test system by optimally adjusting the mechanical power input to each generator based on the realtime measurement received from neighboring generators through a userdefined communication topology.

24 
Optimization under uncertainty: conic programming representations, relaxations, and approximationsXu, Guanglin 01 August 2017 (has links)
In practice, the presence of uncertain parameters in optimization problems introduces new challenges in modeling and solvability to operations research. There are three main paradigms proposed for optimization problems under uncertainty. These include stochastic programming, robust optimization, and sensitivity analysis. In this thesis, we examine, improve, and combine the latter two paradigms in several relevant models and applications. In the second chapter, we study a twostage adjustable robust linear optimization problem in which the righthand sides are uncertain and belong to a compact, convex, and tractable uncertainty set. Under standard and simple assumptions, we reformulate the twostage problem as a copositive optimization program, which in turns leads to a class of tractable semidefinitebased approximations that are at least as strong as the affine policy, which is a well studied tractable approximation in the literature. We examine our approach over several examples from the literature and the results demonstrate that our tractable approximations significantly improve the affine policy. In particular, our approach recovers the optimal values of a class of instances of increasing size for which the affine policy admits an arbitrary large gap. In the third chapter, we leverage the concept of robust optimization to conduct sensitivity analysis of the optimal value of linear programming (LP). In particular, we propose a framework for sensitivity analysis of LP problems, allowing for simultaneous perturbations in the objective coefficients and righthand sides, where the perturbations are modeled in a compact, convex, and tractable uncertainty set. This framework unifies and extends multiple approaches for LP sensitivity analysis in the literature and has close ties to worstcase LP and twostage adjustable linear programming. We define the bestcase and worstcase LP optimal values over the uncertainty set. As the concept aligns well with the general spirit of robust optimization, we denote our approach as robust sensitivity analysis. While the bestcase and worstcase optimal values are difficult to compute in general, we prove that they equal the optimal values of two separate, but related, copositive programs. We then develop tight, tractable conic relaxations to provide bounds on the bestcase and worst case optimal values, respectively. We also develop techniques to assess the quality of the bounds, and we validate our approach computationally on several examples from—and inspired by—the literature. We find that the bounds are very strong in practice and, in particular, are at least as strong as known results for specific cases from the literature. In the fourth chapter of this thesis, we study the expected optimal value of a mixed 01 programming problem with uncertain objective coefficients following a joint distribution. We assume that the true distribution is not known exactly, but a set of independent samples can be observed. Using the Wasserstein metric, we construct an ambiguity set centered at the empirical distribution from the observed samples and containing all distributions that could have generated the observed samples with a high confidence. The problem of interest is to investigate the bound on the expected optimal value over the Wasserstein ambiguity set. Under standard assumptions, we reformulate the problem into a copositive programming problem, which naturally leads to a tractable semidefinitebased approximation. We compare our approach with a momentbased approach from the literature for two applications. The numerical results illustrate the effectiveness of our approach.
Finally, we conclude the thesis with remarks on some interesting open questions in the field of optimization under uncertainty. In particular, we point out that some interesting topics that can be potentially studied by copositive programming techniques.

25 
Aproximação da norma de corte via desigualdade de Grothendieck / Approximation of the cutnorm via Grothendieck\'s inequalityEndo, Eric Ossami 17 July 2014 (has links)
Neste trabalho, objetivamos apresentar o Teorema de Alon e Naor, o qual afirma que existe um algoritmo de aproximação para a norma de corte de uma matriz qualquer, sendo que a garantia de desempenho desse algoritmo é a inversa da constante de Grothendieck. Introduzimos a norma de corte de uma matriz e exibimos algumas de suas propriedades. Uma delas é que a norma de corte é equivalente a uma outra norma, que é valor ótimo de um programa inteiro quadrático que pode ser relaxado por um programa semidefinido. Além do Teorema de Alon e Naor, construímos mais dois algoritmos de aproximação para a norma de corte. Ambos possuem garantia de desempenho inferior que a do Teorema de Alon e Naor, porém as técnicas que foram utilizadas para obter tais algoritmos são interessantes. Enunciamos a Desigualdade e Grothendieck reformulada por Lindenstrauss e Pelcýnski e mostramos uma cota superior para a constante de Grothendieck que se baseia no Argumento de Krivine. Finalmente, apresentamos três aplicações do Teorema de Alon e Naor: em corte máximo de um grafo; na versão algorítmica do Lema da Regularidade de Szemerédi; e no Teorema de Frieze e Kannan. / In this work, our objective is to present Alon and Naor\'s Theorem, which states that there exists an approximation algorithm for cutnorm of any matrix and that the approximations guarantee of the algorithm is the inverse of the Grothendieck\'s constant. We introduce the cutnorm of a matrix and we show some of its properties. One is that the cutnorm is equivalent of some other norm which is the optimum value of quadratic integer program which can be relaxed for a semidefinite program. Beyond Alon and Naor\'s Theorem, we construct two more approximation algorithm for cutnorm. The approximation guarantee of both is inferior to the Alon and Naor\'s Theorem, but the techniques for obtaining such algorithms is interesting. We show Grothendieck\'s Inequality reformulated by Lindenstrauss e Pelcýnski and we show an upper bound for the Grothendieck\'s constant which is based on Krivine\'s Argument. Furthermore, we show three applications of Alon and Naor\'s Theorem: Maximum cut of a graph, an algorithmic version of Szemerédi Regularity Lemma, and Frieze and Kannan\'s Theorem.

26 
Global Optimization with PolynomialsHan, Deren 01 1900 (has links)
The class of POP (Polynomial Optimization Problems) covers a wide rang of optimization problems such as 0  1 integer linear and quadratic programs, nonconvex quadratic programs and bilinear matrix inequalities. In this paper, we review some methods on solving the unconstraint case: minimize a realvalued polynomial p(x) : Rn â R, as well the constraint case: minimize p(x) on a semialgebraic set K, i.e., a set defined by polynomial equalities and inequalities. We also summarize some questions that we are currently considering. / SingaporeMIT Alliance (SMA)

27 
Behavioral Measures and their Correlation with IPM Iteration Counts on SemiDefinite Programming ProblemsFreund, Robert M., Ordóñez, Fernando, Toh, Kim Chuan 04 March 2005 (has links)
We study four measures of problem instance behavior that might account for the observed differences in interiorpoint method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar) condition measure C(d) of the data instance, (iii) a measure of the nearabsence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the correlation between these measures and IPM iteration counts (solved using the software SDPT3) when the measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.896), and is a very good predictor of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The nearabsence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations.

28 
Robust Beamforming for OFDM Modulated TwoWay MIMO Relay NetworkZhou, Jianwei 2012 May 1900 (has links)
This thesis studies a twoway relay network (TWRN), which consists of two single antenna source nodes and a multiantenna relay node. The source nodes exchange information via the assistance of the relay node in the middle. The relay scheme in this TWRN is amplifyandforward (AF) based analog network coding (ANC). A robust beamforming matrix optimization algorithm is presented here with the objective to minimize the transmit power at the relay node under given signal to interference and noise ratio (SINR) requirements of source nodes. This problem is first formulated as a nonconvex optimization problem, and it is next relaxed to a semidefinite programming (SDP) problem by utilizing the Sprocedure and rankone relaxation. This robust beamforming optimization algorithm is further validated in a MATLABbased orthogonal frequencydivision multiplexing (OFDM) MIMO twoway relay simulation system. To better investigate the performance of this beamforming algorithm in practical systems, synchronization issues such as standard timing offset (STO) and carrier frequency offset (CFO) are considered in simulation. The transmission channel is modeled as a frequency selective fading channel, and the source nodes utilize training symbols to perform minimum meansquare error (MMSE) channel estimation. BER curves under perfect and imperfect synchronization are presented to show the performance of TWRN with ANC. It is shown that the outage probability of robust beamforming algorithm is tightly related to the SINR requirements at the source nodes, and the outage probability increases significantly when the SINR requirements are high.

29 
On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic ProgrammingDing, Yichuan 17 May 2007 (has links)
Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some important results on QCQP, like the SProcedure, and the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form trace(X^TQX + 2C^T X) + β, and trace(X^TQX + XPX^T + 2C^T X)+ β respectively, where X is an n by r real matrix. For each class of problems, we proposed different semidefinite relaxation formulations and compared their strength. The theoretical results obtained in this thesis have found interesting applications, e.g., solving the Quadratic Assignment Problem.

30 
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.0962 seconds