Selin Damla Ahipaşaoğlu

In this work, we address the exact D-optimal experimental design problem when the number of design vectors is large. First, we propose a customized column generation algorithm to solve the continuous relaxation of the problem. In the approach, each restricted master problem is constructed carefully so that the number of variables stays small and therefore the subproblem can be solved efficiently by a Primal-Dual Interior-Point-based Semidefinite Programming solver. The support of this solution provides a subset of design points to be used in a local search algorithm for the solution of the integer problem. We prove that a local search algorithm restricted to points of this subset provides an exact design that is provably close to the exact D-optimal design. Our numerical experiments show that, for large-scale instances in which the number of regression points exceeds by far the number of experiments, our approach achieves superior performance compared to existing branch-and-bound-based algorithms in both computational efficiency and solution quality.

We extend the classical mean-variance (MV) framework and propose a robust and sparse portfolio selection model incorporating an ellipsoidal uncertainty set to reduce the impact of estimation errors and fixed transaction costs to penalize over-diversification. In the literature, the MV model under fixed transaction costs is referred to as the sparse or cardinality-constrained MV optimization, which is a mixed integer problem and is challenging to solve when the number of assets is large. We develop an efficient semismooth Newton-based proximal difference-of-convex algorithm to solve the proposed model and prove its convergence to at least a local minimizer with a locally linear convergence rate. We explore properties of the robust and sparse portfolio both analytically and numerically. In particular, we show that the MV optimization is indeed a robust procedure as long as an investor makes the proper choice on the risk-aversion coefficient. We contribute to the literature by proving that there is a one-to-one correspondence between the risk-aversion coefficient and the level of robustness. Moreover, we characterize how the number of traded assets changes with respect to the interaction between the level of uncertainty on model parameters and the magnitude of transaction cost.

Given a multivariate data set, sparse principal component analysis (SPCA) aims to extract several linear combinations of the variables that together explain the variance in the data as much as possible, while controlling the number of nonzero loadings in these combinations. In this paper we consider 8 different optimization formulations for computing a single sparse loading vector; these are obtained by combining the following factors: we employ two norms for measuring variance (L2, L1) and two sparsity-inducing norms (L0, L1), which are used in two different ways (constraint, penalty). Three of our formulations, notably the one with L0 constraint and L1 variance, have not been considered in the literature. We give a unifying reformulation which we propose to solve via a natural alternating maximization (AM) method. We show the the AM method is nontrivially equivalent to GPower (Journ\'{e}e et al; JMLR 11:517--553, 2010) for all our formulations. Besides this, we provide 24 efficient parallel SPCA implementations: 3 codes (multi-core, GPU and cluster) for each of the 8 problems. Parallelism in the methods is aimed at i) speeding up computations (our GPU code can be 100 times faster than an efficient serial code written in C++), ii) obtaining solutions explaining more variance and iii) dealing with big data problems (our cluster code is able to solve a 357 GB problem in about a minute).

In a Markovian traffic equilibrium model, users move toward their destinations by a sequence of successive link choices using a discrete choice model at each node, taking congestion into account. Although a convex optimization formulation is available to compute the equilibrium flows for a continuous distribution of link utilities, practical applications have thus far been mainly restricted to the multinomial logit model and its variants. In this paper, we relax the assumption of a complete joint distribution of link utilities to only knowledge on the marginal distributions and propose a new convex optimization formulation for a distributionally robust Markovian traffic equilibrium. The formulation is provably efficiently solvable and has the flexibility of allowing for general marginal distributions, thus capturing different types of nonidentical, skewed, and heavy-tailed distributions at the link level.

We analyze and solve a single-period portfolio optimization problem with non-convex constraints, which address practical concerns of investment such as the active share weights of sectors and the number of stocks held in a portfolio. We reformulate the problem to simplify the computation and propose an inexact l₂-norm penalty method to solve the problem.

Crashing is shortening the project makespan by reducing activity times in a project network by allocating resources to them. Activity durations are often uncertain and an exact probability distribution itself might be ambiguous. We study a class of distributionally robust project crashing problems where the objective is to optimize the first two marginal moments (means and SDs) of the activity durations to minimize the worst‐case expected makespan. Under partial correlation information and no correlation information, the problem is solvable in polynomial time as a semidefinite program and a second‐order cone program, respectively. However, solving semidefinite programs is challenging for large project networks. We exploit the structure of the distributionally robust formulation to reformulate a convex‐concave saddle point problem over the first two marginal moment variables and the arc criticality index variables. We then use a projection and contraction algorithm for monotone variational inequalities in conjunction with a gradient method to solve the saddle point problem enabling us to tackle large instances. Numerical results indicate that a manager who is faced with ambiguity in the distribution of activity durations has a greater incentive to invest resources in decreasing the variations rather than the means of the activity durations.

A popular discrete choice model that incorporates correlation information is the Multinomial Probit (MNP) model where the random utilities of the alternatives are chosen from a multivariate normal distribution. Computing the choice probabilities is challenging in the MNP model when the number of alternatives is large. Mishra, Natarajan and Teo (IEEE TAC, 2012) have proposed a semidefinite optimization approach to compute choice probabilities for the distribution of the random utilities that maximizes expected agent utility given only the mean, variance and covariance information. Their model is referred to as the Cross Moment (CMM) model. Computing the choice probabilities with many alternatives is challenging in the CMM model since one needs to solve large scale semidefinite programs. We develop a simpler formulation as a representative agent model by maximizing over the choice probabilities in the unit simplex where the objective function is the sum of the expected utilities and a strongly concave perturbation function. By characterizing the perturbation function for the CMM model and its gradient, we develop a simple first order gradient method with inexact line