Most commercial CAD systems do not offer sufficient support for the design activity. The reason is that they cannot understand the functional requirements of the design product. The user is responsible for maintaining the functional requirements in different design phases. By incorporating constraint programming concepts, these CAD systems would evolve into systems which would maintain the functional requirements in the design process, and perform analysis and simulation of geometric models. The CAD systems incorporated with constraint programming concepts would reduce design time, avoid human fatigue and error, and also maintain consistency of the geometric constraints imposed on the model. The G+ system addresses these issues by introducing a constraint-based system for geometric modeling by object-oriented methods. The G+ is designed such that available specialized algorithms can be utilized to enable handling of non-linear problems by both iterative and non-iterative schemes.

Adaptive filters have found applications in many signal processing problems. In some situations, linear constraints are imposed on the filter weights such that the filter is forced to exhibit a certain desired response. Several algorithms for linearly constrained least-squares adaptive filtering have been developed in the literature. When implemented with finite precision arithmetic, these algorithms are inevitably subjected to rounding errors. It is essential to understand how these algorithms react to rounding errors.In this thesis, the numerical properties of three linearly constrained least-squares adaptive filtering algorithms, namely, the linearly constrained fast least algorithm, the linear systolic array for MVDR beamforming and the linearly constrained QRD-RLS algorithm, are studied. It is shown that all these algorithms can be separated into a constrained part and an unconstrained part. The numerical properties of unconstrained least-squares algorithms (i.e., the unconstrained part of the linearly constrained algorithms under study) are reviewed from the perspectives of error propagation, error accumulation and numerical persistency. It is shown that persistent excitation and sufficient numerical resolution are needed to ensure the stability of the CRLS algorithm, while the QRD-RLS algorithm is unconditionally stable. The numerical properties of the constrained algorithms are then examined. Based on the technique of how the constraints are applied, these algorithms can be grouped into two categories. The first two algorithms admit a similar structure in that the unconstrained parts preceed the constrained parts. Error propagation analysis shows that this structure gives rise to unstable error propagation in the constrained part. In contrast, the constrained part of the third algorithm preceeds the unconstrained part. It is shown that this algorithm gives an ++ / exact solution to a linearly constrained least-squares adaptive filtering problem with perturbed constraints and perturbed input data. A minor modification to the constrained part of the linearly constrained QRD-RLS algorithm is proposed to avoid a potential numerical difficulty due to the Gaussian elimination operation employed in the algorithm.

In this thesis we propose a new class of Linearly Constrained Convex Optimization methods based on the use of a generalization of Shepard's interpolation formula. We prove the properties of the surface such as the interpolation property at the boundary of the feasible region and the convergence of the gradient to the null space of the constraints at the boundary. We explore several descent techniques such as steepest descent, two quasi-Newton methods and the Newton's method. Moreover, we implement in the Matlab language several versions of the method, particularly for the case of Quadratic Programming with bounded variables. Finally, we carry out performance tests against Matab Optimization Toolbox methods for convex optimization and implementations of the standard log-barrier and active-set methods. We conclude that the steepest descent technique seems to be the best choice so far for our method and that it is competitive with other standard methods both in performance and empirical growth order.

No description available.

We propose a new method to perform functional principal component analysis (FPCA) for discretely observed functional data by solving successive optimization problems. The new framework can be applied to both regularly and irregularly observed data, and to both dense and sparse data. Our method does not require estimates of the individual sample functions or the covariance functions. Hence, it can be used to analyze functional data with multidimensional arguments (e.g. random surfaces). Furthermore, it can be applied to many processes and models with complicated or nonsmooth covariance functions. In our method, smoothness of eigenfunctions is controlled by directly imposing roughness penalties on eigenfunctions, which makes it more efficient and flexible to tune the smoothness. Efficient algorithms for solving the successive optimization problems are proposed. We provide the existence and characterization of the solutions to the successive optimization problems. The consistency of our method is also proved. Through simulations, we demonstrate that our method performs well in the cases with smooth samples curves, with discontinuous sample curves and nonsmooth covariance and with sample functions having two dimensional arguments (random surfaces), repectively. We apply our method to classification problems of retinal pigment epithelial cells in eyes of mice and to longitudinal CD4 counts data. In the second part of this dissertation, we propose a sparse Fisher’s discriminant analysis method with thresholded linear constraints. Various regularized linear discriminant analysis (LDA) methods have been proposed to address the problems of the LDA in high-dimensional settings. Asymptotic optimality has been established for some of these methods when there are only two classes. A difficulty in the asymptotic study for the multiclass classification is that for the two-class classification, the classification boundary is a hyperplane and an explicit formula for the classification error exists, however, in the case of multiclass, the boundary is usually complicated and no explicit formula for the error generally exists. Another difficulty in proving the asymptotic consistency and optimality for sparse Fisher’s discriminant analysis is that the covariance matrix is involved in the constraints of the optimization problems for high order components. It is not easy to estimate a general high-dimensional covariance matrix. Thus, we propose a sparse Fisher’s discriminant analysis method which avoids the estimation of the covariance matrix, provide asymptotic consistency results and the corresponding convergence rates for all components. To prove the asymptotic optimality, we provide an asymptotic upper bound for a general linear classification rule in the case of muticlass which is applied to our method to obtain the asymptotic optimality and the corresponding convergence rate. In the special case of two classes, our method achieves the same as or better convergence rates compared to the existing method. The proposed method is applied to multivariate functional data with wavelet transformations.

