Search

Combinatorial optimization (CO) has a broad range of applications in various fields, including operations research, computer science, and artificial intelligence. However, many of these problems are classified as nondeterministic polynomial‐time (NP)‐complete or NP‐hard problems, which are known for their computational complexity and cannot be solved in polynomial time on traditional digital computers. To address this challenge, continuous‐time Ising machine solvers have been developed, utilizing different physical principles to map CO problems to ground state finding. However, most Ising machine prototypes operate at speeds comparable to digital hardware and rely on binarizing node states, resulting in increased system complexity and further limiting operating speed. To tackle these issues, a novel device‐algorithm co‐design method is proposed for fast sub‐optimal solution finding with low hardware complexity. On the device side, a piezoelectric lithium niobate (LiNbO3) microelectromechanical system (MEMS) oscillator network‐based Ising machine without second‐harmonic injection locking (SHIL) is devised to solve Max‐cut and graph coloring problems. The LiNbO3 oscillator operates at speeds greater than 9 GHz, making it one of the fastest oscillatory Ising machines. System‐wise, an innovative grouping method is used that achieves a performance guarantee of 0.878 for Max‐cut and 0.658 for graph coloring problems, which is comparable to Ising machines that utilize binarization. [ABSTRACT FROM AUTHOR]

Abstract Combinatorial optimization (CO) has a broad range of applications in various fields, including operations research, computer science, and artificial intelligence. However, many of these problems are classified as nondeterministic polynomial‐time (NP)‐complete or NP‐hard problems, which are known for their computational complexity and cannot be solved in polynomial time on traditional digital computers. To address this challenge, continuous‐time Ising machine solvers have been developed, utilizing different physical principles to map CO problems to ground state finding. However, most Ising machine prototypes operate at speeds comparable to digital hardware and rely on binarizing node states, resulting in increased system complexity and further limiting operating speed. To tackle these issues, a novel device‐algorithm co‐design method is proposed for fast sub‐optimal solution finding with low hardware complexity. On the device side, a piezoelectric lithium niobate (LiNbO3) microelectromechanical system (MEMS) oscillator network‐based Ising machine without second‐harmonic injection locking (SHIL) is devised to solve Max‐cut and graph coloring problems. The LiNbO3 oscillator operates at speeds greater than 9 GHz, making it one of the fastest oscillatory Ising machines. System‐wise, an innovative grouping method is used that achieves a performance guarantee of 0.878 for Max‐cut and 0.658 for graph coloring problems, which is comparable to Ising machines that utilize binarization.

In this paper, we examine a zero-duality gap with polynomial multipliers between a non-convex polynomial program and its associated generalized Lagrangian dual problem. To this end, we introduce a sum of squares certificate of non-negativity, abbreviated as (SC), that allows us to verify the non-negativity of a polynomial over a feasible set of a system of given polynomials. With the help of (SC), we show that the zero-duality gap with polynomial multipliers coincides with the convergent Lasserre hierarchy of semidefinite programming relaxations. This zero-duality gap with polynomial multipliers reduces to the classical zero-duality gap with constant multipliers when considering it in the setting of SOS-convex polynomial programs or quadratic programs with the hidden convexity. We also show that, in the framework of truncated polynomial systems, the zero-duality gap with polynomial multipliers can be checked via the classical Karush–Kuhn–Tucker condition under an additional convexity condition. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of finding a discrete subtree of minimum variance with bounded size of a given tree. We show that the problem is NP-hard on very simple trees and it remains difficult even if we consider the Mean Absolute Deviation criterion on star graphs. Referring to the variance criterion, we first propose a reformulation of the problem as an Integer Quadratic Program that, however, does not have particular structural properties that may help in finding good lower bounds on the optimal value of the problem. Then, basing on recent results on conic optimization, we investigate alternative reformulations of the problem in order to obtain some lower bounds. In particular, we exploit a continuous linear, conic, reformulation of the problem and show that this is, in fact, an exact linear reformulation of the Integer Quadratic Program. Alternatively, by referring to the upper envelope approach, we show how to obtain a lower bound for the optimal objective function value of our discrete tree-shaped facility location problem in pseudo-polynomial time. [ABSTRACT FROM AUTHOR]

