Stochastic semidefinite programming: a new paradigm for stochastic optimization

Semidefinite programs are a class of optimization problems that have been studied extensively during the past 15 years. Semidefinite programs are naturally related to linear programs, and both are defined using deterministic data. Stochastic programs were introduced in the 1950s as a paradigm for dealing with uncertainty in data defining linear programs. In this paper, we introduce stochastic semidefinite programs as a paradigm for dealing with uncertainty in data defining semidefinite programs.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465. The material in this paper is part of the doctoral dissertation of this author in preparation at Washington State University.     

One State's Self-Study of Initial Certification Programs in Science and Mathematics

Creating standards-based teacher education programs for mathematics and science teachers continues to be on the forefront of discussion in US colleges and universities. Yet prior to reforming teacher education programs, self-studies should be conducted to evaluate the status of such programs. This article describes how mathematics and science education specialists in Arizona examined their programs to determine avenues for reform. Both qualitative and quantitative research methods were employed to explore five areas pertaining to initial certification programs in mathematics and science. Mission statements, the composition of initial certification programs, and curriculum, instruction, and assessment practices of faculty were examined. In addition, profiles were created pertaining to faculty, staff, and students who participate in the programs. From this self-study, it became evident that various components of initial certification programs in Arizona may not be consistent with the national reforms in mathematics, science, and teacher education. This paper provides an overview of the self-study and findings and reflects upon the process of self-study.     

A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs

Ariyawansa and Zhu have recently introduced (two-stage) stochastic semidefinite programs (with recourse) (SSDPs) [1] and chance-constrained semidefinite programs (CCSDPs) [2] as paradigms for dealing with uncertainty in applications leading to semidefinite programs. Semidefinite programs have been the subject of intense research during the past 15 years, and one of the reasons for this research activity is the novelty and variety of applications of semidefinite programs. This research activity has produced, among other things, efficient interior point algorithms for semidefinite programs. Semidefinite programs however are defined using deterministic data while uncertainty is naturally present in applications. The definitions of SSDPs and CCSDPs in [1] and [2] were formulated with the expectation that they would enhance optimization modeling in applications that lead to semidefinite programs by providing ways to handle uncertainty in data. In this paper, we present results of our attempts to create SSDP and CCSDP models in four such applications. Our results are promising and we hope that the applications presented in this paper would encourage researchers to consider SSDP and CCSDP as new paradigms for stochastic optimization when they formulate optimization models.     

On the transformation of lexicographic nonlinear multiobjective programs to single objective programs

This paper deals with multiobjective optimization programs in which the objective functions are ordered by their degree of priority. A number of approaches have been proposed (and several implemented) for the solution of lexicographic (preemptive priority) multiobjective optimization programs. These approaches may be divided into two classes. The first encompasses the development of algorithms specifically designed to deal directly with the initial model. Considered only for linear multiobjective programs and multiobjective programs with a finite discrete feasible region, the second one attempts to transform, efficiently, the lexicographic multiobjective model into an equvivalent model, i.e. a single objective programming problem. In this paper, we deal with the second approach for lexicographic nonlinear multiobjective programs.     

Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality

In this paper we show that a convexifiability property of nonconvex quadratic programs with nonnegative variables and quadratic constraints guarantees zero duality gap between the quadratic programs and their semi-Lagrangian duals. More importantly, we establish that this convexifiability is hidden in classes of nonnegative homogeneous quadratic programs and discrete quadratic programs, such as mixed integer quadratic programs, revealing zero duality gaps. As an application, we prove that robust counterparts of uncertain mixed integer quadratic programs with objective data uncertainty enjoy zero duality gaps under suitable conditions. Various sufficient conditions for convexifiability are also given.     

Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling

We consider the solution of nonlinear programs with nonlinear semidefiniteness constraints. The need for an efficient exploitation of the cone of positive semidefinite matrices makes the solution of such nonlinear semidefinite programs more complicated than the solution of standard nonlinear programs. This paper studies a sequential semidefinite programming (SSP) method, which is a generalization of the well-known sequential quadratic programming method for standard nonlinear programs. We present a sensitivity result for nonlinear semidefinite programs, and then based on this result, we give a self-contained proof of local quadratic convergence of the SSP method. We also describe a class of nonlinear semidefinite programs that arise in passive reduced-order modeling, and we report results of some numerical experiments with the SSP method applied to problems in that class.     

