Stochastic Approximation Algorithms for Constrained Optimization via Simulation

We develop four algorithms for simulation-based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian, while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique, while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving an open Jackson network. The Newton-based SF algorithm is seen to show the best overall performance.

An actor-critic algorithm with function approximation for discounted cost constrained Markov decision processes

We develop in this article the first actor-critic reinforcement learning algorithm with function approximation for a problem of control under multiple inequality constraints. We consider the infinite horizon discounted cost framework in which both the objective and the constraint functions are suitable expected policy-dependent discounted sums of certain sample path functions. We apply the Lagrange multiplier method to handle the inequality constraints. Our algorithm makes use of multi-timescale stochastic approximation and incorporates a temporal difference (TD) critic and an actor that makes a gradient search in the space of policy parameters using efficient simultaneous perturbation stochastic approximation (SPSA) gradient estimates. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal policy. (C) 2010 Elsevier B.V. All rights reserved.

Proposed role of w chromosome inactivation and the absence of dosage compensation in avian sex determination

Three features of avian sex chromosomes - female heterogamety (ZZ male, ZW female), the apparently inactive state of the W chromosome, and dose-dependent expression of Z-linked genes - are examined in regard to their possible relation to sex determination. It is proposed that the W chromosome is facultatively heterochromatic and that the Z and W chromosomes carry one or more homologous sex-determination genes. The absence of dosage compensation in ZZ embryos, and W inactivation in ZW embryos, would then bring about a 2n(ZZ)-n(ZW) inequality in the effective copy number of such genes. The absence of dosage compensation of Z-linked genes in ZZ embryos is viewed as a means by which two copies of Z-W homologous sex determination genes are kept active to meet the requirements of testis determination. W inactivation may promote ovarian development by reducing the effective copy number of these genes from 2n to n. If there is a W-specific gene for femaleness, spread of heterochromatization to this gene in cells forming the right gonadal primordium may explain the latter's normally undifferentiated state; reversal of heterochromatization may similarly explain the development of the right gonad into a testis following left ovariectomy.

On Walkup's class K (d) and a minimal triangulation of (S-3 (sic) S-1)(#3)

For d >= 2, Walkup's class K (d) consists of the d-dimensional simplicial complexes all whose vertex-links are stacked (d - 1)-spheres. Kalai showed that for d >= 4, all connected members of K (d) are obtained from stacked d-spheres by finitely many elementary handle additions. According to a result of Walkup, the face vector of any triangulated 4-manifold X with Euler characteristic chi satisfies f(1) >= 5f(0) - 15/2 chi, with equality only for X is an element of K(4). Kuhnel observed that this implies f(0)(f(0) - 11) >= -15 chi, with equality only for 2-neighborly members of K(4). Kuhnel also asked if there is a triangulated 4-manifold with f(0) = 15, chi = -4 (attaining equality in his lower bound). In this paper, guided by Kalai's theorem, we show that indeed there is such a triangulation. It triangulates the connected sum of three copies of the twisted sphere product S-3 (sic) S-1. Because of Kuhnel's inequality, the given triangulation of this manifold is a vertex-minimal triangulation. By a recent result of Effenberger, the triangulation constructed here is tight. Apart from the neighborly 2-manifolds and the infinite family of (2d + 3)-vertex sphere products Sd-1 X S-1 (twisted for d odd), only fourteen tight triangulated manifolds were known so far. The present construction yields a new member of this sporadic family. We also present a self-contained proof of Kalai's result. (C) 2011 Elsevier B.V. All rights reserved.

Relation between integral and partial properties of ternary solutions along different composition trajectories

The relations between partial and integral properties of ternary solutions along composition trajectories suggested by Kohler, Colinet and Jacob, and along an arbitrary path are derived. The chemical potentials of the components are related to the slope of integral free energy by expressions involving the binary compositions generated by the intersections of the composition trajectory with the sides of the ternary triangle. Only along the Kohler composition trajectory it is possible to derive the integral free energy from the variation of the chemical potential of a single component with composition or vice versa. Along all other paths the differential of the integral free energy is related to two chemical potentials. The Gibbs-Duhem integration proposed by Darken for the ternary system uses the Kohler isogram. The relative merits of different limits for integration are discussed.