This paper proposes a second-order cone programming (SOCP) relaxation for the generalized trust-region problem by exploiting the property that any symmetric matrix and identity matrix can be simultaneously diagonalizable. We show that our proposed SOCP relaxation can provide a lower bound as tight as that of the standard semidefinite programming (SDP) relaxation. Moreover, we provide a sufficient condition under which the proposed SOCP relaxation is exact. Since the standard SDP relaxation suffers from a much heavier computing burden, the proposed SOCP relaxation has a much higher efficiency in solving process. Then we design a branch-and-bound algorithm based on this SOCP relaxation to obtain the global optimal solution for a general problem. Three types of numerical experiments are carried out to demonstrate the effectiveness and efficiency of our proposed SOCP relaxation. [ABSTRACT FROM AUTHOR]

In this paper, we propose an algorithm to globally solve the extended trust-region subproblem with two linear intersecting cuts. Based on the tightness of the linear cuts at optimal solution, we can resolve the original problem by solving either a traditional trust-region subproblem over a sphere or a semidefinite programming relaxation with second-order cone constraints. Two examples from literature and numerical experiment on randomly generated instances are used to demonstrate how the proposed algorithm works. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel low-dimensional semidefinite programming (SDP) relaxation for convex quadratically constrained nonconvex quadratic programming problems. This new relaxation is derived by simultaneous matrix diagonalization method under the difference of convex decomposition scheme. The highlight of the relaxation is the low dimensionality of the positive semidefinite constraint, which only depends on the number of negative eigenvalues in the objective function. We prove that a mixed SOCP and SDP relaxation appeared in the literature is equivalent to the proposed relaxation, while the proposed relaxation has fewer constraints. We also provide conditions under which the proposed relaxation is as tight as the classical SDP relaxation and provides an optimal value for the original problem. For general cases, a spatial branch-and-bound algorithm is designed for finding a global optimal solution. Extensive numerical experiments support that the proposed algorithm outperforms two cutting-edge algorithms when the problem size is medium or large and the number of negative eigenvalues in the nonconvex objective function is relatively small. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of nonconvex nonhomogeneous quadratically constrained quadratic optimization problem. We derive some sufficient condition for the input data, and then establish a semi-definite approximation bound based on a randomization algorithm. The approximation bound is optimal in the order of m in general under the given restriction on the input data. [ABSTRACT FROM AUTHOR]

Semidefinite programming, SDP, relaxations have proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem, QAP, arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal-dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers ADMM in combination with facial reduction, FR, to solve the SDP relaxation. This first order approach allows for: inexpensive iterations, a method of cheaply obtaining low rank solutions; and a trivial way of exploiting the FR for adding cutting plane inequalities. In fact, we solve the doubly nonnegative, DNN, relaxation that includes both the SDP and all the nonnegativity constraints. When compared to current approaches and current best available bounds we obtain robustness, efficiency and improved bounds. [ABSTRACT FROM AUTHOR]

The problem of estimating the phases (angles) of a complex unit-modulus vector z from their noisy pairwise relative measurements C = zz* +σW, where W is a complex-valued Gaussian random matrix, is known as phase synchronization. The maximum likelihood estimator (MLE) is a solution to a unit-modulus-constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite programming (SDP) relaxation or the generalized power method (GPM). Numerical experiments suggest that both of these methods succeed with high probability for σ up to Õ(n1/2), yet existing analyses only confirm this observation for σ up to O(n1/4). In this paper, we bridge the gap by proving that the SDP relaxation is tight for σ = O(√ n/log n), and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter C∞ bound for the MLE. A novel technique we develop in this paper is to (theoretically) track n closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an C∞ perturbation bound for leading eigenvectors. Our result also confirms predictions that use techniques from statistical mechanics. [ABSTRACT FROM AUTHOR]

This paper proposes an exact algorithm for the Max-Mean dispersion problem ( $$Max-Mean DP$$ ), an NP-Hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. This relaxation can be tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve $$Max-Mean DP$$ instances to optimality. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up to 100 elements, outperforming other alternative approaches. [ABSTRACT FROM AUTHOR]

