Explore chapters and articles related to this topic
Wearable Localization via Mobile Crowd Sensing
Published in Kaikai Liu, Xiaolin Li, Mobile SmartLife via Sensing, Localization, and Cloud Ecosystems, 2017
When the problem becomes complex, i.e., a self-localization application, as shown in Fig. 9.4, LS-based approaches may converge to the local optimal solutions when the measurement noise is not Gaussian or the initial value in iteration is not good. Converting the initial non-convex problem to a convex one is a typical solution to avoid the local optimal. Among existing solutions, semidefinite programming (SDP) has been demonstrated to have a tight bound with the initial non-convex problem and tends to achieve optimal global results [117]. The SDP approach has been widely used in the sensor network localization areas, i.e., self-localization as shown in Fig. 9.4, where the dense inter-node ranging information is utilized to infer the location relative to the anchor node. Usually two anchor nodes are need to resolve the 2D coordinates of the whole network without ambiguity.
Distributed Machine Learning for Network Big Data
Published in Yulei Wu, Fei Hu, Geyong Min, Albert Y. Zomaya, Big Data and Computational Intelligence in Networking, 2017
where S is an empirical covariance matrix, and λ determines the degree of the sparsity in Θ. Equation 14.1 is an instance of semidefinite programming (SDP), and thus can be solved by SDP algorithms such as the interior point method [6]. However, the interior point method requires a computationally expensive Hessian matrix, which makes it undesirable for large-scale data. Interestingly, an optimal Θ can also be found by iteratively solving a series of lasso problems [7], if Θ is initialized with a positive definite matrix (please refer to friedman2008sparse for the details of the algorithm). As an example, we estimated a graph by graphical lasso using scikit-learn [8] Wisconsin breast cancer data [9,30]. Taking ten features from the breast cancer data as an input, the graphical lasso estimated the sparse inverse covariance matrix. Figure 14.2 visualizes the estimated inverse covariance matrix, where nodes represent the features and edges represent the node dependencies.
Linear Programming and Mixed Integer Programming
Published in Erchin Serpedin, Thomas Chen, Dinesh Rajan, Mathematical Foundations for SIGNAL PROCESSING, COMMUNICATIONS, AND NETWORKING, 2012
There are many software packages for solving LP and MIP problems. The reader is encouraged to try noncommercial software like LP_SOLVE, GPLK or MINTO. Semidefinite programming solvers can be easily used for LP problems; packages like SeDuMi, SDPT3, CVX, Yalmip are all free and the latter has also a MIP module.
Convergence to a second-order critical point by a primal-dual interior point trust-region method for nonlinear semidefinite programming
Published in Optimization Methods and Software, 2022
Several numerical methods for solving nonlinear SDP problems have been proposed. These include augmented Lagrangian methods, sequential linear/quadratic SDP methods, filter SDP methods and interior point methods. Augmented Lagrangian methods for nonlinear SDP problems were studied by Fares, Apkarian and Noll [6], Kocvara and Stingl [16–19,31], Sun, Zhang and Wu [34] and Noll [28], for example. Other augmented Lagrangian methods include [11,24,29,33,37]. On the other hand, numerical methods based on sequential linear/quadratic programming methods were studied by Fares, Noll and Apkarian [7], Correa and Ramirez [5], Freund, Jarre and Vogelbusch [8], and Kanzow, Nagel, Kato and Fukushima [13], for example. Filter SDP methods were proposed by Correa and Ramirez [5], Gomez and Ramirez [9], Li and Sun [23] and Zhu and Zhu [44]. These methods solve linear/quadratic semidefinite programming problems by interior point methods at each iteration. Interior point methods for nonlinear SDP problems were studied by Yamashita, Yabe and Harada [42,43], Yamashita and Yabe [40], Kato, Yabe and Yamashita [15] and Yamakawa and Yamashita [38,39], for example. Other interior point methods were proposed by Jarre [12] and Leibfritz and Mostafa [22]. A survey of numerical methods for solving nonlinear SDP problems can be found in the paper by Yamashita and Yabe [41].
Exploiting low-rank structure in semidefinite programming by approximate operator splitting
Published in Optimization, 2022
Mario Souto, Joaquim D. Garcia, Álvaro Veiga
Traditionally, semidefinite programming has been widely used in control theory. Classic applications such as the stability of dynamic systems and stochastic control problems [9] have motivated the development of SDP over decades. Modern applications such as motion planning for humanoid robots [10] use SDP as a core element for control. In several cases, SDP problems in control can be formulated in the form of linear matrix inequalities (LMI) [11]. In this sense, for some particular applications in control, there is no need to use general SDP algorithms since some LMI problems have closed-form solutions, although adding a little complexity to the problem might render the closed form solutions useless. As a consequence, interior-point methods that were particularly developed to solve LMI problems were proposed [12]. An extensive literature on LMI can be found in [13,14].
A primal-dual interior point trust-region method for nonlinear semidefinite programming
Published in Optimization Methods and Software, 2021
Hiroshi Yamashita, Hiroshi Yabe, Kouhei Harada
These methods solve subproblems which can be converted to linear semidefinite programming problems at each iteration. As another approach, Jarre [12] applied a primal predictor corrector interior method to nonconvex SDP problems, and Yang and Yu [46] proposed a homotopy method for solving nonlinear SDP problems. Leibfritz and Mostafa [23] proposed an interior point trust-region algorithm for a class of nonlinear SDP problems. Yamashita et al. [45] proposed a line search primal-dual interior point method by using a primal-dual merit function and showed its global convergence property. Within the framework of the primal-dual interior point method, Yamashita and Yabe [42] analysed the local behaviour of the proposed method. Furthermore, Kato et al. [14] also proposed another line search primal-dual interior point method by introducing the shifted barrier KKT condition and derived a differentiable primal-dual merit function to prove the global convergence. We note that a similar approach for nonlinear SDP was also done by Yamakawa and Yamashita [40,41]. A survey of numerical methods for solving nonlinear SDP problems can be found in the paper by Yamashita and Yabe [43].