Solving linear programming problems exactly

A linear programming problem in an inequality form having a bounded solution is solved error-free using an algorithm that sorts the inequalities, removes the redundant ones, and uses the p-adic arithmetic. (C) Elsevier Science Inc., 1997

Space vector pulsewidth modulation — A status review

The technique of space vector pulsewidth modulation (SVM) is reviewed. The basic principle of SVM is derived and is compared with sine-triangle PWM. Operation in the overmodulation range is explained. Extension of SVM to other inverter-motor combinations such as three level inverters and split phase motors are discussed.

Thermodynamic constraints along isograms in ternary systems: application to three-phase equilibria

Thermodynamic constraints on component chemical potentials in three-phase fields introduced by the various isograms suggested in the literature are derived for a ternary system containing compounds. When compositions of two compounds lie on an isogram, it is associated with specific characteristics which can be used to obtain further understanding of the interplay of thermodynamic factors that determine phase equilibria. When two compounds are shared by adjacent three-phase fields, the constraints are dictated by binary compositions generated by the intersection of a line passing through the shared compounds with the sides of the ternary triangle. Generalized expressions for an arbitrary line through the triangle are presented. These are consistent with special relations obtained along Kohler, Colinet and Jacob isograms. Five axioms are introduced and proved. They provide valuable tools for checking consistency of thermodynamic measurements and for deriving thermodynamic properties from phase diagrams. (C) 1997 Elsevier Science S.A.

Robust Formulations for Handling Uncertainty in Kernel Matrices

We study the problem of uncertainty in the entries of the Kernel matrix, arising in SVM formulation. Using Chance Constraint Programming and a novel large deviation inequality we derive a formulation which is robust to such noise. The resulting formulation applies when the noise is Gaussian, or has finite support. The formulation in general is non-convex, but in several cases of interest it reduces to a convex program. The problem of uncertainty in kernel matrix is motivated from the real world problem of classifying proteins when the structures are provided with some uncertainty. The formulation derived here naturally incorporates such uncertainty in a principled manner leading to significant improvements over the state of the art. 1.

Incremental-angle and angular velocity estimation using a star sensor

A method is described for estimating the incremental angle and angular velocity of a spacecraft using integrated rate parameters with the help of a star sensor alone. The chief advantage of this method is that the measured stars need not be identified, whereas the identification of the stars is necessary in earlier methods. This proposed estimation can be carried out with all of the available measurements by a simple linear Kalman filter, albeit with a time-varying sensitivity matrix. The residuals of estimated angular velocity by the proposed spacecraft incremental-angle and angular velocity estimation method are as accurate as the earlier methods. This method also enables the spacecraft attitude to be reconstructed for mapping the stars into an imaginary unit sphere in the body reference frame, which will preserve the true angular separation of the stars. This will pave the way for identification of the stars using any angular separation or triangle matching techniques applied to even a narrow field of view sensor that is made to sweep the sky. A numerical simulation for inertial as well as Earth pointing spacecraft is carried out to establish the results.

Precoder Designs for MIMO Broadcast Channels with Imperfect CSI

