Search

This paper investigates the elliptic localization for moving object problem from time delay (TD) and Doppler frequency shift (DFS) measurements, where the transmitter position and velocity are unknown. The transmitter is not perfectly time syncronized such that unknown offsets exist in the TD and DFS measurements. We propose to jointly estimate the object and transmitter positions and velocities and the offsets. Using the TD and DFS measurements from both the indirect and direct paths between the transmitter and the receivers, we formulate a non-convex weighted least squares (WLS) problem. Local convergence may occur when solving the non-convex WLS problem, implying that good estimate is not guaranteed. Thus, we relax the non-convex WLS problem into a convex semidefinite program by applying semidefinite relaxation (SDR). Moreover, we theoretically show that the performance can be improved by using multiple transmitters as compared to that using single transmitter, although more unknown parameters are introduced. We then extend the proposed SDR method to handle the multiple transmitters case. Finally, the mean square error analysis is provided to show that the proposed WLS method reaches the Cramer-Rao lower bound accuracy under small Gaussian noise condition. Simulation results validate the theoretical analysis and show the superior performance over the existing methods.

By exploiting the idea employed in the spectral Dai-Yuan method by Xue et al. [IEICE Trans. Inf. Syst. 101 (12)2984-2990 (2018)] and the approach applied in the modified Hager-Zhang scheme for nonsmooth optimization [PLos ONE 11(10): e0164289 (2016)], we develop a Dai-Yuan type iterative scheme for convex constrained nonlinear monotone system. The scheme's algorithm is obtained by combining its search direction with the projection method [Kluwer Academic Publishers, pp. 355-369(1998)]. One of the new scheme's attribute is that it is derivative-free, which makes it ideal for solving non-smooth problems. Furthermore, we demonstrate the method's application in image de-blurring problems by comparing its performance with a recent effective method. By employing mild assumptions, global convergence of the scheme is determined and results of some numerical experiments show the method to be favorable compared to some recent iterative methods.

We consider the incremental subgradient algorithm employing dynamic step sizes for minimizing the sum of a large number of component convex functions. The dynamic step size rule was firstly introduced by Goffin and Kiwiel [Math. Program., 1999, 85(1): 207-211] for the subgradient algorithm, soon later, for the incremental subgradient algorithm by Nedic and Bertsekas in [SIAM J. Optim., 2001, 12(1): 109-138]. It was observed experimentally that the incremental approach has been very successful in solving large separable optimizations, and that the dynamic step sizes generally have better computational performance than others in the literature. In the present paper, we propose two modified dynamic step size rules for the incremental subgradient algorithm and analyse the convergence properties of them. At last, the assignment problem is considered and the incremental subgradient algorithms employing different kinds of dynamic step sizes are applied to solve the problem. The computational experiments show that the two modified ones converges dramatically faster and stabler than the corresponding one in [SIAM J. Optim., 2001, 12(1): 109-138]. Particularly, for solving large separable convex optimizations, we strongly recommend the second one (see Algorithm 3.3 in the paper) since it has interesting computational performance and is the simplest one.

During the detailed design phase of an aerospace program, one of the most important consistency checks is to ensure that no two distinct objects occupy the same physical space. Since exact geometrical modeling is usually intractable, geometry models are discretized, which often introduces small interferences not present in the fully detailed model. In this paper, we focus on computing the depth of the interference, so that these false positive interferences can be removed, and attention can be properly focused on the actual design. Specifically, we focus on efficiently computing the penetration depth between two polyhedra, which is a well-studied problem in the computer graphics community. We formulate the problem as a constrained five-variable global optimization problem, and then derive an equivalent unconstrained, two-variable nonsmooth problem. To solve the optimization problem, we apply a popular stochastic multistart optimization algorithm in a novel way, which exploits the advantages of each problem formulation simultaneously. Numerical results for the algorithm, applied to 14 randomly generated pairs of penetrating polytopes, illustrate both the effectiveness and efficiency of the method.

To deal with ambiguities in partial label learning (PLL), the existing PLL methods implement disambiguations, by either identifying the ground-truth label or averaging the candidate labels. However, these methods can be easily misled by the false-positive labels in the candidate label set. We find that these ambiguities often originate from the noise caused by highly correlated or overlapping candidate labels, which leads to the difficulty in identifying the ground-truth label on the first attempt. To give the trained models more tolerance, we first propose the top-k partial loss and convex top-k partial hinge loss. Based on the losses, we present a novel top-k partial label machine (TPLM) for partial label classification. An efficient optimization algorithm is proposed based on accelerated proximal stochastic dual coordinate ascent (Prox-SDCA) and linear programming (LP). Moreover, we present a theoretical analysis of the generalization error for TPLM. Comprehensive experiments on both controlled UCI datasets and real-world partial label datasets demonstrate that the proposed method is superior to the state-of-the-art approaches.