This paper is concerned with the computation of the principal components for a general tensor, known as the tensor principal component analysis (PCA) problem. We show that the general tensor PCA problem is reducible to its special case where the tensor in question is super-symmetric with an even degree. In that case, the tensor can be embedded into a symmetric matrix. We prove that if the tensor is rank-one, then the embedded matrix must be rank-one too, and vice versa. The tensor PCA problem can thus be solved by means of matrix optimization under a rank-one constraint, for which we propose two solution methods: (1) imposing a nuclear norm penalty in the objective to enforce a low-rank solution; (2) relaxing the rank-one constraint by semidefinite programming. Interestingly, our experiments show that both methods can yield a rank-one solution for almost all the randomly generated instances, in which case solving the original tensor PCA problem to optimality. To further cope with the size of the resulting convex optimization models, we propose to use the alternating direction method of multipliers, which reduces significantly the computational efforts. Various extensions of the model are considered as well. [ABSTRACT FROM AUTHOR]

We consider the design of semidefinite programming (SDP) based approximation algorithm for the problem Max Hypergraph Cut with Limited Unbalance (MHC-LU): Find a partition of the vertices of a weighted hypergraph H = ( V,E) into two subsets V, V with || V| − | V|| ⩽ u for some given u and maximizing the total weight of the edges meeting both V and V. The problem MHC-LU generalizes several other combinatorial optimization problems including Max Cut, Max Cut with Limited Unbalance (MC-LU), Max Set Splitting, Max E k-Set Splitting and Max Hypergraph Bisection. By generalizing several earlier ideas, we present an SDP randomized approximation algorithm for MHC-LU with guaranteed worst-case performance ratios for various unbalance parameters τ = u/| V |. We also give the worst-case performance ratio of the SDP-algorithm for approximating MHC-LU regardless of the value of τ. Our strengthened SDP relaxation and rounding method improve a result of Ageev and Sviridenko (2000) on Max Hypergraph Bisection (MHC-LU with u = 0), and results of Andersson and Engebretsen (1999), Gaur and Krishnamurti (2001) and Zhang et al. (2004) on Max Set Splitting (MHC-LU with u = | V|). Furthermore, our new formula for the performance ratio by a tighter analysis compared with that in Galbiati and Maffioli (2007) is responsible for the improvement of a result of Galbiati and Maffioli (2007) on MC-LU for some range of τ. [ABSTRACT FROM AUTHOR]

Motivated by applications in wireless communications, this paper develops semidefinite programming (SDP) relaxation techniques for some mixed binary quadratically constrained quadratic programs (MBQCQP) and analyzes their approximation performance. We consider both a minimization and a maximization model of this problem. For the minimization model, the objective is to find a minimum norm vector in N-dimensional real or complex Euclidean space, such that M concave quadratic constraints and a cardinality constraint are satisfied with both binary and continuous variables. By employing a special randomized rounding procedure, we show that the ratio between the norm of the optimal solution of the minimization model and its SDP relaxation is upper bounded by O(Q²(M-Q+1)+M²) in the real case and by O(M(M-Q+1)) in the complex case. For the maximization model, the goal is to find a maximum norm vector subject to a set of quadratic constraints and a cardinality constraint with both binary and continuous variables. We show that in this case the approximation ratio is bounded from below by O(∈/ln(M)) for both the real and the complex cases. Moreover, this ratio is tight up to a constant factor. [ABSTRACT FROM AUTHOR]

In this article we propose a simple heuristic algorithm for approaching the maximally predictable portfolio, which is constructed so that return model of the resulting portfolio would attain the largest goodness-of-fit. It is obtained by solving a fractional program in which a ratio of two convex quadratic functions is maximized, and the number of variables associated with its nonconcavity has been a bottleneck in spite of continuing endeavour for its global optimization. The proposed algorithm can be implemented by simply solving a series of convex quadratic programs, and computational results show that it yields within a few seconds a (near) Karush–Kuhn–Tucker solution to each of the instances which were solved via a global optimization method in [H. Konno, Y. Takaya and R. Yamamoto,A maximal predictability portfolio using dynamic factor selection strategy, Int. J. Theor. Appl. Fin. 13 (2010) pp. 355–366]. In order to confirm the solution accuracy, we also pose a semidefinite programming relaxation approach, which succeeds in ensuring a near global optimality of the proposed approach. Our findings through computational experiments encourage us not to employ the global optimization approach, but to employ the local search algorithm for solving the fractional program of much larger size. [ABSTRACT FROM AUTHOR]

