In deregulated electricity markets, generating companies submit energy bids which are derived from a self-schedule. In this thesis, we propose an improved semidefinite programming-based model for the self-scheduling problem. The model provides the profit-maximizing generation quantities of a single generator over a multi-period horizon and accounts for uncertainty in prices using robust optimization. Within this robust framework, the price information is represented analytically as an ellipsoid. The risk-adversity of the decision maker is taken into account by a scaling parameter. Hence, the focus of the model is directed toward the trade-off between profit and risk. The bounds obtained by the proposed approach are shown to be significantly better than those obtained by a mean-variance approach from the literature. We then apply the proposed model within a branch-and-bound algorithm to improve the quality of the solutions. The resulting solutions are also compared with the mean-variance approach, which is formulated as a mixed-integer quadratic programming problem. The results indicate that the proposed approach produces solutions which are closer to integrality and have lower relative error than the mean-variance approach.

Polynomial programming, a class of non-linear 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 large-scale 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 re-derive 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 second-order cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of non-convex binary quadratic polynomial problems. The third relaxation is based purely on second-order cone programming, it outperforms the semidefinite-based 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 second-order 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 branch-and-bound algorithm to find global optimal solutions.

In this thesis, we consider receiver design problems in a multi-cell MIMO system using the coordinated multi-point transmission/reception technique. The linear minimum mean square error (LMMSE) receiver, which involves the inverse operation, is adopted. By the Cayley-Hamilton 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 second-order cone programming (SOCP) and semidefinite relaxation (SDR) programming. By computer simulations, we show that the SDR and SOCP are equivalent.

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

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 E-optimal 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 add-ons, SeDuMi and CVX, have been developed to solve SDP problems e ciently. In this paper, we show in detail how to formulate A- and E-optimal design problems as SDP problems and solve them by SeDuMi and CVX. This technique can be used to construct approximate A-optimal and E-optimal designs for all linear and non-linear 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 two-stage 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 A-optimal design problems, the objective function of D-optimal design problem is nonlinear. So D-optimal 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 D-optimal design problems. Finally several numerical examples for A-, D-, and E-optimal designs along with the MATLAB codes are presented. / Graduate

Š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.

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 two-way 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 bi-directional 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 self-interference 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 norm-bounded 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 S-procedure and semidefinite programming (SDP) with rank-one relaxation. This method provides an optimal solution when the rank-one relaxation condition for the SDP is satisfied. In cases where the rank-one condition cannot be satisfied, it’s necessary to resort to sub-optimal techniques. The second approach presented here reformulates the robust non-convex quadratically constrained quadratic programming (QCQP) into a robust linear programming (LP) problem by using first-order perturbation of the optimal non-robust 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.

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 NP-hard 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 NP-hardproblems: Constraint Satisfaction Problems (CSPs) and Computational Learning Problems. For CSPs, we mainly study the approximability of MAX CUT, MAX 3-CSP,MAX 2-LINR, VERTEX-PRICING, 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 3-CSP 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 3-CSP is satisfiable, i.e.,there does exist an assignment that satisfies every constraint. Assumingthe d-to-1 conjecture (a variant of the Unique Games Conjecture), weprove that it is NP-hard to give a better than 5/8-approximation for theproblem. Such a result matches a SDP algorithm by Zwick which givesa 5/8-approximation problem for satisfiable 3-CSP. In addition, our resultalso conditionally resolves a fundamental open problem in PCP theory onthe optimal soundness for a 3-query nonadaptive PCP system for NP withperfect completeness.• The problem of MAX 2-LINZ 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 2-LINZ instance, even that thereexists a solution that satisfies 1−ε of the equations, it is NP-hard to findone that satisfies ² of the equations for any ε > 0.

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.

Polynomial programming, a class of non-linear 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 large-scale 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 re-derive 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 second-order cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of non-convex binary quadratic polynomial problems. The third relaxation is based purely on second-order cone programming, it outperforms the semidefinite-based 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 second-order 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 branch-and-bound algorithm to find global optimal solutions.