Spelling suggestions: "subject:"semidefinite programming"" "subject:"semidefinite erogramming""
41 
A Robust Optimization Approach to the Selfscheduling Problem Using Semidefinite ProgrammingLandry, Jason Conrad January 2009 (has links)
In deregulated electricity markets, generating companies submit energy bids which are derived from a selfschedule. In this thesis, we propose an improved semidefinite programmingbased model for the selfscheduling problem. The model provides the profitmaximizing generation quantities of a single generator over a multiperiod horizon and accounts for uncertainty in prices using robust optimization. Within this robust framework, the price information is represented analytically as an ellipsoid. The riskadversity of the decision maker is taken into account by a scaling parameter. Hence, the focus of the model is directed toward the tradeoff between profit and risk. The bounds obtained by the proposed approach are shown to be significantly better than those obtained by a meanvariance approach from the literature. We then apply the proposed model within a branchandbound algorithm to improve the quality of the solutions. The resulting solutions are also compared with the meanvariance approach, which is formulated as a mixedinteger quadratic programming problem. The results indicate that the proposed approach produces solutions which are closer to integrality and have lower relative error than the meanvariance approach.

42 
New Conic Optimization Techniques for Solving Binary Polynomial Programming ProblemsGhaddar, Bissan January 2011 (has links)
Polynomial programming, a class of nonlinear programming where the objective and the constraints are multivariate polynomials, has attracted the attention of many researchers in the past decade. Polynomial programming is a powerful modeling tool that captures various optimization models. Due to the wide range of applications, a research topic of high interest is the development of computationally efficient algorithms for solving polynomial programs. Even though some solution methodologies are already available and have been studied in the literature, these approaches are often either problem specific or are inapplicable for largescale polynomial programs. Most of the available methods are based on using hierarchies of convex relaxations to solve polynomial programs; these schemes grow exponentially in size becoming rapidly computationally expensive. The present work proposes methods and implementations that are capable of solving polynomial programs of large sizes. First we propose a general framework to construct conic relaxations for binary polynomial programs, this framework allows us to rederive previous relaxation schemes and provide new ones. In particular, three new relaxations for binary quadratic polynomial programs are presented. The first two relaxations, based on secondorder cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of nonconvex binary quadratic polynomial problems. The third relaxation is based purely on secondorder cone programming, it outperforms the semidefinitebased relaxations that are proposed in the literature in terms of computational efficiency while being comparable in terms of bounds. To strengthen the relaxations further, a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs is presented. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. The scheme can be used on any initial relaxation of the polynomial program whether it is secondorder cone based or semidefinite based relaxations. The proposed scheme is specialized for binary polynomial programs and is in principle scalable to large general combinatorial optimization problems. In the case of binary polynomial programs, the proposed scheme converges to the global optimal solution under mild assumptions on the initial approximation of the binary polynomial program. Finally, for binary polynomial programs the proposed relaxations are integrated with the dynamic scheme in a branchandbound algorithm to find global optimal solutions.

43 
Approximate LMMSE detector for uplink in multireceiver MIMO systemLo, KunFeng 15 August 2011 (has links)
In this thesis, we consider receiver design problems in a multicell MIMO system using the coordinated multipoint transmission/reception technique. The linear minimum
mean square error (LMMSE) receiver, which involves the inverse operation, is adopted. By the CayleyHamilton theorem, the matrix inverse can be represented by weighted sum of power of matrices. Given an order of the matrix power, we calculate the best weight in sense of the minimum mean square error. Both the uplink and the downlink scenarios are considered. Also, given a target signal to interference and noise ratio (SINR), we consider the best weight design problem in the downlink scenario. This problem can be formulated as the secondorder cone programming (SOCP) and semidefinite relaxation (SDR) programming. By computer simulations, we show that the SDR and SOCP are equivalent.