This letter considers constrained steering direction estimation in the presence of additive Gaussian disturbance. The uncertainty region is modeled through double-sided quadratic constraints (up to three) and the Maximum Likelihood (ML) criterion is adopted to get the direction estimator. It is shown that the considered formulation leads to a fractional Quadratically Constrained Quadratic Program (QCQP) whose solution can be computed in polynomial time via semidefinite programming relaxation, Charnes-Cooper transformation, and suitable rank-one decomposition tools. At the analysis stage, with reference to a specific constraint set, the performance of the devised estimator is compared with the constrained Cramer Rao lower Bound (CRB). [ABSTRACT FROM AUTHOR]

In this paper, we consider suboptimal cooperative downlink beamforming strategies to maximize the user sum rate in a clustered multicell system with limited feedback. We decouple the problem into multiple independent subproblems through the uplink–downlink duality theorem. Semidefinite relaxation is applied to transform the original nonconvex problem into a convex semidefinite programming problem, which can be efficiently solved in polynomial time. We propose a novel limited feedback scheme based on a compressive sensing technique that can yield high-quality channel state information (CSI) feedback. We also consider a limited feedback scenario where base stations within one cluster have different estimates of the same CSI knowledge. We investigate the channel quantization criterion by choosing the codeword vector that has the minimum norm of the difference between the codeword and the normalized channel. Numerical results demonstrate the effectiveness of the proposed beamforming algorithm and limited feedback schemes. [ABSTRACT FROM PUBLISHER]

Consider the weighted maxmin dispersion problem of locating point(s) in a given region X ⊆ Rn that is/are furthest from a given set of m points. The region is assumed to be convex under componentwise squaring. We show that this problem is NP-hard even when A is a box and the weights are equal. We then propose a convex relaxation of this problem for finding an approximate solution and derive an approximation bound of 1-O(√ln(m)γ*)/2, where γ* depends on χ. When χ is a box or a product of low-dimensional spheres, γ* = O (1/n ) and the convex relaxation reduces to a semidefinite program and a second-order cone program. [ABSTRACT FROM AUTHOR]

Our interest lies in solving sum of squares (SOS) relaxations of large-scale unconstrained polynomial optimization problems. Because interior-point methods for solving these problems are severely limited by the large-scale, we are motivated to explore efficient implementations of an accelerated first-order method to solve this class of problems. By exploiting special structural properties of this problem class, we greatly reduce the computational cost of the first-order method at each iteration. We report promising computational results as well as a curious observation about the behaviour of the first-order method for the SOS relaxations of the unconstrained polynomial optimization problem. [ABSTRACT FROM AUTHOR]

We study the ideal generated by polynomials vanishing on a semialgebraic set and give elementary proofs for some equivalent conditions for reality of ideals or S-radical ideals. These results can be applied for modifying polynomial optimization problems so that the associated semidefinite programming relaxation problems have no duality gap. [ABSTRACT FROM AUTHOR]

Examples of weakly infeasible semidefinite programs (SDP) are useful to test whether SDP solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre's semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible SDP. Such examples could be used to test whether a SDP solver can detect weak infeasibility. In addition, in this note, we generate weakly infeasible SDP from an instance of polynomial optimization with nonempty feasible region and solve them by SDP solvers. Although all semidefinite programming relaxation problems are infeasible, we observe that SDP solvers do not detect the infeasibility and that values returned by SDP solvers are equal to the optimal value of the instance due to numerical round-off errors. [ABSTRACT FROM AUTHOR]

