Bounds on linear PDEs via semidefinite optimization

Using recent progress on moment problems, and their connections with semidefinite optimization, we present in this paper a new methodology based on semidefinite optimization, to obtain a hierarchy of upper and lower bounds on linear functionals defined on solutions of linear partial differential equations. We apply the proposed method to examples of PDEs in one and two dimensions, with very encouraging results. We pay particular attention to a PDE with oblique derivative conditions, commonly arising in queueing theory. We also provide computational evidence that the semidefinite constraints are critically important in improving the quality of the bounds, that is, without them the bounds are weak. Research supported by the SMA-MI Talliance. Research partially supported by the SMA-MIT alliance and an NSF predoctoral fellowship.     

Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step

Interior-point methods for semidefinite optimization problems have been studied frequently, due to their polynomial complexity and practical implications. In this paper we propose a primal-dual infeasible interior-point algorithm that uses full Nesterov-Todd (NT) steps with a different feasibility step. We obtain the currently best known iteration bound for semidefinite optimization problems.     

LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semidefinite approaches for large sparse instances, we set up a common branch-and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities of the bisection cut polytope described in a recent study by the authors. While the problem specific cuts help to strengthen the linear relaxation significantly, the semidefinite bound profits much more from separating the cycle inequalities of the cut polytope on a slightly enlarged support. Extensive numerical experiments show that this semidefinite branch-and-cut approach without problem specific cuts is a superior choice to the classical simplex approach exploiting bisection specific inequalities on a clear majority of our large sparse test instances from VLSI design and numerical optimization.     

A note on semidefinite programming relaxations for polynomial optimization over a single sphere