Given a graph G and a set S ⊆ V ( G ) , the Δ -interval of S , [ S ] Δ , is the set formed by the vertices of S and every w ∈ V ( G ) forming a triangle with two vertices of S . If [ S ] Δ = S , then S is Δ -convex of G ; if [ S ] Δ = V ( G ) , then S is a Δ -interval set of G . The Δ -interval number of G is the minimum cardinality of a Δ -interval set and the Δ -convexity number of G is the maximum cardinality of a proper Δ -convex subset of V ( G ) . In this work, we show that the problem of computing the Δ -convexity number is W[1]-hard and NP-hard to approximate within a factor O ( n 1 − ɛ ) for any constant ɛ > 0 even for graphs with diameter 2 and that the problem of computing the Δ -interval number is NP-complete for general graphs. For the positive side, we present characterizations that lead to polynomial-time algorithms for computing the Δ -convexity number of chordal graphs and for computing the Δ -interval number of block graphs. We also present results on the Δ -hull, Δ -interval and Δ -convexity numbers concerning the three standard graph products, namely, the Cartesian, the strong and the lexicographic products, in function of these and well-studied parameters of the operands.

The notion of abstract convex structure generalizes the standard notion of convexity in linear spaces. We consider abstract convex structures that are combinatorial objects studied in various areas of mathematics and convex algebras as introduced in [8] and we study a general definition of convex preferences. Relations defined by aggregation of orderings are considered.

Convolutional transform learning (CTL), learning filters by minimizing the data fidelity loss function in an unsupervised way, is becoming very pervasive, resulting from keeping the best of both worlds: the benefit of unsupervised learning and the success of the convolutional neural network. There have been growing interests in developing efficient CTL algorithms. However, developing a convergent and accelerated CTL algorithm with accurate representations simultaneously with proper sparsity is an open problem. This article presents a new CTL framework with a log regularizer that can not only obtain accurate representations but also yield strong sparsity. To efficiently address our nonconvex composite optimization, we propose to employ the proximal difference of the convex algorithm (PDCA) which relies on decomposing the nonconvex regularizer into the difference of two convex parts and then optimizes the convex subproblems. Furthermore, we introduce the extrapolation technology to accelerate the algorithm, leading to a fast and efficient CTL algorithm. In particular, we provide a rigorous convergence analysis for the proposed algorithm under the accelerated PDCA. The experimental results demonstrate that the proposed algorithm can converge more stably to desirable solutions with lower approximation error and simultaneously with stronger sparsity and, thus, learn filters efficiently. Meanwhile, the convergence speed is faster than the existing CTL algorithms.

A set of vertices S of a graph G is a (geodesically) convex set, if S contains all the vertices belonging to any shortest path connecting two vertices of S . The cardinality of a maximum proper convex set of G is called the convexity number, con ( G ) , of G . The complementary prism G G ¯ of G is obtained from the disjoint union of G and its complement G ¯ by adding the edges of a perfect matching between them. In this work, we examine the convex sets of the complementary prism of a tree and derive formulas for the convexity numbers of the complementary prisms of all trees.

Support vector machines (SVM) have drawn wide attention for the last two decades due to its extensive applications, so a vast body of work has developed optimization algorithms to solve SVM with various soft-margin losses. To distinguish all, in this paper, we aim at solving an ideal soft-margin loss SVM: L0/1 soft-margin loss SVM (dubbed as L0/1-SVM). Many of the existing (non)convex soft-margin losses can be viewed as one of the surrogates of the L0/1 soft-margin loss. Despite its discrete nature, we manage to establish the optimality theory for the L0/1-SVM including the existence of the optimal solutions, the relationship between them and P-stationary points. These not only enable us to deliver a rigorous definition of L0/1 support vectors but also allow us to define a working set. Integrating such a working set, a fast alternating direction method of multipliers is then proposed with its limit point being a locally optimal solution to the L0/1-SVM. Finally, numerical experiments demonstrate that our proposed method outperforms some leading classification solvers from SVM communities, in terms of faster computational speed and a fewer number of support vectors. The bigger the data size is, the more evident its advantage appears.