Sum-rate maximization in two-way amplify-and-forward (AF) multiple-input multiple-output (MIMO) relaying belongs to the class of difference-of-convex functions (DC) programming problems. DC programming problems occur also in other signal processing applications and are typically solved using different modifications of the branch-and-bound method which, however, does not have any polynomial time complexity guarantees. In this paper, we develop two efficient polynomial time algorithms for the sum-rate maximization in two-way AF MIMO relaying. The first algorithm guarantees to find at least a Karush-Kuhn-Tucker (KKT) solution. There is a strong evidence, however, that such a solution is actually globally optimal. The second algorithm that is based on the generalized eigenvectors shows the same performance as the first one with reduced computational complexity. The objective function of the problem is represented as a product of quadratic fractional ratios and parameterized so that its convex part (versus the concave part) contains only one (or two) optimization variables. One of the algorithms is called POlynomial Time DC (POTDC) and is based on semi-definite programming (SDP) relaxation, linearization, and an iterative Newton-type search over a single parameter. The other algorithm is called RAte-maximization via Generalized EigenvectorS (RAGES) and is based on the generalized eigenvectors method and an iterative search over two (or one, in its approximate version) optimization variables. We derive an upper-bound for the optimal value of the corresponding optimization problem and show by simulations that this upper-bound is achieved by both algorithms. It provides an evidence that the algorithms find a global optimum. The proposed methods are also superior to other state-of-the-art algorithms. [ABSTRACT FROM PUBLISHER]

In this paper, we strengthen the edge-based semidefinite programming relaxation (ESDP) recently proposed by Wang, Zheng, Boyd, and Ye (SIAM J. Optim. 19:655-673, ) by adding lower bound constraints. We show that, when distances are exact, zero individual trace is necessary and sufficient for a sensor to be correctly positioned by an interior solution. To extend this characterization of accurately positioned sensors to the noisy case, we propose a noise-aware version of ESDP ( ρ-ESDP) and show that, for small noise, a small individual trace is equivalent to the sensor being accurately positioned by a certain analytic center solution. We then propose a postprocessing heuristic based on ρ-ESDP and a distributed algorithm to solve it. Our computational results show that, when applied to a solution obtained by solving ρ-ESDP proposed of Pong and Tseng (Math. Program. doi:), this heuristics usually improves the RMSD by at least 10%. Furthermore, it provides a certificate for identifying accurately positioned sensors in the refined solution, which is not common for existing refinement heuristics. [ABSTRACT FROM AUTHOR]

SFSDP is a Matlab package for solving sensor network localization (SNL) problems. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) by Biswas and Ye [2004]. To improve the efficiency of FSDP, SFSDP exploits the aggregated and correlative sparsity of a sensor network localization problem. As a result, SFSDP can handle much larger problems than other software as well as three-dimensional anchor-free problems. SFSDP analyzes the input data of a sensor network localization problem, solves the problem, and displays the computed locations of sensors. SFSDP also includes the features of generating test problems for numerical experiments. [ABSTRACT FROM AUTHOR]

We investigate the relationships between various sum of squares (SOS) and semidefinite programming (SDP) relaxations for the sensor network localization problem. In particular, we show that Biswas and Ye's SDP relaxation is equivalent to the degree one SOS relaxation of Kim et al. We also show that Nie's sparse-SOS relaxation is stronger than the edge-based semidefinite programming (ESDP) relaxation, and that the trace test for accuracy, which is very useful for SDP and ESDP relaxations, can be extended to the sparse-SOS relaxation. [ABSTRACT FROM AUTHOR]

We investigate in this paper the duality gap between the binary quadratic optimization problem and its semidefinite programming relaxation. We show that the duality gap can be underestimated by $${\xi_{r+1}\delta^2}$$, where δ is the distance between {−1, 1} and certain affine subspace, and ξ is the smallest positive eigenvalue of a perturbed matrix. We also establish the connection between the computation of δ and the cell enumeration of hyperplane arrangement in discrete geometry. [ABSTRACT FROM AUTHOR]

We consider a robust downlink beamforming optimization problem for secondary multicast transmission in a multiple-input multiple-output (MIMO) spectrum sharing cognitive radio (CR) network. The minimization of transmit power is formulated subject to both quality-of-service (QoS) constraints on the secondary receivers and interference temperature constraints on the primary users, under the assumption of imperfect channel state information (CSI). The problem is a nonconvex quadratically constrained quadratic program (QCQP), and in general it is hard to achieve the global optimality. As a compromise, we present two randomized approximation algorithms for the problem via convex optimization techniques. Apart from the general setting of the robust beamforming problem, we identify one interesting special case, the robust problem of which can be solved efficiently. Simulation results are presented to demonstrate the performance gains of the proposed algorithms over an existing robust design. [ABSTRACT FROM PUBLISHER]