44 
The Convexity of Quadratic Maps and the Controllability of Coupled SystemsSheriff, Jamin Lebbe 16 September 2013 (has links)
A quadratic form on \(\mathbb{R}^n\) is a map of the form \(x \mapsto x^T M x\), where M is a symmetric \(n \times n\) matrix. A quadratic map from \(\mathbb{R}^n\) to \(\mathbb{R}^m\) is a map, all m of whose components are quadratic forms. One of the two central questions in this thesis is this: when is the image of a quadratic map \(Q: \mathbb{R}^n \rightarrow \mathbb{R}^m\) a convex subset of \(\mathbb{R}^m\)? This question has intrinsic interest; despite being only a degree removed from linear maps, quadratic maps are not well understood. However, the convexity properties of quadratic maps have practical consequences as well: underlying every semidefinite program is a quadratic map, and the convexity of the image of that map determines the nature of the solutions to the semidefinite program. Quadratic maps that map into \(\mathbb{R}^2\) and \(\mathbb{R}^3\) have been studied before (in (Dines, 1940) and (Calabi, 1964) respectively). The Roundness Theorem, the first of the two principal results in this thesis, is a sufficient and (almost) necessary condition for a quadratic map \(Q: \mathbb{R}^n \rightarrow \mathbb{R}^m\) to have a convex image when \(m \geq 4\), \(n \geq m\) and \(n \not= m + 1\). Concomitant with the Roundness Theorem is an important lemma: when \(n < m\), quadratic maps from \(\mathbb{R}^n\) to \(\mathbb{R}^m\)seldom have convex images. This second result in this thesis is a controllability condition for bilinear systems defined on direct products of the form \(\mathcal{G} \times\mathcal{G}\), where \(\mathcal{G}\) is a simple Lie group. The condition is this: a bilinear system defined on \(\mathcal{G} \times\mathcal{G}\) is not
controllable if and only if the Lie algebra generated by the system’s vector fields is the graph of some automorphism of \(\mathcal{g}\), the Lie algebra of \(\mathcal{G}\). / Engineering and Applied Sciences

45 
Computing optimal designs for regression models via convex programmingZhou, Wenjie 25 August 2015 (has links)
Optimal design problems aim at selecting design points optimally with respect to certain
statistical criteria. The research of this thesis focuses on optimal design problems with
respect to A, D and Eoptimal criteria, which minimize the trace, determinant and largest
eigenvalue of the information matrix, respectively.
Semide nite programming (SDP) is concerned with optimizing a linear objective function
subject to a linear matrix being positive semide nite. Two powerful MATLAB addons,
SeDuMi and CVX, have been developed to solve SDP problems e ciently. In this paper,
we show in detail how to formulate A and Eoptimal design problems as SDP problems
and solve them by SeDuMi and CVX. This technique can be used to construct approximate
Aoptimal and Eoptimal designs for all linear and nonlinear models with discrete design
spaces. The results can also provide guidance to nd optimal designs on continuous design
spaces. For one variable polynomial regression models, we solve the A and E optimal
designs on the continuous design space by using a twostage procedure. In the rst stage
we nd the optimal moments by casting it as an SDP problem and in the second stage we
extract the optimal designs from the optimal moments obtained from the rst stage.
Unlike E and Aoptimal design problems, the objective function of Doptimal design
problem is nonlinear. So Doptimal design problems cannot be reformulated as an SDP.
However, it can be cast as a convex problem and solved by an interior point method. In
this thesis we give details on how to use the interior point method to solve Doptimal design
problems.
Finally several numerical examples for A, D, and Eoptimal designs along with the
MATLAB codes are presented. / Graduate

46 
Pusiau apibrėžto programavimo optimizavimo paketo SeDuMi analizė / Analysis of the Semidefinite programming SeDuMi optimization packageSvorobovič, Andrej 16 August 2007 (has links)
Šiame darbe yra aprašomas optimizavimo paketas SeDuMi Interface ir jam priklausantis skaičiavimo paketas SeDuMi 1.05. Išvardintos paketo savybės, kurios išskiria jį iš kitų optimizavimo paketų. Aprašytos paketo funkcijų reikšmės. Supažindinama su optimizavimo paketų įvairove. Palyginamas pusiau apibrėžtas programavimas su tiesiniu programavimu, kadangi pakete SeDuMi interface realizuoti pusiau apibrėžto programavimo algoritmai. Taip pat lyginami programų skaičiavimų laikai: programų naudojančių SeDuMi paketo funkcijas ir programų su MATLAB funkcijomis. Palyginimui realizuoti, naudojamas klasikinis optimizavimo uždavinys –mažiausių reikšmių elipsoido uždavinys. / The optimization software SeDuMi Interface and it‘s calculation packet SeDuMi 1.05 is described in this work. Distinctive software features are listed. and values of packet’s functions are described. Variety of optimization packets is presented. Semidefinite programming is compared with linear programming, since semidefinite programming algorithms are implemented in the SeDuMi interface. Time of execution of the programs has been also compared: programs using SeDuMi software functions has been compared with programs using MATLAB functions. For the comparison classical optimization problem is used – the minimum volume ellipsoid problem.

