Convex optimization algorithms for cooperative RSS-based sensor localization

To obtain a global solution for the source location estimates, the cost function of RSS-based sensor localization is relaxed as convex optimization problem which can be solved by interior point method. Weighted squared least square (WSLS) and weighted least square (WLS) based optimization functions are proposed to locate the source nodes. The corresponding semidefinite programming (SDP), second-order cone program (SOCP) and mixed SOC/SDP algorithms are designed by considering the known or unknown transmit powers. The computational complexity of the proposed algorithms is derived by analyzing the number of variables and equality constraints produced in the relaxation. The simulations show that the mixed SOC/SDP runs faster than the SDP, although the algorithms have the approximately equal accuracy performance. Whether the transmit power is known or not, the accuracy performance of the WLS-SDP is better than that of the WSLS-SDP and WSLS-SOC/SDP algorithms. However the computational complexity of the WLS-SDP is greatly larger than that of WSLS-SOC/SDP and WSLS-SDP due to a large number of variables.     

Efficient hyperkernel learning using second-order cone programming

The kernel function plays a central role in kernel methods. Most existing methods can only adapt the kernel parameters or the kernel matrix based on empirical data. Recently, Ong et al. introduced the method of hyperkernels which can be used to learn the kernel function directly in an inductive setting. However, the associated optimization problem is a semidefinite program (SDP), which is very computationally expensive, even with the recent advances in interior point methods. In this paper, we show that this learning problem can be equivalently reformulated as a second-order cone program (SOCP), which can then be solved more efficiently than SDPs. Comparison is also made with the kernel matrix learning method proposed by Lanckriet et al. Experimental results on both classification and regression problems, with toy and real-world data sets, show that our proposed SOCP formulation has significant speedup over the original SDP formulation. Moreover, it yields better generalization than Lanckriet et al.'s method, with a speed that is comparable, or sometimes even faster, than their quadratically constrained quadratic program (QCQP) formulation.     

Constrained Stochastic LQC: A Tractable Approach

Despite the celebrated success of dynamic programming for optimizing quadratic cost functions over linear systems, such an approach is limited by its inability to tractably deal with even simple constraints. In this paper, we present an alternative approach based on results from robust optimization to solve the stochastic linear-quadratic control (SLQC) problem. In the unconstrained case, the problem may be formulated as a semidefinite optimization problem (SDP). We show that we can reduce this SDP to optimization of a convex function over a scalar variable followed by matrix multiplication in the current state, thus yielding an approach that is amenable to closed-loop control and analogous to the Riccati equation in our framework. We also consider a tight, second-order cone (SOCP) approximation to the SDP that can be solved much more efficiently when the problem has additional constraints. Both the SDP and SOCP are tractable in the presence of control and state space constraints; moreover, compared to the Riccati approach, they provide much greater control over the stochastic behavior of the cost function when the noise in the system is distributed normally.     

Control applications of nonlinear convex programming

Since 1984 there has been a concentrated effort to develop efficient interior-point methods for linear programming (LP). In the last few years researchers have begun to appreciate a very important property of these interior-point methods (beyond their efficiency for LP): they extend gracefully to nonlinear convex optimization problems. New interior-point algorithms for problem classes such as semidefinite programming (SDP) or second-order cone programming (SOCP) are now approaching the extreme efficiency of modern linear programming codes. In this paper we discuss three examples of areas of control where our ability to efficiently solve nonlinear convex optimization problems opens up new applications. In the first example we show how SOCP can be used to solve robust open-loop optimal control problems. In the second example, we show how SOCP can be used to simultaneously design the set-point and feedback gains for a controller, and compare this method with the more standard approach. Our final application concerns analysis and synthesis via linear matrix inequalities and SDP.     

A nonsmooth nonlinear conjugate gradient method for interactive contact force problems