Recently Wang, Zheng, Boyd, and Ye (SIAM J Optim 19:655-673, 2008) proposed a further relaxation of the semidefinite programming (SDP) relaxation of the sensor network localization problem, named edge-based SDP (ESDP). In simulation, the ESDP is solved much faster by interior-point method than SDP relaxation, and the solutions found are comparable or better in approximation accuracy. We study some key properties of the ESDP relaxation, showing that, when distances are exact, zero individual trace is not only sufficient, but also necessary for a sensor to be correctly positioned by an interior solution. We also show via an example that, when distances are inexact, zero individual trace is insufficient for a sensor to be accurately positioned by an interior solution. We then propose a noise-aware robust version of ESDP relaxation for which small individual trace is necessary and sufficient for a sensor to be accurately positioned by a certain analytic center solution, assuming the noise level is sufficiently small. For this analytic center solution, the position error for each sensor is shown to be in the order of the square root of its trace. Lastly, we propose a log-barrier penalty coordinate gradient descent method to find such an analytic center solution. In simulation, this method is much faster than interior-point method for solving ESDP, and the solutions found are comparable in approximation accuracy. Moreover, the method can distribute its computation over the sensors via local communication, making it practical for positioning and tracking in real time. [ABSTRACT FROM AUTHOR]

This paper considers the problem of radar waveform design in the presence of colored Gaussian disturbance under a peak-to-average-power ratio (PAR) and an energy constraint. First of all, we focus on the selection of the radar signal optimizing the signal-to-noise ratio (SNR) in correspondence of a given expected target Doppler frequency (Algorithm 1). Then, through a max-min approach, we make robust the technique with respect to the received Doppler (Algorithm 2), namely we optimize the worst case SNR under the same constraints as in the previous problem. Since Algorithms 1 and 2 do not impose any condition on the waveform phase, we also devise their phase quantized versions (Algorithms 3 and 4, respectively), which force the waveform phase to lie within a finite alphabet. All the problems are formulated in terms of nonconvex quadratic optimization programs with either a finite or an infinite number of quadratic constraints. We prove that these problems are NP-hard and, hence, introduce design techniques, relying on semidefinite programming (SDP) relaxation and randomization as well as on the theory of trigonometric polynomials, providing high-quality suboptimal solutions with a polynomial time computational complexity. Finally, we analyze the performance of the new waveform design algorithms in terms of detection performance and robustness with respect to Doppler shifts. [ABSTRACT FROM PUBLISHER]

Recent advances in wireless sensor networks have led to renewed interests in the problem of source localization. Source localization has broad range of applications such as emergency rescue, asset inventory, and resource management. Among various measurement models, one important and practical source signal measurement is the received signal time of arrival (TOA) at a group of collaborative wireless sensors. Without time-stamp at the transmitter, in traditional approaches, these received TOA measurements are subtracted pairwise to form time-difference of arrival (TDOA) data for source localization, thereby leading to a 3-dB loss in signal-to-noise ratio (SNR). We take a different approach by directly applying the original measurement model without the subtraction preprocessing. We present two new methods that utilize semidefinite programming (SDP) relaxation for direct source localization. We further address the issue of robust estimation given measurement errors and inaccuracy in the locations of receiving sensors. Our results demonstrate some potential advantages of source localization based on the direct TOA data over time-difference preprocessing. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between the so-called bi-quadratic optimization problem and its semidefinite programming (SDP) relaxation. It is shown that each r-bound approximation solution of the relaxed bi-linear SDP can be used to generate in randomized polynomial time an $${\mathcal{O}(r)}$$-approximation solution of the original bi-quadratic optimization problem, where the constant in $${\mathcal{O}(r)}$$ does not involve the dimension of variables and the data of problems. For special cases of maximization model, we provide an approximation algorithm for the considered problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider the following indefinite complex quadratic maximization problem: maximize z Qz, subject to z ∈ ℂ and z = 1, k = 1,..., n, where Q is a Hermitian matrix with tr Q = 0, z ∈ ℂ is the decision vector, and m ⩾ 3. An Ω(1/log n) approximation algorithm is presented for such problem. Furthermore, we consider the above problem where the objective matrix Q is in bilinear form, in which case a $$ 0.7118\left( {\cos \frac{\pi } {m}} \right)^2 $$ approximation algorithm can be constructed. In the context of quadratic optimization, various extensions and connections of the model are discussed. [ABSTRACT FROM AUTHOR]