New strong duality results for convex programs with separable constraints

It is known that convex programming problems with separable inequality constraints do not have duality gaps. However, strong duality may fail for these programs because the dual programs may not attain their maximum. In this paper, we establish conditions characterizing strong duality for convex programs with separable constraints. We also obtain a sub-differential formula characterizing strong duality for convex programs with separable constraints whenever the primal problems attain their minimum. Examples are given to illustrate our results.     

A computational study of methods for solving polynomial geometric programs

A computational comparison of several methods for dealing with polynomial geometric programs is presented. Specifically, we compare the complementary programs of Avriel and Williams (Ref. 1) with the reversed programs and the harmonic programs of Duffin and Peterson (Refs. 2, 3). These methods are used to generate a sequence of posynomial geometric programs which are solved using a dual algorithm.The authors would like to acknowledge the helpful comments of the referees. Also, they would like to acknowledge the programming assistance of Mr. S. N. Wong of The Pennsylvania State University. The first author's research was supported in part by a Research Initiation Grant awarded through The Pennsylvania State University.     

The Impact of Participation in an Ancillary Science and Mathematics Program (SEMAA) on Engagement Rates of Middle School Students in Regular Mathematics Classrooms

The purpose of this study was to investigate the impact of participation in a federally sponsored, short‐term, cocurricular, mathematics and science program (Science Engineering Mathematics Aerospace Academy, SEMAA) on the engagement rates of sixth‐ and seventh‐grade students in public school mathematics classes. Engagement was measured with the Student Record of Behavior at three time intervals. Results of a 22.3 ANOVA investigating three main effects (participation, level of access to technology, and time) and their primary and secondary interactions reflected no discernable impact of the SEMAA program on student engagement rates. Ancillary programs designed to compensate for deficiencies in daily instructional programs may represent engagement opportunities vastly different from the daily instructional programs they support. Consequently, ancillary programs may not impact engagement in regular classrooms and subsequently improve achievement outcomes, especially when implemented in low‐performing schools and high‐stakes accountability settings. Recommendations include alignment of ancillary programs with the daily instructional programs they support and with ongoing professional development activities and that further study include broadened samples, settings, and variables.     

Homogeneous Self-dual Algorithms for Stochastic Semidefinite Programming

Ariyawansa and Zhu have proposed a new class of optimization problems termed stochastic semidefinite programs to handle data uncertainty in applications leading to (deterministic) semidefinite programs. For stochastic semidefinite programs with finite event space, they have also derived a class of volumetric barrier decomposition algorithms, and proved polynomial complexity of certain members of the class. In this paper, we consider homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space. We show how the structure in such problems may be exploited so that the algorithms developed in this paper have complexity similar to those of the decomposition algorithms mentioned above.     

Stochastic second-order cone programming: Applications models

Second-order cone programs are a class of convex optimization problems. We refer to them as deterministic second-order cone programs (DSCOPs) since data defining them are deterministic. In DSOCPs we minimize a linear objective function over the intersection of an affine set and a product of second-order (Lorentz) cones. Stochastic programs have been studied since 1950s as a tool for handling uncertainty in data defining classes of optimization problems such as linear and quadratic programs. Stochastic second-order cone programs (SSOCPs) with recourse is a class of optimization problems that defined to handle uncertainty in data defining DSOCPs. In this paper we describe four application models leading to SSOCPs.     

Nonlinear Lagrangian Functions and Applications to Semi-Infinite Programs

In this paper a nonlinear penalty method via a nonlinear Lagrangian function is introduced for semi-infinite programs. A convergence result is established which shows that the sequence of optimal values of nonlinear penalty problems converges to that of semi-infinite programs. Moreover a conceptual convergence result of a discretization method with an adaptive scheme for solving semi-infinite programs is established. Preliminary numerical experiments show that better optimal values for some nonlinear semi-infinite programs can be obtained using the nonlinear penalty method.     

Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

Solving multistage stochastic network programs on massively parallel computers