Interactive rigid body simulation is important for robot simulation and virtual design. A vital part of the simulation is the computation of contact forces. This paper addresses the contact force problem, as used in interactive simulation. The contact force problem can be formulated in the form of a nonlinear complementarity problem (NCP), which can be solved using an iterative splitting method, such as the projected Gauss–Seidel (PGS) method. We present a novel method for solving the NCP problem by applying a Fletcher–Reeves type nonlinear nonsmooth conjugate gradient (NNCG) type method. We analyze and present experimental convergence behavior and properties of the new method. Our results show that the NNCG method has at least the same convergence rate as PGS, and in many cases better.     

Heuristic and exact algorithms for the max–min optimization of the multi-scenario knapsack problem

We are concerned with a variation of the standard 0–1 knapsack problem, where the values of items differ under possible S scenarios. By applying the ‘pegging test’ the ordinary knapsack problem can be reduced, often significantly, in size; but this is not directly applicable to our problem. We introduce a kind of surrogate relaxation to derive upper and lower bounds quickly, and show that, with this preprocessing, the similar pegging test can be applied to our problem. The reduced problem can be solved to optimality by the branch-and-bound algorithm. Here, we make use of the surrogate variables to evaluate the upper bound at each branch-and-bound node very quickly by solving a continuous knapsack problem. Through numerical experiments we show that the developed method finds upper and lower bounds of very high accuracy in a few seconds, and solves larger instances to optimality faster than the previously published algorithms.     

Antenna array synthesis with clusters of unmanned aerial vehicles

In this paper, we investigate the use of formations of Unmanned Aerial Vehicles (UAVs) as phased antenna arrays. This will help to improve communications with clusters of small unmanned aerial vehicles which are currently constrained by on-board power limitations. The problem of maximizing the power output from the array in the direction of the receiver is posed as an optimization problem which happens to be non-convex; a relaxation of this problem is then solved as a computationally tractable (convex) Second-Order Conic Program (SOCP). The performance obtained by the simplified approach is then tested against rigorous numerical bounds obtained using Semidefinite Programming (SDP) duality theory; these bounds are of independent interest in antenna theory. In order to maintain the objective value close to the optimal when the vehicles deviate from their positions (due to wind gusts, for example), a simple linear control law is proposed. Simulation results are given to show the effectiveness of the proposed approaches.     

Specialized fast algorithms for IQC feasibility and optimization problems

The conventional way to treat integral quadratic constraint (IQC) problems is to transform them into semi-definite programs (SDPs). SDPs can then be solved using interior point methods which have been proven efficient. This approach, however, is not always the most efficient since it introduces additional decision variables to the SDP, and the additional decision variables sometimes largely increase the complexity of the problem. In this paper, we demonstrate how to solve IQC problems by other alternatives. More specifically, we consider two cutting plane algorithms. We will show that in certain cases these cutting plane algorithms can solve IQC problems much faster than the conventional approach. Numerical examples, as well as some explanations from the point of view of computational complexity, are provided to support our point.     

Control and simulation for a closed-chain dual redundant ' manipulator system

The two-level hierarchical control scheme is adopted to solve a dual-chain robotic system formed by two redundant manipulators grasping a common object with hard point contacts. The upper-level coordinator gathers all the necessary information to resolve the force distribution problem so as to generate all the desired contact forces With all the desired contact forces being specified, the dynamics of each chain are decoupled. Therefore, the lower-level local control problem can be treated as a general open-chain redundant manipulator problem. Furthermore, the Compact-Dual LP method is applied to resolve the upper-level coordination problem; while the Compact QP method associated with the computed torque control method is adopted to solve the redundant manipulator problem. To obtain proper simulation results, the simulated actual contact forces are formulated and the corresponding simulation problem of the closed-chain robotic system is also completely solved in the article. Simulation results show that the two-level hierarchical control scheme is an effective and efficient algorithm for resolving the large-scale control problem of multiple-chain robotic systems. © 1995 John Wiley & Sons, Inc.     

An efficient multiple-kernel learning for pattern classification