We propose a computationally efficient method to construct nonparametric, heteroscedastic prediction bands for uncertainty quantification, with or without any user-specified predictive model. Our approach provides an alternative to the now-standard conformal prediction for uncertainty quantification, with novel theoretical insights and computational advantages. The data-adaptive prediction band is universally applicable with minimal distributional assumptions, has strong non-asymptotic coverage properties, and is easy to implement using standard convex programs. Our approach can be viewed as a novel variance interpolation with confidence and further leverages techniques from semi-definite programming and sum-of-squares optimization. Theoretical and numerical performances for the proposed approach for uncertainty quantification are analyzed., 21 pages, 4 figures

The tensor-tensor product-induced tensor nuclear norm (t-TNN) (Lu et al., 2020) minimization for low-tubal-rank tensor recovery attracts broad attention recently. However, minimizing the t-TNN faces some drawbacks. For example, the obtained solution could be suboptimal to the original problem due to its loose approximation. In this article, we extract a unified nonconvex surrogate of the tensor tubal rank as a tighter regularizer, which involves many popular nonconvex penalty functions. An iterative reweighted t-TNN algorithm is proposed to solve the resulting generalized nonconvex tubal rank minimization for tensor recovery. It converges to a critical point globally with rigorous proofs based on the Kurdyka-Łojasiwicz property. Furthermore, we provide the theoretical guarantees for exact and robust recovery by developing the tensor null space property. Extensive experiments demonstrate that our approach markedly enhances recovery performance compared with several state-of-the-art convex and nonconvex methods.

This paper focuses on the design of on-line optimal input sequence for robust active fault diagnosis (AFD) of discrete-time linear parameter varying (LPV) systems using set-theoretic methods. Instead of the traditional set-separation constraint conditions leading to the design of off-line input sequence, the proposed approach focuses on on-line (re)shaping of the input sequence based on the real-time information of the output to discriminate system modes at each time instant such that the conservatism of robust AFD has the potential to be further reduced. The criterion on the design of optimal input is characterized based on a non-convex fractional programming problem at each time instant, which is shown to be efficiently solved within a convex optimization framework. Aside this main contribution, by exploiting Lagrange duality, the optimal input is explicitly obtained by solving a characteristic equation. At the end, a physical circuit model is provided to illustrate the effectiveness of the proposed method.

With the wide range application of machine learning in healthcare for helping humans drive crucial decisions, data privacy becomes an inevitable concern due to the utilization of sensitive data such as patients records and registers of a company. Thus, constructing a privacy preserving machine learning model while still maintaining high accuracy becomes a challenging problem. In this paper, we propose two differentially private algorithms, i.e., Output Perturbation with aGM (OPERA) and Gradient Perturbation with aGM (GRPUA) for empirical risk minimization, a useful method to obtain a globally optimal classifier, by leveraging the analytic Gaussian mechanism (aGM) to achieve privacy preservation of sensitive medical data in a healthcare system. We theoretically analyze and prove utility upper bounds of proposed algorithms and compare them with prior algorithms in the literature. The analyses show that in the high privacy regime, our proposed algorithms can achieve a tighter utility bound for both settings: strongly convex and non-strongly convex loss functions. Besides, we evaluate the proposed private algorithms on three benchmark datasets, i.e., Adult, BANK and IPUMS-BR. The simulation results demonstrate that our approaches can achieve higher accuracy and lower objective values compared with existing ones in all three datasets while providing differential privacy guarantees.

The Lyapunov equation for polytopic linear inclusions over the space of Minkowski functions of nonempty compact and convex sets that contain the origin as an interior point is studied. In particular, necessary and sufficient conditions for the characterization, existence and uniqueness of its fundamental solution are derived.

In this paper, we obtain the criterion of boundedness of maximal operators associated with smooth hypersurfaces. Also we compute the exact value of the boundedness index of such operators associated with arbitrary convex analytic hypersurfaces in the case where the height of a hypersurface in the sense of A. N. Varchenko is greater than 2. Moreover, we obtain the exact value of the boundedness index for degenerated smooth hypersurfaces, i.e., for hypersurfaces satisfying conditions of the classical Hartman-Nirenberg theorem. The obtained results justify the Stein-Iosevich-Sawyer hypothesis for arbitrary convex analytic hypersurfaces as well as for smooth degenerated hypersurfaces. Also we discuss some related problems of the theory of oscillatory integrals.

