16295262
A preconditioning proximal newton method for nondifferentiable convex optimization
We propose a proximal Newton method for solving nondifferentiable convex optimization. This method combines the generalized Newton method with Rockafellar’s proximal point algorithm. At each step, the proximal point is found approximately and the regularization matrix is preconditioned to overcome inexactness of this approximation. We show that such a preconditioning is possible within some accuracy and the second-order differentiability properties of the Moreau-Yosida regularization are invariant with respect to this preconditioning. Based upon these, superlinear convergence is established under a semismoothness condition.
19172237
A verification method for solutions of nonsmooth equations
This paper proposes a verification method for the existence of solutions of nonsmooth equations. We generalize the Krawczyk operator to nonsmooth equations by using the mean-value theorem for nonsmooth functions. We establish a semi-local convergence theorem for the generalized Newton method for nonsmooth equations. The proposed method is a combination of the generalized Krawczyk operator and the semi-local convergence theorem.ZusammenfassungDieser Artikel schlägt eine Methode zur Verifizierung der Existenz von Lösungen nicht-differenzierbarer Gleichungen vor. Wir verallgemeinern den Krawczyk-Operator auf nicht-differenzierbare Gleichungen indem wir den Mittelwertsatz für nicht-differenzierbare Funktionen benutzen. Wir entwickeln einen semilokalen Konvergenzsatz für das verallgemeinerte Newton-Verfahren, angewendet auf nicht-differenzierbare Gleichungen. Die vorgeschlagene Methode ist eine Kombination aus dem verallgemeinerten Krawczyk-Operator und dem semi-lokalen Konvergenzsatz.
33892015
A Multiple-Criteria Quadratic Programming Approach to Network Intrusion Detection
The early and reliable detection and deterrence of malicious attacks, both from external and internal sources are a crucial issue for today’s e-business. There are various methods available today for intrusion detection; however, every method has its limitations and new approaches should still be explored. The objectives of this study are twofold: one is to discuss the formulation of Multiple Criteria Quadratic Programming (MCQP) approach, and to investigate the applicability of the quadratic classification method to the intrusion detection problem. The demonstration of successful Multiple Criteria Quadratic Programming application in intrusion detection can add another option to network security toolbox. The classification results are examined by cross-validation and improved by an ensemble method. The results demonstrated that MCQP is excellent and stable. Furthermore, the outcome of MCQP can be improved by the ensemble method.
8507685
Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities
The smoothing Newton method for solving a system of nonsmooth equations F(x) = 0, which may arise from the nonlinear complementarity problem, the variational inequality problem or other problems, can be regarded as a variant of the smoothing method. At the kth step, the nonsmooth function F is approximated by a smooth function f(.,∈ κ ), and the derivative of f(.,∈ κ ) at x k is used as the Newton iterative matrix. The merits of smoothing methods and smoothing Newton methods are global convergence and convenience in handling. In this paper, we show that the smoothing Newton method is also superlinearly convergent if F is semismooth at the solution and f satisfies a Jacobian consistency property. We show that most common smooth functions, such as the Gabriel-More function, have this property. As an application, we show that for box constrained variational inequalities if the involved function is P- uniform, the iteration sequence generated by the smoothing Newton method will converge to the unique solution of the problem globally and superlinearly (quadratically).
1201471
Lossy and lossless compression for color-quantized images
An efficient compression scheme for color-quantized images based on progressive coding of color information has been developed. Rather than sorting color indexes into a linear list structure, a binary-tree structure of color indexes is proposed. With this structure the new algorithm can progressively recover an image from 2 colors up to all of the colors contained in the original image, i.e., a lossless recovery achieved. Experimental results show that it can efficiently compress images in both lossy and lossless cases. Typically for color-quantized Lena image with 256 colors, the algorithm achieved 0.5 bpp lower than state-of-the-art lossless compression methods while preserving the efficient lossy compression. Such a compression scheme is very attractive to many applications that require the ability to fast browsing or progressive transmission, and if necessary, to exactly recover the original image.
14272026
Fully automated facial symmetry axis detection in frontal color images
We consider the problem of automatically detecting a facial symmetry axis in what we will call a standard human face image (acquired when the subject is looking directly into the camera, in front of a clean gray background under controlled illumination). Images of this kind are encountered in face recognition scenarios; this detection should facilitate more sophisticated facial image processing. The proposed method is based on GLDH (gray level difference histogram) analysis and consists of three components: (1) the face region detection stage crops an approximate face region out of the background, (2) symmetry detection discovers a vertical axis to optimally bisect the region of interest, assuming it is bilaterally symmetric, and (3) orientation adjustment aligns the angle of the symmetry axis with the orientation of the face. An implementation of the method is described, and results are presented. This detector's robust performance is evidenced by its success finding symmetry axes in more than 7,500 images collected from 600 distinct subjects. One of our method's most noteworthy contributions is that, according to our experimental results, many of the automatically detected axes are more accurate than the reference axes. Our automated detector is a powerful tool because it is not as susceptible to human error as its manual counterpart and, as the first application of its kind, it could potentially serve as a new biometric.
12811258
A Parsimony Approach to Genome-Wide Ortholog Assignment
The assignment of orthologous genes between a pair of genomes is a fundamental and challenging problem in comparative genomics, since many computational methods for solving various biological problems critically rely on bona fide orthologs as input. While it is usually done using sequence similarity search, we recently proposed a new combinatorial approach that combines sequence similarity and genome rearrangement. This paper continues the development of the approach and unites genome rearrangement events and (post-speciation) duplication events in a single framework under the parsimony principle. In this framework, orthologous genes are assumed to correspond to each other in the most parsimonious evolutionary scenario involving both genome rearrangement and (post-speciation) gene duplication. Besides several original algorithmic contributions, the enhanced method allows for the detection of inparalogs. Following this approach, we have implemented a high-throughput system for ortholog assignment on a genome scale, called MSOAR, and applied it to the genomes of human and mouse. As the result will show, MSOAR is able to find 99 more true orthologs than the INPARANOID program did. We have also compared MSOAR with the iterated exemplar algorithm on simulated data and found that MSOAR performed very well in terms of assignment accuracy. These test results indiate that our approach is very promising for genome-wide ortholog assignment.
10227949
Analysis of nonsmooth vector-valued functions associated with second-order cones
Abstract.Let be the Lorentz/second-order cone in . For any function f from to , one can define a corresponding function fsoc(x) on by applying f to the spectral values of the spectral decomposition of x∈ with respect to . We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Fréchet differentiability, continuous differentiability, as well as (ρ-order) semismoothness. These results are useful for designing and analyzing smoothing methods and nonsmooth methods for solving second-order cone programs and complementarity problems.
12374753
Efficient Method for Geometric Attribute Estimation
A new method is proposed to estimate the discrete geometric attributes, such as normal vector and curvature. The method contains two steps: points sampling and 4D Shepard interpolation. In the first step, we extract points from point cloud and estimate the attribute of the sampled points. During the second step, we interpolate a global 4D Shepard surface over these sampled points and compute the attribute of each point in point cloud. This method is very effective for using a new global surface model. It benefits many applications such as segmentation, feature extraction, data preprocessing and etc. Application examples are given to verify the proposed method.