We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates (BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.     

Solving polynomial least squares problems via semidefinite programming relaxations

A polynomial optimization problem whose objective function is represented as a sum of positive and even powers of polynomials, called a polynomial least squares problem, is considered. Methods to transform a polynomial least square problem to polynomial semidefinite programs to reduce degrees of the polynomials are discussed. Computational efficiency of solving the original polynomial least squares problem and the transformed polynomial semidefinite programs is compared. Numerical results on selected polynomial least square problems show better computational performance of a transformed polynomial semidefinite program, especially when degrees of the polynomials are larger.     

Successive Linearization Methods for Nonlinear Semidefinite Programs

We present a successive linearization method with a trust region-type globalization for the solution of nonlinear semidefinite programs. At each iteration, the method solves a quadratic semidefinite program, which can be converted to a linear semidefinite program with a second order cone constraint. A subproblem of this kind can be solved quite efficiently by using some recent software for semidefinite and second-order cone programs. The method is shown to be globally convergent under certain assumptions. Numerical results on some nonlinear semidefinite programs including optimization problems with bilinear matrix inequalities are reported to illustrate the behaviour of the proposed method.The research of the fourth author was supported in part by a Grant-in-Aid for Scientific Research from Japan Society for the Promotion of Science. The research of the second author was supported by the DFG (Deutsche Forschungsgemeinschaft).     

A class of semidefinite programs with rank-one solutions

We show that a class of semidefinite programs (SDP) admits a solution that is a positive semidefinite matrix of rank at most r, where r is the rank of the matrix involved in the objective function of the SDP. The optimization problems of this class are semidefinite packing problems, which are the SDP analogs to vector packing problems. Of particular interest is the case in which our result guarantees the existence of a solution of rank one: we show that the computation of this solution actually reduces to a Second Order Cone Program (SOCP). We point out an application in statistics, in the optimal design of experiments.     

On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0–1 quadratic problems leading to quasi-Newton methods

This article presents a family of semidefinite programming bounds, obtained by Lagrangian duality, for 0–1 quadratic optimization problems with linear or quadratic constraints. These bounds have useful computational properties: they have a good ratio of tightness to computing time, they can be optimized by a quasi-Newton method, and their final tightness level is controlled by a real parameter. These properties are illustrated on three standard combinatorial optimization problems: unconstrained 0–1 quadratic optimization, heaviest $k$ -subgraph, and graph bisection.     

Homogeneous Self-dual Algorithms for Stochastic Semidefinite Programming

Ariyawansa and Zhu have proposed a new class of optimization problems termed stochastic semidefinite programs to handle data uncertainty in applications leading to (deterministic) semidefinite programs. For stochastic semidefinite programs with finite event space, they have also derived a class of volumetric barrier decomposition algorithms, and proved polynomial complexity of certain members of the class. In this paper, we consider homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space. We show how the structure in such problems may be exploited so that the algorithms developed in this paper have complexity similar to those of the decomposition algorithms mentioned above.     

A new proof of the strong duality theorem for semidefinite programming

Semidefinite programs are convex optimization problems arising in a wide variety of applications and are the extension of linear programming. Most methods for linear programming have been generalized to semidefinite programs. Just as in linear programming, duality theorem plays a basic and an important role in theory as well as in algorithmics. Based on the discretization method and convergence property, this paper proposes a new proof of the strong duality theorem for semidefinite programming, which is different from other common proofs and is more simple.     

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation.     

Lower-Order Penalization Approach to Nonlinear Semidefinite Programming

In this paper, we reformulate a nonlinear semidefinite programming problem into an optimization problem with a matrix equality constraint. We apply a lower-order penalization approach to the reformulated problem. Necessary and sufficient conditions that guarantee the global (local) exactness of the lower-order penalty functions are derived. Convergence results of the optimal values and optimal solutions of the penalty problems to those of the original semidefinite program are established. Since the penalty functions may not be smooth or even locally Lipschitz, we invoke the Ekeland variational principle to derive necessary optimality conditions for the penalty problems. Under certain conditions, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original semidefinite program. Communicated by Y. Zhang This work was supported by a Postdoctoral Fellowship of Hong Kong Polytechnic University and by the Research Grants Council of Hong Kong.     

On Polynomial Optimization Over Non-compact Semi-algebraic Sets

The optimal value of a polynomial optimization over a compact semi-algebraic set can be approximated as closely as desired by solving a hierarchy of semidefinite programs and the convergence is finite generically under the mild assumption that a quadratic module generated by the constraints is Archimedean. We consider a class of polynomial optimization problems with non-compact semi-algebraic feasible sets, for which an associated quadratic module, that is generated in terms of both the objective function and the constraints, is Archimedean. For such problems, we show that the corresponding hierarchy converges and the convergence is finite generically. Moreover, we prove that the Archimedean condition (as well as a sufficient coercivity condition) can be checked numerically by solving a similar hierarchy of semidefinite programs. In other words, under reasonable assumptions, the now standard hierarchy of semidefinite programming relaxations extends to the non-compact case via a suitable modification.     

On approximating complex quadratic optimization problems via semidefinite programming relaxations

In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite. This research was supported in part by NSF grant DMS-0306611.     

无线通信系统设计中的两个优化问题和相关优化方法

无线通信系统设计中的许多问题可建模为优化问题.一方面,这些优化问题常常具有高度的非线性性,一般情况下难于求解;另一方面,它们又有自身的特殊结构,例如隐含的凸性、可分性等.利用优化的方法结合问题的特殊结构求解和处理无线通信系统设计问题是近年来学术界研究的热点.本文重点讨论无线通信系统设计中的两个优化问题和相关优化方法,包括多用户干扰信道最大最小准则下的联合传输/接收波束成形设计和多输入多输出(Multi-Input Multi-Output,MIMO)检测问题,主要介绍现代优化技术结合问题的特殊结构在求解和处理上述两个问题的最新进展.     

Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MaxCut, Max2Sat, and Max3Sat. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.     

Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.     

Convex optimization problems involving finite autocorrelation sequences

 We discuss convex optimization problems in which some of the variables are constrained to be finite autocorrelation sequences. Problems of this form arise in signal processing and communications, and we describe applications in filter design and system identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding power spectral density, which results in a set of linear inequalities. They can also be cast as linear matrix inequalities via the Kalman-Yakubovich-Popov lemma. The linear matrix inequality formulation is exact, and results in convex optimization problems that can be solved using interior-point methods for semidefinite programming. However, it has an important drawback: to represent an autocorrelation sequence of length $n$, it requires the introduction of a large number ($n(n+1)/2$) of auxiliary variables. This results in a high computational cost when general-purpose semidefinite programming solvers are used. We present a more efficient implementation based on duality and on interior-point methods for convex problems with generalized linear inequalities. Received: August 20, 2001 / Accepted: July 16, 2002 Published online: September 27, 2002 RID="★" ID="★" This material is based upon work supported by the National Science Foundation under Grant No. ECS-9733450.     

About the non-convex optimization problem induced by non-positive semidefinite kernel learning

During the last years, kernel based methods proved to be very successful for many real-world learning problems. One of the main reasons for this success is the efficiency on large data sets which is a result of the fact that kernel methods like support vector machines (SVM) are based on a convex optimization problem. Solving a new learning problem can now often be reduced to the choice of an appropriate kernel function and kernel parameters. However, it can be shown that even the most powerful kernel methods can still fail on quite simple data sets in cases where the inherent feature space induced by the used kernel function is not sufficient. In these cases, an explicit feature space transformation or detection of latent variables proved to be more successful. Since such an explicit feature construction is often not feasible for large data sets, the ultimate goal for efficient kernel learning would be the adaptive creation of new and appropriate kernel functions. It can, however, not be guaranteed that such a kernel function still leads to a convex optimization problem for Support Vector Machines. Therefore, we have to enhance the optimization core of the learning method itself before we can use it with arbitrary, i.e., non-positive semidefinite, kernel functions. This article motivates the usage of appropriate feature spaces and discusses the possible consequences leading to non-convex optimization problems. We will show that these new non-convex optimization SVM are at least as accurate as their quadratic programming counterparts on eight real-world benchmark data sets in terms of the generalization performance. They always outperform traditional approaches in terms of the original optimization problem. Additionally, the proposed algorithm is more generic than existing traditional solutions since it will also work for non-positive semidefinite or indefinite kernel functions.     

Approximate Optimality and Approximate Duality for Quasi Approximate Solutions in Robust Convex Semidefinite Programs

In this paper, we study quasi approximate solutions for a convex semidefinite programming problem in the face of data uncertainty. Using the robust optimization approach (worst-case approach), approximate optimality conditions and approximate duality theorems for quasi approximate solutions in robust convex semidefinite programming problems are explored under the robust characteristic cone constraint qualification. Moreover, some examples are given to illustrate the obtained results.