This correspondence considers the problem of robust waveform design in the presence of colored Gaussian disturbance under a similarity and an energy constraint. We resort to a max-min approach, where the worst case detection performance (over the possible Doppler shifts) is optimized with respect to the radar waveform under the previously mentioned constraints. The resulting optimization problem is a non-convex Quadratically Constrained Quadratic Program (QCQP) with an infinite number of constraints, which is NP-hard in general and typically difficult to solve. Hence, we propose an algorithm with a polynomial computational complexity to generate a good sub-optimal solution for the aforementioned QCQP. The analysis, conducted in comparison with some known radar waveforms, shows that the sub-optimal solutions by the algorithm lead to high-quality radar signals. [ABSTRACT FROM PUBLISHER]

Two kinds of MAX RES CUT problems, the MAX s− t CUT and the MAX s− t− v CUT, with limited unbalanced constraints are considered. Approximation algorithms used in Frieze and Jerrum (Integer Programming and Combinatorial Optimization, vol. 920, pp. 1–13, Springer, Berlin, ), Galbiati and Maffioli (Theor. Comput. Sci. 385:78–87, ), Han et al. (Math. Program. Ser. B 92:509–535, ) and Ye (Math. Programm. 90:101–111, ) are extended to the two MAX RES CUT problems. A special matrix P is constructed by which it can ensure that the given nodes s, t are feasible to equality constraints with probability one for the MAX s− t CUT and s, t, v are feasible to equality constraints with at least probability 0.912 for the MAX s− t− v CUT. A fussy greedy sizing-adjusted procedure is then proposed to confirm that the round solution is feasible for all constraints. We find these extensions are nontrivial and some interesting results about performance ratio are obtained for the MAX RES CUT problem with limited unbalanced constraints. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the problem of constrained code optimization for radar space-time adaptive processing (STAP) in the presence of colored Gaussian disturbance. At the design stage, we devise a code design algorithm complying with the following optimality criterion: maximization of the detection performance under a control on the regions of achievable values for the temporal and spatial Doppler estimation accuracy, and on the degree of similarity with a pre-fixed radar code. The resulting quadratic optimization problem is solved resorting to a convex relaxation that belongs to the semidefinite program (SDP) class. An optimal solution of the initial problem is then constructed through a suitable rank-one decomposition of an optimal solution of the relaxed one. At the analysis stage, we assess the performance of the new algorithm both on simulated data and on the standard challenging the Knowledge-Aided Sensor Signal Processing and Expert Reasoning (KASSPER) datacube. [ABSTRACT FROM AUTHOR]

Based on the convergent sequence of SDP relaxations for a multivariate polynomial optimization problem (POP) by Lasserre (2006), Waki et al. (2006) constructed a sequence of sparse SDP relaxations to solve sparse POPs efficiently. Nevertheless, the size of the sparse SDP relaxation is the major obstacle in order to solve POPs of higher degree. This paper proposes an approach to transform general POPs to quadratic optimization problems (QOPs), which allows to reduce the size of the SDP relaxation substantially. We introduce different heuristics resulting in equivalent QOPs and show how sparsity of a POP is maintained under the transformation procedure. As the most important issue, we discuss how to increase the quality of the SDP relaxation for a QOP. Moreover, we increase the accuracy of the solution of the SDP relaxation by applying additional local optimization techniques. Finally, we demonstrate the high potential of this approach through numerical results for large scale POPs of higher degree. [ABSTRACT FROM AUTHOR]

We improve upon recent lower bounds on the minimum distortion of embedding certain finite metric spaces into L1. In particular, we show that for every n ≥ 1, there is an n-point metric space of negative type that requires a distortion of Ω(log log n) for such an embedding, implying the same lower bound on the integrality gap of a well-known semidefinite programming relaxation for sparsest cut. This result builds upon and improves the recent lower bound of (log log n)1/6-o(1) due to Khot and Vishnoi [The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into l1, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 2005, pp. 53-62]. We also show that embedding the edit distance metric on {0, 1}n into L1 requires a distortion of Ω(log n). This result improves a very recent (log n)1/2-o(1) lower bound by Khot and Naor [Nonembeddability theorems via Fourier analysis, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 2005, pp. 101-112]. [ABSTRACT FROM AUTHOR]