Adaptive gradient algorithms have recently become extremely popular because they have been applied successfully in training deep neural networks, such as Adam, AMSGrad, and AdaBound. Despite their success, however, the distributed variant of the adaptive method, which is expected to possess a rapid training speed at the beginning and a good generalization capacity at the end, is rarely studied. To fill the gap, a distributed adaptive subgradient algorithm is presented, called D-AdaBound, where the learning rates are dynamically bounded by clipping the learning rates. Moreover, we obtain the regret bound of D-AdaBound, in which the objective functions are convex. Finally, we confirm the effectiveness of D-AdaBound by simulation experiments on different datasets. The results show the performance improvement of D-AdaBound relative to existing distributed online learning algorithms.

Implementing a proper clustering algorithm and a high accuracy classifier for applying on electricity smart meter data is the first stage in analyzing and managing electricity consumption. In this paper, Random Forest (RF) classifier optimized by Artificial Bee Colony (ABC) which is called Artificial Bee Colony-based Random Forest (ABC-RF) is proposed. Also, in order to determine the representative load curves, the Convex Clustering (CC) is used. The solution paths generated by convex clustering show relationships among clusters that were hidden by static methods such as k-means clustering. To validate the proposed method, a case study that includes a real dataset of residential smart meters is implemented. The results evidence that the proposed ABC-RF method provides a higher accuracy if compared to other classification methods.

International audience; This paper presents a computational method to test the stabilizability of discrete-time switched linear systems. The existence of a conic cover of the space on whose elements a convex condition holds is proved to be necessary and sufficient for stabilizability. An algorithm for computing a conic partition that satisfies the new necessary and sufficient condition is given. The algorithm, that allows also to determine bounds on the exponential convergence rate, is proved to overcome the conservatism of conditions equivalent to periodic stabilizability and is applied to a four dimensional system.

Many problems in industrial smart manufacturing, such as process operational optimization and decision-making, can be regarded as distributed non-convex optimization problems, whose goal is to utilize distributed nodes to cooperatively search for the minimal value of the global objective function. Considering data transmission mode, transmission condition and communication waste in industrial applications, it is meaningful to study the distributed non-convex optimization problem with an event-triggered strategy over time-varying directed networks. To solve such a problem, a distributed non-convex event-triggered algorithm is proposed in this paper. Under some assumptions on local objective functions, gradients and step-sizes, the convergence of the proposed event-triggered algorithm to the local minimum is proved. Moreover, it is obtained that the proposed distributed event-triggered algorithm has a convergence rate of O(1/ln(t)). Finally, two examples in industrial systems are provided to validate the effectiveness of the proposed algorithm.

The volumetric weight of a package has become an essential factor in calculating the delivery cost of shipments in the international logistics market. In this work, we extend the two-dimensional vector packing problem by considering a more realistic cost structure, which is a general function of volumetric weight. The problem is to pack a set of different items into some identical bins without violating weight limits and volume capacities so that the total delivery cost is minimized. We develop an exact approach based on a branch-and-price algorithm and subset-row inequalities for the problem. To efficiently solve the pricing problem in column generation, a label-setting algorithm with an effective label dominance rule and a bounding procedure is presented. A stronger label dominance rule is derived for the case where the cost function is convex. The computational results show that the exact method is effective in solving the various test instances of the problem. If the volumetric weight is not considered, the exact method can be adapted to solve the two-dimensional vector packing problem with piecewise linear cost function and outperformed the existing exact algorithm by computing 27 optimal solutions for previously open instances.

We consider the central configurations of the 1+N-body problem, where N bodies are infinitesimal and the remaining one body is dominant. For regular polygon central configurations, we prove that the masses of all the infinitesimal bodies are equal when N is odd and the masses of the alternate infinitesimal bodies must be equal when N is even. Moreover, in the case of N being even, we present the relationship of the mass parameters between two consecutive infinitesimal bodies.

The DC optimal power flow (DCOPF) problem is a fundamental problem in power systems operations and planning. With high penetration of uncertain renewable resources in power systems, DCOPF needs to be solved repeatedly for a large amount of scenarios, which can be computationally challenging. As an alternative to iterative solvers, neural networks are often trained and used to solve DCOPF. These approaches can offer orders of magnitude reduction in computational time, but they cannot guarantee generalization, and small training error does not imply small testing errors. In this work, we propose a novel algorithm for solving DCOPF that guarantees the generalization performance. First, by utilizing the convexity of DCOPF problem, we train an input convex neural network. Second, we construct the training loss based on KKT optimality conditions. By combining these two techniques, the trained model has provable generalization properties, where small training error implies small testing errors. In experiments, our algorithm improves the optimality ratio of the solutions by a factor of five in comparison to end-to-end models.