A bilinear algorithm for sparse representations

We consider the following sparse representation problem: represent a given matrix X∈ℝ ^m×N as a multiplication X=AS of two matrices A∈ℝ ^m×n (m≤n<N) and S∈ℝ ^n×N , under requirements that all m×m submatrices of A are nonsingular, and S is sparse in sense that each column of S has at least n−m+1 zero elements. It is known that under some mild additional assumptions, such representation is unique, up to scaling and permutation of the rows of S. We show that finding A (which is the most difficult part of such representation) can be reduced to a hyperplane clustering problem. We present a bilinear algorithm for such clustering, which is robust to outliers. A computer simulation example is presented showing the robustness of our algorithm.     

Convergence analysis of a global optimization algorithm using stochastic differential equations

We establish the convergence of a stochastic global optimization algorithm for general non-convex, smooth functions. The algorithm follows the trajectory of an appropriately defined stochastic differential equation (SDE). In order to achieve feasibility of the trajectory we introduce information from the Lagrange multipliers into the SDE. The analysis is performed in two steps. We first give a characterization of a probability measure (Π) that is defined on the set of global minima of the problem. We then study the transition density associated with the augmented diffusion process and show that its weak limit is given by Π.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

A combinatorial algorithm for the TDMA message scheduling problem

In this paper, we introduce a combinatorial algorithm for the message scheduling problem on Time Division Multiple Access (TDMA) networks. In TDMA networks, time is divided in to slots in which messages are scheduled. The frame length is defined as the total number of slots required for all stations to broadcast without message collisions. The objective is to provide a broadcast schedule of minimum frame length which also provides the maximum throughput. This problem is known to be -hard, thus efficient heuristics are needed to provide solutions to real-world instances. We present a two-phase algorithm which exploits the combinatorial structure of the problem in order to provide high quality solutions. The first phase finds a feasible frame length in which the throughput is maximized in phase two. Computational results are provided and compared with other heuristics in the literature as well as to the optimal solutions found using a commercial integer programming solver. Experiments on 63 benchmark instances show that the proposed method is able to provide optimal frame lengths for all cases with near optimal throughput.     

Bilinear modeling solution approach for fixed charge network flow problems

We present a continuous, bilinear formulation for the fixed charge network flow problem. This formulation is used to derive an exact algorithm for the fixed charge network flow problem converging in a finite number of steps. Some preliminary computational experiments are reported to show the performance of the algorithm.     

Fundamental equation of the dual flow rate-solvent gradient elution in liquid chromatography

An alternative expression of the fundamental equation of multi-mode gradient elution involving simultaneous changes in mobile phase composition and flow rate is derived using simple kinetic arguments and graphic interpretation. The new expression consists of a system of two integral equations and provides an easy and direct way of predicting retention times under dual-mode gradient conditions.     

Uptake measurements of acetic acid on ice and nitric acid-doped thin ice films over upper troposphere/lower stratosphere temperatures

The adsorption of gaseous acetic acid (CH(3)C(O)OH) on thin ice films and on ice doped with nitric acid (1.96 and 7.69 wt %) was investigated over upper troposphere and lower stratosphere (UT/LS) temperatures (198-208 K), and at low gas concentrations. Experiments were performed in a Knudsen flow reactor coupled to a quadrupole mass spectrometer. The initial uptake coefficients, γ(0), on thin ice films or HNO(3)-doped ice films were measured at low surface coverage. In all cases, γ(0) showed an inverse temperature dependence, and for pure thin ice films, it was given by the expression γ(0)(T) = (4.73 ± 1.13) × 10(-17) exp[(6496 ± 1798)/T]; the quoted errors are the 2σ precision of the linear fit, and the estimated systematic uncertainties are included in the pre-exponential factor. The inverse temperature dependence suggests that the adsorption process occurs via the formation of an intermediate precursor state. Uptakes were well represented by the Langmuir adsorption model, and the saturation surface coverage, N(max), on pure thin ice films was (2.11 ± 0.16) × 10(14) molecules cm(-2), independent of temperature in the range 198-206 K. Light nitration (1.96 and 7.69 wt %) of ice films resulted in more efficient CH(3)C(O)OH uptakes and larger N(max) values that may be attributed to in-bulk diffusion or change in nature of the gas-ice surface interaction. Finally, it was estimated that the rate of adsorption of acetic acid on high-density cirrus clouds in the UT/LS is fast, and this is reflected in the short atmospheric lifetimes (2-8 min) of acetic acid; however, the extent of this uptake is minor resulting in at most a 5% removal of acetic acid in UT/LS cirrus clouds.     

Optimal persistent disturbance attenuation control for linear hybrid systems

In this paper, the disturbance attenuation properties for a class of linear hybrid systems are investigated, and a hybrid optimal persistent disturbance attenuation control problem is studied. First, a procedure is developed to determine the minimal l^∞$l^{\infty }$ induced gain of linear hybrid systems. However, for general hybrid systems, the termination of the procedure is not guaranteed. Then, the decidability issues are discussed. The termination of the procedure in a finite number of steps is shown for a subclass of hybrid systems with simplified discrete event dynamics, called switched linear systems. Finally, the optimal persistent disturbance attenuation controller synthesis problem is studied. It is shown that the optimal performance level can be achieved by a piecewise linear state feedback control law, and a systematic approach is proposed to design such feedback control.     

An approximate dynamic programming framework for modeling global climate policy under decision-dependent uncertainty

Analyses of global climate policy as a sequential decision under uncertainty have been severely restricted by dimensionality and computational burdens. Therefore, they have limited the number of decision stages, discrete actions, or number and type of uncertainties considered. In particular, two common simplifications are the use of two-stage models to approximate a multi-stage problem and exogenous formulations for inherently endogenous or decision-dependent uncertainties (in which the shock at time t+1 depends on the decision made at time t). In this paper, we present a stochastic dynamic programming formulation of the Dynamic Integrated Model of Climate and the Economy (DICE), and the application of approximate dynamic programming techniques to numerically solve for the optimal policy under uncertain and decision-dependent technological change in a multi-stage setting. We compare numerical results using two alternative value function approximation approaches, one parametric and one non-parametric. We show that increasing the variance of a symmetric mean-preserving uncertainty in abatement costs leads to higher optimal first-stage emission controls, but the effect is negligible when the uncertainty is exogenous. In contrast, the impact of decision-dependent cost uncertainty, a crude approximation of technology R&D, on optimal control is much larger, leading to higher control rates (lower emissions). Further, we demonstrate that the magnitude of this effect grows with the number of decision stages represented, suggesting that for decision-dependent phenomena, the conventional two-stage approximation will lead to an underestimate of the effect of uncertainty.     

Pareto set approximation by the method of adjustable weights and successive lexicographic goal programming

A nonlinear multiobjective optimization problem is considered. Two methods are proposed to generate solutions with an approximately uniform distribution in a Pareto set. The first method is supposed to find the solutions as minimizers of weighted sums of objective functions where the weights are properly selected using a branch and bound type algorithm. The second method is based on lexicographic goal programming. The proposed methods are compared with several metaheuristic methods using two and three-criteria tests and applied problems.