Dynamic network reliability modeling under nonhomogeneous Poisson processes

In this paper, we consider a two-state (up and down) network consisting of n links. We study the D-spectrum based dynamic reliability of the network under the assumption that the links are subject to failure according to a nonhomogeneous Poisson process. Several mixture representations are provided for the reliability function of residual lifetime of used networks, under different conditions on the status of the network or its links. These representations enable us to explore the residual reliability of operating networks in terms of the reliability functions of residual lifetimes of upper record values. The distribution function of inactivity time of a network is examined under the condition that the network has failed by inspection time t. Stochastic ordering properties of the residual lifetimes of networks under conditional D-spectra are investigated. Several examples and graphs are also provided to illustrate the established results.     

Estimation for nonhomogeneous Poisson processes from aggregated data

A well-known heuristic for estimating the rate function or cumulative rate function of a nonhomogeneous Poisson process assumes that the rate function is piecewise constant on a set of data-independent intervals. We investigate the asymptotic (as the amount of data grows) behavior of this estimator in the case of equal interval widths, and show that it can be transformed into a consistent estimator if the interval lengths shrink at an appropriate rate as the amount of data grows.     

Asymptotic tail behavior of Poisson shot-noise processes with interdependence between shock and arrival time

This paper studies the tail behavior of the Poisson shot-noise processes with interdependent and heavy-tailed random shocks. In the presence of statistical dependence between the shock and its arrival time we establish the asymptotic behavior of the tail probability. Two examples are presented as illustrations of the main results as well.     

An optimal service rate in a Poisson arrival queue with two-stage service policy*

We consider a two-stage service policy for a Poisson arrival queueing system. The idle server starts to work with ordinary service rate when a customer arrives. If the number of customers in the system reaches N, the service rate gets faster and continues until the system becomes empty. Otherwise, the server finishes the busy period with ordinary service rate. After assigning various operating costs to the system, we show that there exists a unique fast service rate minimizing the long-run average cost per unit time.This work was supported by Korea Research Foundation Grant(KRF-2002-070-C00021).     

Robust least square semidefinite programming with applications

In this paper, we consider a least square semidefinite programming problem under ellipsoidal data uncertainty. We show that the robustification of this uncertain problem can be reformulated as a semidefinite linear programming problem with an additional second-order cone constraint. We then provide an explicit quantitative sensitivity analysis on how the solution under the robustification depends on the size/shape of the ellipsoidal data uncertainty set. Next, we prove that, under suitable constraint qualifications, the reformulation has zero duality gap with its dual problem, even when the primal problem itself is infeasible. The dual problem is equivalent to minimizing a smooth objective function over the Cartesian product of second-order cones and the Euclidean space, which is easy to project onto. Thus, we propose a simple variant of the spectral projected gradient method (Birgin et al. in SIAM J. Optim. 10:1196–1211, 2000) to solve the dual problem. While it is well-known that any accumulation point of the sequence generated from the algorithm is a dual optimal solution, we show in addition that the dual objective value along the sequence generated converges to a finite value if and only if the primal problem is feasible, again under suitable constraint qualifications. This latter fact leads to a simple certificate for primal infeasibility in situations when the primal feasible set lies in a known compact set. As an application, we consider robust correlation stress testing where data uncertainty arises due to untimely recording of portfolio holdings. In our computational experiments on this particular application, our algorithm performs reasonably well on medium-sized problems for real data when finding the optimal solution (if exists) or identifying primal infeasibility, and usually outperforms the standard interior-point solver SDPT3 in terms of CPU time.     

The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming

We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and the strong second order sufficient condition, the rate of convergence is linear and the ratio constant is proportional to 1/c, where c is the penalty parameter that exceeds a threshold . The research of Defeng Sun is partly supported by the Academic Research Fund from the National University of Singapore. The research of Jie Sun and Liwei Zhang is partly supported by Singapore–MIT Alliance and by Grants RP314000-042/057-112 of the National University of Singapore. The research of Liwei Zhang is also supported by the National Natural Science Foundation of China under project grant no. 10471015 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry, China.     

Solving k-cluster problems to optimality with semidefinite programming

This paper deals with the computation of exact solutions of a classical NP-hard problem in combinatorial optimization, the $k$ -cluster problem. This problem consists in finding a heaviest subgraph with $k$ nodes in an edge weighted graph. We present a branch-and-bound algorithm that applies a novel bounding procedure, based on recent semidefinite programming techniques. We use new semidefinite bounds that are less tight than the standard semidefinite bounds, but cheaper to get. The experiments show that this approach is competitive with the best existing ones.     