This paper considers adaptive detection and estimation in the presence of useful signal and interference mismatches. We assume a homogeneous environment where the random disturbance components from the primary and secondary data share the same covariance matrix. Moreover, the data under test contains a deterministic interference vector in addition to the possible useful signal. We focus on the situation where an energy fraction of both the useful signal and the deterministic interference may lie outside their nominal subspaces (conical uncertainty model). Under these conditions, we devise a procedure for the computation of the joint maximum likelihood (ML) estimators of the useful signal and interference vectors, resorting to a suitable rank-one decomposition of a semidefinite program (SDP) problem optimal solution. Hence, we use the aforementioned estimators for the synthesis of adaptive receivers based on different generalized likelihood ratio test (GLRT) criteria. At the analysis stage, we assess the performance of the new detectors in comparison with some decision rules, available in open literature. [ABSTRACT FROM AUTHOR]

This paper deals with the design of coded waveforms which optimize radar performances in the presence of colored Gaussian disturbance. We focus on the class of linearly coded pulse trains and determine the optimum radar code according to the following criterion: maximization of the detection performance under a control on the region of achievable Doppler estimation accuracies, and imposing a similarity constraint with a prefixed radar code. This last constraint is tantamount to requiring a similarity between the ambiguity functions of the devised waveform and of the pulse train encoded with the prefixed sequence. The resulting optimization problem is nonconvex and quadratic. In order to solve it, we propose a technique (with polynomial computational complexity) based on the relaxation of the original problem into a semidefinite program. Thus, the best code is determined through a rank-one decomposition of an optimal solution of the relaxed problem. At the analysis stage, we assess the performance of the new encoding technique in terms of detection performance, region of achievable Doppler estimation accuracies, and ambiguity function. [ABSTRACT FROM AUTHOR]

A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance between the two players is two. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best-known result (3.9546, 4.3931). To achieve the improved bounds, we call upon results from absorbing Markov chain theory and mathematical programming theory--particularly fractional quadratic programming and semidefinite programming. Moreover, we also establish some important properties of this problem, which could be of independent interest and useful for resolving this problem completely. Finally, we conjecture that the symmetric rendezvous value is asymptotically equal to 4.25 based on our numerical calculations. [ABSTRACT FROM AUTHOR]

Abstract: By means of polynomial decomposition, a control scheme for polynomial nonlinear systems with affine time-varying uncertain parameters is presented. The idea of polynomial decomposition is to convert the coefficients of polynomial into a matrix with free variables, so that the nonnegativity of polynomials with even orders can be checked by linear matrix inequality (LMI) solvers or bilinear matrix inequality (BMI) solvers. Control synthesis for polynomial nonlinear system is based on Lyapunov stability theorem in this paper. Constructing Lyapunov function and finding feedback controller are automatically finished by computer programming with algorithms given in this paper. For multidimension systems with relatively high-order controller, the controller constructed with full monomial base will be in numerous terms. To overcome this problem, the reduced-form controller with minimum monomial terms is derived by the proposed algorithm. Then a suboptimal control aiming at minimum cost performance with gain constraints is advanced. The control scheme achieves effective performance as illustrated by numerical examples. [Copyright &y& Elsevier]

A semidefinite programming (SDP) relaxation approach is proposed to solve multiuser detection problems in systems with M-ary quadrature amplitude modulation (M-QAM). In the proposed approach, the optimal M-ary maximum likelihood (ML) detection is carried out by converting the associated M-ary integer programming problem into a binary integer programming problem. Then a relaxation approach is adopted to convert the binary integer programming problem into an SDP problem. This relaxation process leads to a detector of much reduced complexity. A multistage approach is then proposed to improve the performance of the SDP relaxation based detectors. Computer simulations demonstrate that the symbol-error rate (SER) performance offered by the proposed multistage SDP relaxation based detectors outperforms that of several existing suboptimal detectors. [ABSTRACT FROM PUBLISHER]