We illustrate some recent results on exact solutions to discrete-time l(1)-norm minimization problems with convolution constraints. A fixed-point property for this class of problems is introduced. The convolution cons...
详细信息
ISBN:
(纸本)0780395670
We illustrate some recent results on exact solutions to discrete-time l(1)-norm minimization problems with convolution constraints. A fixed-point property for this class of problems is introduced. The convolution constraints can be interpreted as a dynamic system with initial conditions. We show by construction that optimal solutions with a rational Z-transform exist for any initial conditions satisfying the fixed-point property. Some fixed-point initial conditions satisfy a further stability property. If there exists a stable fixed point, then for any initial condition in some neighbourbood of the fixed point an optimal solution can be constructed having a rational Z-transform.
We use linear programming (LP) to derive upper and lower bounds on the kissing number A(d) of any q-ary linear code C with distance distribution frequencies A(i), in terms of the given parameters [n, k, d]. In particu...
详细信息
ISBN:
(纸本)9781665403122
We use linear programming (LP) to derive upper and lower bounds on the kissing number A(d) of any q-ary linear code C with distance distribution frequencies A(i), in terms of the given parameters [n, k, d]. In particular, a polynomial method gives explicit analytic bounds in a certain range of parameters, which are sharp for some low-rate codes like the first-order Reed-Muller codes. The general LP bounds are more suited to numerical estimates. Besides the classical estimation of the probability of decoding error and of undetected error, we outline recent applications in hardware protection against side-channel attacks using code-based masking countermeasures, where the protection is all the more efficient a s the kissing number is low.
Signal transduction pathways play important roles in various biological processes such as cell cycle, apoptosis, proliferation, differentiation and responses to the external stimuli. Efficient computational methods ar...
详细信息
Signal transduction pathways play important roles in various biological processes such as cell cycle, apoptosis, proliferation, differentiation and responses to the external stimuli. Efficient computational methods are of great demands to map signaling pathways systematically based on the interactome and microarray data in the post-genome era. This paper proposes a novel approach to infer the pathways based on the network flow well studied in the operation research. The authors define a potentiality variable for each protein to denote the extent to which it contributes to the objective pathway. And the capacity on each edge is not a constant but a function of the potentiality variables of the corresponding two proteins. The total potentiality of all proteins is given an upper bound. The approach is formulated to a linear programming model and solved by the simplex method. Experiments on the yeast sporulation data suggest this novel approach recreats successfully the backbone of the MAPK signaling pathway with a low upper bound of the total potentiality. By increasing the upper bound, the approach successfully predicts all the members of the Mitogen-activated protein kinases （MAPK） pathway responding to the pheromone. This simple but effective approach can also be used to infer the genetic information processing pathways underlying the expression quantitative trait loci （eQTL） associations, illustrated by the second example.
In this paper, we propose two new perturbation simplex variants. Solving linear programming problems without introducing artificial variables, each of the two uses the dual pivot rule to achieve primal feasibility, an...
详细信息
In this paper, we propose two new perturbation simplex variants. Solving linear programming problems without introducing artificial variables, each of the two uses the dual pivot rule to achieve primal feasibility, and then the primal pivot rule to achieve optimality. The second algorithm, a modification of the first, is designed to handle highly degenerate problems more efficiently. Some interesting results concerning merit of the perturbation are established. Numerical results from preliminary tests are also reported. [ABSTRACT FROM AUTHOR]
It is well-known that the integrality gap of the usual linear programming relaxation for Maxcut is 2 - epsilon. For general graphs, we prove that for any c and any fixed boundk, adding linear constraints of support bo...
详细信息
ISBN:
(纸本)9780898716245
It is well-known that the integrality gap of the usual linear programming relaxation for Maxcut is 2 - epsilon. For general graphs, we prove that for any c and any fixed boundk, adding linear constraints of support bounded by k does not reduce the gap below 2-epsilon. We generalize this to prove that for any epsilon and any fixed bound k, strengthening the usual linear programming relaxation by doing k rounds of Sherali-Adams lift-and-project does not reduce the gap below 2 - epsilon. On the other hand, we prove that for dense graphs, this gap drops to 1 + epsilon after adding all linear constraints of support bounded by some constant depending on epsilon.
We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the expected and anticipated number of iterations of theseTodd's probabilistical...
详细信息
We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the expected and anticipated number of iterations of theseTodd's probabilisticalgorithms is bounded above by O(n^1.5). The random LP problem is model with the Cauchy distribution.
The paper researches a class of nonlinear integer programming problems the objective function of which is the sum of the products of some nonnegative linear functions in the given rectangle and the constraint function...
详细信息
ISBN:
(纸本)9783540743767
The paper researches a class of nonlinear integer programming problems the objective function of which is the sum of the products of some nonnegative linear functions in the given rectangle and the constraint functions of which are all linear as well as strategy variables of which are all integer ones. We give a, linear programming relax-PSO hybrid bound algorithm for solving the problem. The lower bound of the optimal value of the problem is determined by solving a linear programming relax which is obtained through equally converting the objective function into the exponential-logarithmic composite function and linearly lower approximating each exponential function and each logarithmic function over the rectangles. The upper bound of the optimal value and the feasible solution of it are found and renewed with particle swarm optimization (PSO). It is shown by the numerical results Oat the linear programming relax-PSO hybrid bound algorithm is better than the branch-and-bound algorithm in the computational scale and the computational time and the computational precision and overcomes the convergent difficulty of PSO.
In this paper, a new method to address the scheduling problem of a renewable energy community while considering network constraints and users' privacy preservation is proposed. The method decouples the optimizatio...
详细信息
In this paper, a new method to address the scheduling problem of a renewable energy community while considering network constraints and users' privacy preservation is proposed. The method decouples the optimization solution into two interacting procedures: conic projection(CP) and linear programming(LP) optimization. A new optimal CP method is proposed based on local computations and on the calculation of the roots of a fourth-order polynomial for which a closed-form solution is known. Computational tests conducted on both 14-bus and 84-bus distribution networks demonstrate the effectiveness of the proposed method in obtaining the same quality of solutions compared with that by a centralized solver. The proposed method is scalable and has features that can be implemented on microcontrollers since both LP and CP procedures require only simple matrix-vector multiplications.
To solve the problems of SVM in dealing with large sample size and asymmetric distributed samples, a support vector classification algorithm based on variable parameter linear programming is proposed. In the proposed ...
详细信息
To solve the problems of SVM in dealing with large sample size and asymmetric distributed samples, a support vector classification algorithm based on variable parameter linear programming is proposed. In the proposed algorithm, linear programming is employed to solve the optimization problem of classification to decrease the computation time and to reduce its complexity when compared with the original model. The adjusted punishment parameter greatly reduced the classification error resulting from asymmetric distributed samples and the detailed procedure of the proposed algorithm is given. An experiment is conducted to verify whether the proposed algorithm is suitable for asymmetric distributed samples.
The approximate maximum and minimum amounts ofany phase in a complex mineral mixture can be determined by solving a linear programming problem involvingchemical mass balance and X-ray powder diffraction (XRD) data. Th...
详细信息
The approximate maximum and minimum amounts ofany phase in a complex mineral mixture can be determined by solving a linear programming problem involvingchemical mass balance and X-ray powder diffraction (XRD) data. The chemicalinformation necessary is the bulk composition ofthe mixture and an estimation of the compositional range of each of the minerals in the mixture. Stoichiometric constraints for the minerals may be used to reduce their compositional variation. Ifonly a partial chemical analysis for the mixture is available, the maximum amounts of the phases may still be estimated; however, some or all of the stoichiometric constraints may not apply. XRD measurements (scaled using an internal standard) may be incorporated into the linear programming problem using concentration-intensity re- lations between pairs of minerals. Each XRD constraint added to the linear programming problem, in general, reduces the difference between the calculated maximum and minimum amounts of each phase. Because it is necessary to define weights in the objective function of the linear programming problem, the proposed method must be considered a model. For many mixtures, however, the solution is relatively insensitive to the objective function weights. An example consisting of a mixture of montmorillonite, plagioclase feldspar, quartz, and opal-cristo- balite illustrates the linear programming approach. Chemical information alone was used to estimate the mineral abundances. Because quartz and opal-cristobalite are not chemicallydistinct, it was only possible to determine the sum, quartz + opal-cristobalite, present in the mixture.
暂无评论