Multi-stage stochastic programs are typically extremely large, and can be prohibitively expensive to solve on the computer. In this paper we develop an algorithm for multistage programs that integrates the primal-dual row-action framework with proximal minimization. The algorithm exploits the structure of stochastic programs with network recourse, using a suitable problem formulation based on split variables, to decompose the solution into a large number of simple operations. It is therefore possible to use massively parallel computers to solve large instances of these problems. The algorithm is implemented on a Connection Machine CM-2 with up to 32K processors. We solve stochastic programs from an application from the insurance industry, as well as random problems, with up to 9 stages, and with up to 16392 scenarios, where the deterministic equivalent programs have a half million constraints and 1.3 million variables. Research partially supported by NSF grants CCR-9104042 and SES-91-00216, and AFOSR grant 91-0168. Computing resources were made available by AHPCRC at the University of Minnesota, and by NPAC at Syracuse University, New York.     

On-line program debugging

This paper describes a system which allows programmers to construct and debug assembly language programs in an on-line conversational manner, using a graphic display with light pen and keyboard. The amount of programs necessary to realize these functions is about 8000 machine instructions. The expected gain with this system is that it can reduce by a factor of between two and four the time required to prepare, write and debug new programs.     

On duality in stochastic programming with recourse

This short paper compares dual programs of stochastic programs with recourse. It explains why the discrepancy exists between two such dual programs recently appearing in the literature. An example is presented which illustrates the difference.     

Sequential convexification in reverse convex and disjunctive programming

This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas (1974, 1979) to hold for facial disjunctive programs. Sequential convexifiability means that the convex hull of a nonconvex set defined by a collection of constraints can be generated by imposing the constraints one by one, sequentially, and generating each time the convex hull of the resulting set. Here we extend the class of problems considered to disjunctive programs with infinitely many terms, also known as reverse convex programs, and give necessary and sufficient conditions for the solution sets of such problems to be sequentially convexifiable. We point out important classes of problems in addition to facial disjunctive programs (for instance, reverse convex programs with equations only) for which the conditions are always satisfied. Finally, we give examples of disjunctive programs for which the conditions are violated, and so the procedure breaks down.The research underlying this report was supported by Grant ECS-8601660 of The National Science Foundation and Contract N00014-85-K-0198 with the Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.On leave from the University of Aarhus, Denmark.     

Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming

We introduce and study two-stage stochastic symmetric programs with recourse to handle uncertainty in data defining (deterministic) symmetric programs in which a linear function is minimized over the intersection of an affine set and a symmetric cone. We present a Benders’ decomposition-based interior point algorithm for solving these problems and prove its polynomial complexity. Our convergence analysis proved by showing that the log barrier associated with the recourse function of stochastic symmetric programs behaves a strongly self-concordant barrier and forms a self-concordant family on the first stage solutions. Since our analysis applies to all symmetric cones, this algorithm extends Zhao’s results [G. Zhao, A log barrier method with Benders’ decomposition for solving two-stage stochastic linear programs, Math. Program. Ser. A 90 (2001) 507–536] for two-stage stochastic linear programs, and Mehrotra and Özevin’s results [S. Mehrotra, M.G. Özevin, Decomposition-based interior point methods for two-stage stochastic semidefinite programming, SIAM J. Optim. 18 (1) (2007) 206–222] for two-stage stochastic semidefinite programs.     

Spectral bundle methods for non-convex maximum eigenvalue functions: first-order methods

Many challenging problems in automatic control may be cast as optimization programs subject to matrix inequality constraints. Here we investigate an approach which converts such problems into non-convex eigenvalue optimization programs and makes them amenable to non-smooth analysis techniques like bundle or cutting plane methods. We prove global convergence of a first-order bundle method for programs with non-convex maximum eigenvalue functions. Dedicated to R. T. Rockafellar on the occasion of his 70th anniversary     

Goal network programs: A specialized algorithm and an application

This paper presents a specialized network procedure for the solution of pure goal network programs with preemptive priorities. The specialization solves such goal network programs efficiently since it requires a modification only in the pricing rule of the network simplex algorithm. The algorithm is used to solve multiple goal network programs that arise in the assignment of naval personnel to jobs. Computational experience indicates that the specialization dominates the sequential linear goal programming procedure.