47 
Robust Beamforming for TwoWay Relay SystemsAziz, Ahsan 16 December 2013 (has links)
In wireless communication systems, relays are widely used to extend coverage. Over the past years, relays have evolved from simple repeaters to more sophisticated units that perform signal processing to improve signal to interference plus noise ratio (SINR) or throughput (or both) at the destination receiver. There are various types of relays such as amplify and forward (AF), decode and forward (DF), and compress and forward (CF) (or estimate and forward (EF)) relays. In addition, recently there has been a growing interest in twoway relays (TWR). By utilizing the concept of analog network coding (ANC), TWRs can improve the throughput of a wireless sys tem by reducing the number of time slots needed to complete a bidirectional message exchange between two destination nodes. It’s well known that the performance of a TWR system greatly depends on its ability to apply signal processing techniques to effectively mitigate the selfinterference and noise accumulation, thereby improving the SINR. We study a TWR system that is equipped with multiple antennas at the relay node and a single antenna at the two destination nodes. Different from traditional work on TWR, we focus on the case with imperfect knowledge of channel state information (CSI).
For such a TWR, we formulate a robust optimization problem that takes into ac count normbounded estimation errors in CSI and designs an optimal beamforming matrix. Realizing the fact that this problem is extremely hard to solve globally, we derive two different methods to obtain either optimal or efficient suboptimal beam forming matrix solutions. The first method involves solving the robust optimization problem using the Sprocedure and semidefinite programming (SDP) with rankone relaxation. This method provides an optimal solution when the rankone relaxation condition for the SDP is satisfied. In cases where the rankone condition cannot be satisfied, it’s necessary to resort to suboptimal techniques. The second approach presented here reformulates the robust nonconvex quadratically constrained quadratic programming (QCQP) into a robust linear programming (LP) problem by using firstorder perturbation of the optimal nonrobust beamforming solution (which assumes no channel estimation error). Finally, we view the TWR robust beamforming problem from a practical standpoint and develop a set of iterative algorithms based on Newton’s method or the steepest descent method that are practical for hardware implementation.

48 
The Approximability of Learning and Constraint Satisfaction ProblemsWu, Yi 07 October 2010 (has links)
An αapproximation algorithm is an algorithm guaranteed to output a solutionthat is within an α ratio of the optimal solution. We are interested in thefollowing question: Given an NPhard optimization problem, what is the bestapproximation guarantee that any polynomial time algorithm could achieve?
We mostly focus on studying the approximability of two classes of NPhardproblems: Constraint Satisfaction Problems (CSPs) and Computational Learning Problems.
For CSPs, we mainly study the approximability of MAX CUT, MAX 3CSP,MAX 2LINR, VERTEXPRICING, as well as serval variants of the UNIQUEGAMES.• The problem of MAX CUT is to find a partition of a graph so as to maximizethe number of edges between the two partitions. Assuming theUnique Games Conjecture, we give a complete characterization of the approximationcurve of the MAX CUT problem: for every optimum value ofthe instance, we show that certain SDP algorithm with RPR2 roundingalways achieve the optimal approximation curve.• The input to a 3CSP is a set of Boolean constraints such that each constraintcontains at most 3 Boolean variables. The goal is to find an assignmentto these variables to maximize the number of satisfied constraints.We are interested in the case when a 3CSP is satisfiable, i.e.,there does exist an assignment that satisfies every constraint. Assumingthe dto1 conjecture (a variant of the Unique Games Conjecture), weprove that it is NPhard to give a better than 5/8approximation for theproblem. Such a result matches a SDP algorithm by Zwick which givesa 5/8approximation problem for satisfiable 3CSP. In addition, our resultalso conditionally resolves a fundamental open problem in PCP theory onthe optimal soundness for a 3query nonadaptive PCP system for NP withperfect completeness.• The problem of MAX 2LINZ involves a linear systems of integer equations;these equations are so simple such that each equation contains atmost 2 variables. The goal is to find an assignment to the variables so asto maximize the total number of satisfied equations. It is a natural generalizationof the Unique Games Conjecture which address the hardness ofthe same equation systems over finite fields. We show that assuming theUnique Games Conjecture, for a MAX 2LINZ instance, even that thereexists a solution that satisfies 1−ε of the equations, it is NPhard to findone that satisfies ² of the equations for any ε > 0.