Neste trabalho, propomos um método de pontos interiores para minimização com restrições lineares de grande porte. Este método explora a linearidade das restrições, partindo de um ponto viável e preservando a viabilidade dos iterandos. Apresentamos os principais resultados de convergência global, além de uma descrição rica em detalhes de uma implementação prática de todos os passos do método. Para atestar a implementação do método, exibimos uma ampla experimentação numérica, e uma análise comparativa com métodos bem difundidos na comunidade de otimização contínua. / In this work, we propose an interior-point method for large-scale linearly constrained optimization. This method explores the linearity of the constraints, starting from a feasible point and preserving the feasibility of the iterates. We present the main global convergence results, together with a rich description of the implementation details of all the steps of the method. To validate the implementation of the method, we present a wide set of numerical experiments and a comparative analysis with well known softwares of the continuous optimization community.

Neste trabalho, propomos um método de pontos interiores para minimização com restrições lineares de grande porte. Este método explora a linearidade das restrições, partindo de um ponto viável e preservando a viabilidade dos iterandos. Apresentamos os principais resultados de convergência global, além de uma descrição rica em detalhes de uma implementação prática de todos os passos do método. Para atestar a implementação do método, exibimos uma ampla experimentação numérica, e uma análise comparativa com métodos bem difundidos na comunidade de otimização contínua. / In this work, we propose an interior-point method for large-scale linearly constrained optimization. This method explores the linearity of the constraints, starting from a feasible point and preserving the feasibility of the iterates. We present the main global convergence results, together with a rich description of the implementation details of all the steps of the method. To validate the implementation of the method, we present a wide set of numerical experiments and a comparative analysis with well known softwares of the continuous optimization community.

Evolutionary algorithms belongs among the youngest and the most progressive methods of solving difficult optimization tasks. They received huge popularity mainly due to good experimental results in optimization, a simplicity of the implementation and a high modularity, which is an ability to be modified for different problems. Among the most frequently used Evolutionary algorithms belongs Genetic Algorithm, Differential Evolution and Evolutionary Strategy. It is able to apply these algorithms and theirs variants to both continuous, discrete and mixed optimization tasks. A subject of this theses is to compare three main types of algorithms on the catalyst optimization task with mixed variables, linear constraints and experimentally evaluated fitness function.

Title: Optimization Problems under (max, min)-Linear Constraints and Some Related Topics. Author: Mahmoud Gad Department/Institue: Department of Probability and Mathematical Statis- tics Supervisor of the doctoral thesis: 1. Prof. RNDr. Karel Zimmermann,DrSc 2. Prof. Dr. Assem Tharwat, Cairo University, Egypt Abstract: Problems on algebraic structures, in which pairs of operations such as (max, +) or (max, min) replace addition and multiplication of the classical linear algebra have appeared in the literature approximately since the sixties of the last century. The first publications on these algebraic structures ap- peared by Shimbel [37] who applied these ideas to communication networks, Cunninghame-Green [12, 13], Vorobjov [40] and Gidffer [18] applied these alge- braic structures to problems of machine-time scheduling. A systematic theory of such algebraic structures was published probable for the first time in [14]. In recently appeared book [4] the readers can find latest results concerning theory and algorithms for (max, +)-linear systems of equations and inequalities. Since operation max replacing addition in no more a group, but a semigroup oppera- tion, it is a substantial difference between solving systems with variables on one side and systems with variables occuring on both sides of the equations....