The algebraic degree of semidefinite programming

Given a generic semidefinite program, specified by matrices with rational entries, each coordinate of its optimal solution is an algebraic number. We study the degree of the minimal polynomials of these algebraic numbers. Geometrically, this degree counts the critical points attained by a linear functional on a fixed rank locus in a linear space of symmetric matrices. We determine this degree using methods from complex algebraic geometry, such as projective duality, determinantal varieties, and their Chern classes.     

Poisson point processes with exclusion

Summary We give the definition of Poisson point processes with exclusion by their local conditional distributions, treat the existence and uniqueness problem and their applications in percolation theory.     

On semidefinite programming relaxations of maximum k-section

We derive a new semidefinite programming bound for the maximum $k$ -section problem. For $k=2$ (i.e. for maximum bisection), the new bound is at least as strong as a well-known bound by Poljak and Rendl (SIAM J Optim 5(3):467?C487, 1995). For $k \ge 3$ the new bound dominates a bound of Karisch and Rendl (Topics in semidefinite and interior-point methods, 1998). The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem, but only requires the solution of a much smaller semidefinite program.     

Polynomial time solvability of non-symmetric semidefinite programming

In this paper, we consider semidefinite programming with non-symmetric matrices, which is called non-symmetric semidefinite programming (NSDP). We convert such a problem into a linear program over symmetric cones, which is polynomial time solvable by interior point methods. Thus, the NSDP problem can be solved in polynomial time. Such a result corrects the corresponding result given in the literature. Similar methods can be applied to nonlinear programming with non-symmetric matrices.     

Indefinite stochastic LQ control with cross term via semidefinite programming

An indefinite stochastic linear-quadratic (LQ) optimal control problem with cross term over an infinite time horizon is studied, allowing the weighting matrices to be indefinite. A systematic approach to the problem based on semidefinite programming (SDP) and related duality analysis is developed. Several implication relations among the SDP complementary duality, the existence of the solution to the generalized Riccati equation and the optimality of LQ problem are discussed. Based on these relations, a numerical procedure that provides a thorough treatment of the LQ problem via primal-dual SDP is given: it identifies a stabilizing optimal feedback control or determines the problem has no optimal solution. An example is provided to illustrate the results obtained.     

A filter method for nonlinear semidefinite programming with global convergence

In this study, a new filter algorithm is presented for solving the nonlinear semidefinite programming. This algorithm is inspired by the classical sequential quadratic programming method. Unlike the traditional filter methods, the sufficient descent is ensured by changing the step size instead of the trust region radius. Under some suitable conditions, the global convergence is obtained. In the end, some numerical experiments are given to show that the algorithm is effective.     

On sensitivity of central solutions in semidefinite programming

In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since a similar set for which the primal-dual Slater condition holds is always open. Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001     

Theory of semidefinite programming for Sensor Network Localization

We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior-point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we show, for the first time, that these networks can be localized in polynomial time. We also give a simple and efficient criterion for checking whether a given instance of the localization problem has a unique realization in using graph rigidity theory. Finally, we introduce a notion called strong localizability and show that the SDP model will identify all strongly localizable sub-networks in the input network. A preliminary version of this paper has appeared in the Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.     

Robust truss topology optimization via semidefinite programming with complementarity constraints: a difference-of-convex programming approach

The robust truss topology optimization against the uncertain static external load can be formulated as mixed-integer semidefinite programming. Although a global optimal solution can be computed with a branch-and-bound method, it is very time-consuming. This paper presents an alternative formulation, semidefinite programming with complementarity constraints, and proposes an efficient heuristic. The proposed method is based upon the concave–convex procedure for difference-of-convex programming. It is shown that the method can often find a practically reasonable truss design within the computational cost of solving some dozen of convex optimization subproblems.     

Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et?al. (J Comb Optim 2:71–109, 1998). Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in Klerk and Sotirov (Math Program A, 122(2), 225–246, 2010). Continuing in the same vein, we show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.     

Mathematical considerations of nonhomogeneous production processes

A production process in which the production matrix changes with respect to time is called a nonhomogeneous production process. This paper gives several mathematical results on these nonhomogeneous production processes.