49 
Preprocessing and Reduction for Semidefinite Programming via Facial Reduction: Theory and PracticeCheung, YuenLam 05 November 2013 (has links)
Semidefinite programming is a powerful modeling tool for a wide range of optimization and feasibility problems. Its prevalent use in practice relies on the fact that a (nearly) optimal solution of a semidefinite program can be obtained efficiently in both theory and practice, provided that the semidefinite program and its dual satisfy the Slater condition.
This thesis focuses on the situation where the Slater condition (i.e., the existence of positive definite feasible solutions) does not hold for a given semidefinite program; the failure of the Slater condition often occurs in structured semidefinite programs derived from various applications. In this thesis, we study the use of the facial reduction technique, originally proposed as a theoretical procedure by Borwein and Wolkowicz, as a preprocessing technique for semidefinite programs. Facial reduction can be used either in an algorithmic or a theoretical sense, depending on whether the structure of the semidefinite program is known a priori.
The main contribution of this thesis is threefold. First, we study the numerical issues in the implementation of the facial reduction as an algorithm on semidefinite programs, and argue that each step of the facial reduction algorithm is backward stable. Second, we illustrate the theoretical importance of the facial reduction procedure in the topic of sensitivity analysis for semidefinite programs. Finally, we illustrate the use of facial reduction technique on several classes of structured semidefinite programs, in particular the side chain positioning problem in protein folding.

50 
New Conic Optimization Techniques for Solving Binary Polynomial Programming ProblemsGhaddar, Bissan January 2011 (has links)
Polynomial programming, a class of nonlinear programming where the objective and the constraints are multivariate polynomials, has attracted the attention of many researchers in the past decade. Polynomial programming is a powerful modeling tool that captures various optimization models. Due to the wide range of applications, a research topic of high interest is the development of computationally efficient algorithms for solving polynomial programs. Even though some solution methodologies are already available and have been studied in the literature, these approaches are often either problem specific or are inapplicable for largescale polynomial programs. Most of the available methods are based on using hierarchies of convex relaxations to solve polynomial programs; these schemes grow exponentially in size becoming rapidly computationally expensive. The present work proposes methods and implementations that are capable of solving polynomial programs of large sizes. First we propose a general framework to construct conic relaxations for binary polynomial programs, this framework allows us to rederive previous relaxation schemes and provide new ones. In particular, three new relaxations for binary quadratic polynomial programs are presented. The first two relaxations, based on secondorder cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of nonconvex binary quadratic polynomial problems. The third relaxation is based purely on secondorder cone programming, it outperforms the semidefinitebased relaxations that are proposed in the literature in terms of computational efficiency while being comparable in terms of bounds. To strengthen the relaxations further, a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs is presented. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. The scheme can be used on any initial relaxation of the polynomial program whether it is secondorder cone based or semidefinite based relaxations. The proposed scheme is specialized for binary polynomial programs and is in principle scalable to large general combinatorial optimization problems. In the case of binary polynomial programs, the proposed scheme converges to the global optimal solution under mild assumptions on the initial approximation of the binary polynomial program. Finally, for binary polynomial programs the proposed relaxations are integrated with the dynamic scheme in a branchandbound algorithm to find global optimal solutions.

Page generated in 0.1795 seconds