Support vector machines (SVMs) have been broadly applied to classification problems. However, a successful application of SVMs depends heavily on the determination of the right type and suitable hyperparameter settings of kernel functions. Recently, multiple-kernel learning (MKL) algorithms have been developed to deal with these issues by combining different kernels together. The weight with each kernel in the combination is obtained through learning. Lanckriet et al. proposed a way of deriving the weights by transforming the learning into a semidefinite programming (SDP) problem with a transduction setting. However, the amount of time and space required by this method is demanding. In this paper, we reformulate the SDP problem with an induction setting and incorporate two strategies to reduce the search complexity of the learning process, based on the comments discussed in the Lanckriet et al. paper. The primal and dual forms of SDP are derived. A discussion on computation complexity is given. Experimental results obtained from synthetic and benchmark datasets show that the proposed method runs efficiently in multiple-kernel learning.     

Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness

In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time.     

On the complexity of a two-point boundary value problem in different settings

We study the complexity of a two-point boundary value problem. We concentrate on the linear problem of order k with separated boundary conditions. Right-hand side functions are assumed to be r times differentiable with all derivatives bounded by a constant. We consider three models of computation: deterministic with standard and linear information, randomized and quantum. In each setting, we construct an algorithm for solving the problem, which allows us to establish upper complexity bounds. In the deterministic setting, we show that the use of linear information gives us a speed-up of at least one order of magnitude compared with the standard information. For randomized algorithms, we show that the speed-up over standard deterministic algorithms is by 1/2 in the exponent. For quantum algorithms, we can achieve a speed-up by one order of magnitude. We also provide lower complexity bounds. They match upper bounds in the deterministic setting with the standard information, and almost match upper bounds in the randomized and quantum settings. In the deterministic setting with the linear information, a gap still remains between the upper and lower complexity bounds.     

A fast procedure for optimizing dynamic force distribution in multifingered grasping.

This correspondence deals with the dynamic force distribution (DFD) problem, i.e., computing the contact forces to equilibrate a dynamic external wrench on the grasped object. The sum of the normal force components is minimized for enhancing safety and saving energy. By this optimality criterion, the DFD problem can be transformed into a linear programming (LP) problem. Its objective function is the inner product of the dynamic external wrench and a vector, and the constraints on the vector, given by a set of linear inequalities, define a polytope. The solution to the LP problem can always be attained at the vertex of the polytope called the solution vertex. We notice that the polytope is determined by the grasp configuration. Along with the direction change of the dynamic external wrench, only the solution vertex moves to an adjacent vertex sequentially, whereas the polytope with all its vertices remains unchanged. Therefore, the polytope and the adjacencies of each vertex can be computed in the offline phase. Then, in the online phase, simply search the adjacencies of the old solution vertex for the new one. Without lost of optimality, such a DFD algorithm runs a thousandfold faster than solving the LP problem by the simplex method in real time.     

Solving Large-Margin Hidden Markov Model Estimation via Semidefinite Programming

In this paper, we propose to use a new optimization method, i.e., semidefinite programming (SDP), to solve the large-margin estimation (LME) problem of continuous-density hidden Markov model (CDHMM) in speech recognition. First, we introduce a new constraint for LME to guarantee the boundedness of the margin of CDHMM. Second, we show that the LME problem subject to this new constraint can be formulated as an SDP problem under some relaxation conditions. Therefore, it can be solved using many efficient optimization algorithms specially designed for SDP. The new LME/SDP method has been evaluated on a speaker independent E-set speech recognition task using the ISOLET database and a connected digit string recognition task using the TIDIGITS database. Experimental results clearly demonstrate that large-margin estimation via semidefinite programing (LME/SDP) can significantly reduce word error rate (WER) over other existing CDHMM training methods, such as MLE and MCE. It has also been shown that the new SDP-based method largely outperforms the previously proposed LME optimization methods using gradient descent search.     

Energy-efficient joint path-following for attitude-fixed space manipulators with bounds on completion time and motor voltage/current