[1] D. Tse and P. Viswanath, Fundamentals of Wireless Communication.Cambridge University Press, 2006. [2] H. Bolcskei, D. Gesbert, C. B. Papadias, and A.-J. van der Veen, Spacetime Wireless Systems: From Array Processing to MIMO Communications.Cambridge University Press, 2006. [3] Q. H. Spencer, C. B. Peel, A. L. Swindlehurst, and M. Haardt, “An introduction to the multiuser MIMO downlink,” IEEE Commun. Mag.,vol. 42, pp. 60–67, Oct. 2004. [4] K. Kusume, M. Joham,W. Utschick, and G. Bauch, “Efficient tomlinsonharashima precoding for spatial multiplexing on flat MIMO channel,”in Proc. IEEE ICC’2005, May 2005, pp. 2021–2025. [5] R. Fischer, C. Windpassinger, A. Lampe, and J. Huber, “MIMO precoding for decentralized receivers,” in Proc. IEEE ISIT’2002, 2002, p.496. [6] M. Schubert and H. Boche, “Iterative multiuser uplink and downlink beamforming under SINR constraints,” IEEE Trans. Signal Process.,vol. 53, pp. 2324–2334, Jul. 2005. [7] ——, “Solution of multiuser downlink beamforming problem with individual SINR constraints,” IEEE Trans. Veh. Technol., vol. 53, pp.18–28, Jan. 2004. [8] A. Wiesel, Y. C. Eldar, and Shamai, “Linear precoder via conic optimization for fixed MIMO receivers,” IEEE Trans. Signal Process., vol. 52,pp. 161–176, Jan. 2006. [9] N. Jindal, “MIMO broadcast channels with finite rate feed-back,” in Proc. IEEE GLOBECOM’2005, Nov. 2005. [10] R. Hunger, F. Dietrich, M. Joham, and W. Utschick, “Robust transmit zero-forcing filters,” in Proc. ITG Workshop on Smart Antennas, Munich,Mar. 2004, pp. 130–137. [11] M. B. Shenouda and T. N. Davidson, “Linear matrix inequality formulations of robust QoS precoding for broadcast channels,” in Proc.CCECE’2007, Apr. 2007, pp. 324–328. [12] M. Payaro, A. Pascual-Iserte, and M. A. Lagunas, “Robust power allocation designs for multiuser and multiantenna downlink communication systems through convex optimization,” IEEE J. Sel. Areas Commun.,vol. 25, pp. 1392–1401, Sep. 2007. [13] M. Biguesh, S. Shahbazpanahi, and A. B. Gershman, “Robust downlink power control in wireless cellular systems,” EURASIP Jl. Wireless Commun. Networking, vol. 2, pp. 261–272, 2004. [14] B. Bandemer, M. Haardt, and S. Visuri, “Liner MMSE multi-user MIMO downlink precoding for users with multple antennas,” in Proc.PIMRC’06, Sep. 2006, pp. 1–5. [15] J. Zhang, Y. Wu, S. Zhou, and J. Wang, “Joint linear transmitter and receiver design for the downlink of multiuser MIMO systems,” IEEE Commun. Lett., vol. 9, pp. 991–993, Nov. 2005. [16] S. Shi, M. Schubert, and H. Boche, “Downlink MMSE transceiver optimization for multiuser MIMO systems: Duality and sum-mse minimization,”IEEE Trans. Signal Process., vol. 55, pp. 5436–5446, Nov.2007. [17] A. Mezghani, M. Joham, R. Hunger, and W. Utschick, “Transceiver design for multi-user MIMO systems,” in Proc. WSA 2006, Mar. 2006. [18] R. Doostnejad, T. J. Lim, and E. Sousa, “Joint precoding and beamforming design for the downlink in a multiuser MIMO system,” in Proc.WiMob’2005, Aug. 2005, pp. 153–159. [19] N. Vucic, H. Boche, and S. Shi, “Robust transceiver optimization in downlink multiuser MIMO systems with channel uncertainty,” in Proc.IEEE ICC’2008, Beijing, China, May 2008. [20] A. Ben-Tal and A. Nemirovsky, “Selected topics in robust optimization,”Math. Program., vol. 112, pp. 125–158, Feb. 2007. [21] D. Bertsimas and M. Sim, “Tractable approximations to robust conic optimization problems,” Math. Program., vol. 107, pp. 5–36, Jun. 2006. [22] P. Ubaidulla and A. Chockalingam, “Robust Transceiver Design for Multiuser MIMO Downlink,” in Proc. IEEE Globecom’2008, New Orleans, USA, Dec. 2008, to appear. [23] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004. [24] G. H. Golub and C. F. V. Loan, Matrix Computations. The John Hopkins University Press, 1996.

Flux Partitioning of Species Approach in Binary Interdiffusion Process

Validation of the flux partitioning of species model has been illustrated. Various combinations of inequality expression for the fluxes of species A and B in two successively grown hypothetical intermetallic phases in the interdiffusion zone have been considered within the constraints of this concept. Furthermore, ratio of intrinsic diffusivities of the species A and B in those two phases has been correlated in four different cases. Moreover, complete and or partial validation or invalidation of this model with respect to both the species, has been proven theoretically and also discussed with the Co-Si system as an example.

Clustering Based Large Margin Classification: A Scalable Approach using SOCP Formulation

This paper presents a novel Second Order Cone Programming (SOCP) formulation for large scale binary classification tasks. Assuming that the class conditional densities are mixture distributions, where each component of the mixture has a spherical covariance, the second order statistics of the components can be estimated efficiently using clustering algorithms like BIRCH. For each cluster, the second order moments are used to derive a second order cone constraint via a Chebyshev-Cantelli inequality. This constraint ensures that any data point in the cluster is classified correctly with a high probability. This leads to a large margin SOCP formulation whose size depends on the number of clusters rather than the number of training data points. Hence, the proposed formulation scales well for large datasets when compared to the state-of-the-art classifiers, Support Vector Machines (SVMs). Experiments on real world and synthetic datasets show that the proposed algorithm outperforms SVM solvers in terms of training time and achieves similar accuracies.

Minimization of Constraint Violation in Fuzzy Multiobjective Programming

Fuzzy multiobjective programming for a deterministic case involves maximizing the minimum goal satisfaction level among conflicting goals of different stakeholders using Max-min approach. Uncertainty due to randomness in a fuzzy multiobjective programming may be addressed by modifying the constraints using probabilistic inequality (e.g., Chebyshev’s inequality) or by addition of new constraints using statistical moments (e.g., skewness). Such modifications may result in the reduction of the optimal value of the system performance. In the present study, a methodology is developed to allow some violation in the newly added and modified constraints, and then minimizing the violation of those constraints with the objective of maximizing the minimum goal satisfaction level. Fuzzy goal programming is used to solve the multiobjective model. The proposed methodology is demonstrated with an application in the field of Waste Load Allocation (WLA) in a river system.

Phase Equilibria in the System Al2O3-CaO-CoO and Gibbs Energy of Formation of Ca3CoAl4O10

An isothermal section of the system Al2O3-CaO-CoO at 1500 K has been established by equilibrating 22 samples of different compositions at high temperature and phase identification by optical and scanning electron microscopy, X-ray diffraction, and energy dispersive spectroscopy after quenching to room temperature. Only one quaternary oxide, Ca3CoAl4O10, was identified inside the ternary triangle. Based on the phase relations, a solid-state electrochemical cell was designed to measure the Gibbs energy of formation of Ca3CoAl4O10 in the temperature range from 1150 to 1500 K. Calcia-stabilized zirconia was used as the solid electrolyte and a mixture of Co + CoO as the reference electrode. The cell can be represented as: ( - )\textPt,\textCaAl 2 \textO 4 + \textCa 1 2 \textAl 1 4 \textO 3 3 + \textCa 3 \textCoAl 4 \textO 10 + \textCo//(CaO)ZrO 2 \text// \textCoO + \textCo,\text Pt ( + ). (−)PtCaAl2O4+Ca12Al14O33+Ca3CoAl4O10+Co//(CaO)ZrO2//CoO+Co Pt (+) From the emf of the cell, the standard Gibbs energy change for the Ca3CoAl4O10 formation reaction, CoO + 3/5CaAl2O4 + 1/5Ca12Al14O33 → Ca3CoAl4O10, is obtained as a function of temperature: \Updelta Gr\texto Unknown control sequence '\Updelta'/J mol−1 (±50) = −2673 + 0.289 (T/K). The standard Gibbs energy of formation of Ca3CoAl4O10 from its component binary oxides, Al2O3, CaO, and CoO is derived as a function of temperature. The standard entropy and enthalpy of formation of Ca3CoAl4O10 at 298.15 K are evaluated. Chemical potential diagrams for the system Al2O3-CaO-CoO at 1500 K are presented based on the results of this study and auxiliary information from the literature.