This paper investigates the minimum-energy joint path-following problem for space manipulators whose base attitude is stabilized by reaction wheels. In the problem, manipulator joint path is specified for rest-to-rest motion and constraints are imposed as the upper bound on both motion completion time and the voltage/current limits of DC motors in manipulator joints and reaction wheels. We suggest a simple two-stage algorithm to address this problem. The algorithm first tries to find a global optimal solution by solving a relaxed convex problem. If the convex relaxation is not successful, then the algorithm solves subproblems iteratively to find a suboptimal solution. Since both problems are formulated as second-order cone programming (SOCP) form, they can be solved efficiently using dedicated SOCP solvers. The effectiveness of the proposed method is verified by numerical experiments.     

Convex Optimization Algorithms for Active Balancing of Humanoid Robots

We show that a large class of active balancing problems for legged robots can be framed as a second-order cone programming (SOCP) problem, a convex optimization problem for which efficient and numerically robust algorithms exist. We describe this general SOCP balancing framework, show that several existing optimization-based balancing strategies reduce to special cases of this more general formulation, and investigate the computational performance of our SOCP algorithms through simulation studies involving a humanoid model.     

Optimization of temperature of polysilicon rods

The problem of synthesis of optimal control for temperature of polysilicon rods is solved taking heat emission into account. A method of dynamic programming for linear systems with distributed parameters (SDP), a modified performance criterion, and a moderated form of solution to the functional Bellman equations for SDP are used. The obtained control algorithms for polysilicon were numerically realized earlier.     

Alternating optimization to solve penalized regression‐based clustering model

Two previously proposed heuristic algorithms for solving penalized regression‐based clustering model (PRClust) are (a) an algorithm that combines the difference‐of‐convex programming with a coordinate‐wise descent (DC‐CD) algorithm and (b) an algorithm that combines DC with the alternating direction method of multipliers (DC‐ADMM). In this paper, a faster method is proposed for solving PRClust. DC‐CD uses p × n × (n ? 1)/2 slack variables to solve PRClust, where n is the number of data and p is the number of their features. In each iteration of DC‐CD, these slack variable and cluster centres are updated using a second‐order cone programming (SOCP). DC‐ADMM uses p × n × (n ? 1) slack variables. In each iteration of DC‐ADMM, these slack variables and cluster centres are updated using ADMM. In this paper, PRClust is reformulated into an equivalent model to be solved using alternating optimization. Our proposed algorithm needs only n × (n ? 1)/2 slack variables, which is much less than that of DC‐CD and DC‐ADMM and updates them analytically using a simple equation in each iteration of the algorithm. Our proposed algorithm updates only cluster centres using an SOCP. Therefore, our proposed SOCP is much smaller than that of DC‐CD, which is used to update both cluster centres and slack variables. Experimental results on real datasets confirm that our proposed method is faster and much faster than DC‐ADMM and DC‐CD, respectively.     

Iteration complexity analysis of dual first-order methods for conic convex programming

In this paper we provide a detailed analysis of the iteration complexity of dual first-order methods for solving conic convex problems. When it is difficult to project on the primal feasible set described by conic and convex constraints, we use the Lagrangian relaxation to handle the conic constraints and then, we apply dual first-order algorithms for solving the corresponding dual problem. We give convergence analysis for dual first-order algorithms (dual gradient and fast gradient algorithms): we provide sublinear or linear estimates on the primal suboptimality and feasibility violation of the generated approximate primal solutions. Our analysis relies on the Lipschitz property of the gradient of the dual function or an error bound property of the dual. Furthermore, the iteration complexity analysis is based on two types of approximate primal solutions: the last primal iterate or an average primal sequence.     

Using instance-level constraints in agglomerative hierarchical clustering: theoretical and empirical results

Clustering with constraints is a powerful method that allows users to specify background knowledge and the expected cluster properties. Significant work has explored the incorporation of instance-level constraints into non-hierarchical clustering but not into hierarchical clustering algorithms. In this paper we present a formal complexity analysis of the problem and show that constraints can be used to not only improve the quality of the resultant dendrogram but also the efficiency of the algorithms. This is particularly important since many agglomerative style algorithms have running times that are quadratic (or faster growing) functions of the number of instances to be clustered. We present several bounds on the improvement in the running times of algorithms obtainable using constraints. A preliminary version of this paper appeared as Davidson and Ravi (2005b).