Theses supervised by Prof. Dr. Mustafa Çelebi Pınar
13 theses · İhsan Doğramacı Bilkent University
Ağ gelir yönetimi için sağlamcı optimizasyon modelleri
Effective capacity allocation methods play a crucial role in Network Revenue Management. Yet, current methods for determining optimal capacity controls under uncertainty, such as stochastic optimization, often assume a known probability distribution for unknown parameters. This assumption may degrade a model's performance when faced with unexpected data patterns. This thesis explores a novel approach through robust optimization to address stochastic resource allocation problems. We introduce a heuristic based on these robust formulations to derive actionable results. Through extensive simulations focused on seat allocation problems within the revenue management domain, our proposed formulations demonstrate improved worst-case performances. Notably, even under favorable scenarios, our solutions remain comparable to existing methods in the revenue management literature.
Oyun teorisi ve makine öğrenimi uygulamalarıyla seyreklik kısıtlı minimum-maksimum optimizasyon
Classical game-theoretic methods often yield dense strategies for a player, which might not be practical in real-world implementations. This thesis studies incorporating the sparsity constraint to the minimax optimization problem to compute sparse strategies in bimatrix games. The theory and algorithms also apply to the equivalent problem of computing sparse classifiers in the margin maximizing boosting problem. Optimality conditions in the sparse optimization literature are extended to nonsmooth functions. A new optimality condition for neighborhood search that covers the existing conditions is proposed. Practical greedy algorithms are developed to find candidate points satisfying optimality conditions. Based on the properties of the Minimax function, connections between the cardinality-constrained problem and the cardinality-regularized problem are established. A new concave penalty for cardinality-regularized optimization problems over the unit simplex is proposed, which offers an alternative to the sparsity-promoting penalties in the literature. The resulting problem is solved efficiently using a faster version of the Difference of Convex (DC) algorithm. The proposed algorithms are tested empirically on random game matrices and real data for binary classification. The performance is compared to well-known regularization techniques and the MILP formulation of the problem.
Derin sinir ağları üzerinden eniyileme konuları
We present two studies in the intersection of deep learning and optimization, Deep Portfolio Optimization, and Subset Based Error Recovery. Along with the emergence of deep models in finance, the portfolio optimization trend had shifted towards data-driven models from the classical model-based approaches. However, the deep portfolio models generally suffer from the non-stationary nature of the data and the results obtained are not always very stable. To address this issue, we propose to use Graph Neural Networks (GNN) which allows us to incorporate graphical knowledge to increase the stability of the models in order to improve the results obtained in comparison to the state-of-the-art recurrent architectures. Furthermore, we analyze the algorithmic risk-return trade-off for the deep portfolio optimization models to give insights on risk for the fully data-driven models. We also propose a data denoising method using Extreme Learning Machine (ELM) structure. Furthermore, we show that the method is equivalent to a robust two-layer ELM that implicitly benefits from the proposed denoising algorithm. Current robust ELM methods in the literature involve well-studied L1, L2 regularization techniques as well as the usage of the robust loss functions such as Huber Loss. We extend the recent analysis on the Robust Regression literature to be effectively used in more general, non-linear settings and to be compatible with any ML algorithm such as Neural Networks (NN). These methods are useful under the scenario where the observations suffer from the effect of heavy noise. Tests for denoising and regularized ELM methods are conducted on both synthetic and real data. Our method performs better than its competitors for most of the scenarios, and successfully eliminates most of the noise.
Seyrek kısıtlı temel bileşen analizi için algoritmalar
The classical Principal Component Analysis problem consists of finding a linear transform that reduces the dimensionality of the original dataset while keeping most of the variation. Extra sparsity constraint sets most of the coefficients to zero which makes interpretation of the linear transform easier. We present two approaches to the sparsity constrained Principal Component Analysis. Firstly, we develop computationally cheap heuristics that can be deployed in very high-dimensional problems. Our heuristics are justified with linear algebra approximations and theoretical guarantees. Furthermore, we strengthen our algorithms by deploying the necessary conditions for the optimization model. Secondly, we use a non-convex log-sum penalty in the semidefinite space. We show a connection to the cardinality function and develop an algorithm, PCA Sparsified, to solve the problem locally via solving a sequence of convex optimization problems. We analyze the theoretical properties of this algorithm and comment on the numerical implementation. Moreover, we derive a pre-processing method that can be used with previous approaches. Finally, our findings from the numerical experiments we conducted show that our greedy algorithms scale to high dimensional problems easily while being highly competitive in many problems with state-of-art algorithms and even beating them uniformly in some cases. Additionally, we illustrate the effectiveness of PCA Sparsified on small dimensional problems in terms of variance explained. Although it is computationally very demanding, it consistently outperforms local and greedy approaches.
Gürbüz ihale tasarımı
In optimal auction design literature, it is a common assumption that valuations of buyers are independently drawn from a unique distribution. In this thesis, we study auctions with ambiguity for an environment where valuation distribution is uncertain itself and introduce a linear programming approach to robust auction design problem. We develop an algorithm that gives the optimal solution to the problem under certain assumptions when the seller is ambiguity averse with prior set P and the buyers are ambiguity neutral with a prior f in P. Also, we consider the case where the buyers are ambiguity averse as the seller and formulate this problem as a mixed integer programming problem. Then, we propose a hybrid algorithm that enables to achieve a good solution for this problem in a reduced time.
Doğrusal programlama ile ihale tasarımı ve en iyi atama
For the sale of a single object through an auction, we assume discrete type space for agents and make use of linear programming to find optimal mechanism design for a risk-neutral seller. First, we show that the celebrated incentive compatible mechanism, second price auction, is not optimal. We find a slightly different optimal mechanism referred to as "discrete second price auction". Second we consider the problem of allocation with costly inspection. We obtain the optimal solution in the form of a favored-agent mechanism by the Greedy Algorithm. Moreover, we relax the common prior assumption and maximize the worst-case utility of an ambiguity averse seller for the two problems mentioned above. While the problem does not yield a useful optimal mechanism in general, optimal solutions for some special cases are obtained.
Dağılım belirsizliği altında portfolyo risk ölçülerinin gürbüz optimizasyonu
In this study, we consider the portfolio selection problem with different risk measures and different perspectives regarding distributional uncertainty. First, we consider the problem of optimal portfolio choice using the first and second lower partial moment risk measures, for a market consisting of n risky assets and a riskless asset, with short positions allowed. We derive closed-form robust portfolio rules minimizing the worst case risk measure under uncertainty of the return distribution given the mean/covariance information. A criticism levelled against distributionally robust portfolios is sensitivity to uncertainties or estimation errors in the mean return data, i.e., Mean Return Ambiguity. Modeling ambiguity in mean return via an ellipsoidal set, we derive results for a setting with mean return and distributional uncertainty combined. Using the adjustable robustness paradigm we extend the single period results to multiple periods in discrete time, and derive closed-form dynamic portfolio policies. Next, we consider the problem of optimal portfolio choice minimizing the Conditional Value-at-Risk (CVaR) and Value-at-Risk (VaR) measures under the minimum expected return constraint. We derive the optimal portfolio rules for the ellipsoidal mean return vector and distributional ambiguity setting. In the presence of a riskless asset, the robust CVaR and VaR measures, coupled with a minimum mean return constraint, yield simple, mean-variance efficient optimal portfolio rules. In a market without the riskless asset, we obtain a closed-form portfolio rule that generalizes earlier results, without a minimum mean return restriction. In the final problem, we have a change of perspective regarding uncertainty. Rather than the information on first and second moments, knowledge of a nominal distribution of asset returns is assumed, and the actual distribution is considered to be within a ball around this nominal distribution. The metric choice on the probability space is the Kantorovich distance. We investigate convergence of the risky investment to uniform portfolio when a riskless asset is available. While uniform investment to risky assets becomes optimal, it is shown that as the uncertainty radius increases, the total allocation to risky assets diminishes. Hence, as uncertainty increases, the risk averse investor is driven out of the risky market.
Merkezi olmayan gürbüz yatırım oyunları
In the first part of the thesis, assuming a one-period economy with an investor and two portfolio managers who are experts in investing each in a risky asset (or an index) with first and second moment information available to all parties, we consider the problem of the principal in distributing her wealth optimally among the two managers as well as setting optimally the fees to the portfolio managers under the condition that the principal wants to safeguard against uncertainty in the expert forecasts of the managers regarding the mean return of assets. In the second part, simple games are devised to ensure a fair allocation of contracts between the two managers under the conditions assumed in the first part. Furthermore, the game concept is extended in which three or more managers are involved.
S-prosedür ve bazı çeşitleri hakkında
ABSTRACTON THE S-PROCEDURE AND SOME VARIANTSKürşad DerinkuyuusM.S. in Industrial EngineeringSupervisor: Prof. Dr. Mustafa Celebi PınarşJuly, 2004In this thesis, we deal with the S-procedure that corresponds to verifying that theminimum of a quadratic function over constraints consisting of quadratic func-tions is positive. S-procedure is an instrumental tool in control theory and robustoptimization analysis. It is also used in linear matrix inequality (or semi deï¬niteprogramming) reformulations and analysis of quadratic programming. We im-prove an error bound in the Approximate S-Lemma used in establishing levels ofconservatism results for approximate robust counterparts. Moreover we extendthe S-procedure and obtain some general results in this ï¬eld. Finally, we get abound similar to Nesterov?s bound for trust region subproblem, which consistsin minimizing an indeï¬nite quadratic function subject to a norm-1 constraint byusing the Approximate S-Lemma.Keywords: S-procedure, Approximate S-Lemma, Extended S-procedure, robustoptimization, (conic) quadratic programming.iii
Çokyüzlü trafik belirsizliği durumunda gürbüz ağ tasarımı
In this thesis, we study the design of networks robust to changes in demand estimates. We consider the case where the set of feasible demands is de¯ned by an arbitrary polyhedron. Our motivation is to determine link capacity or rout- ing con¯gurations, which remain feasible for any realization in the corresponding demand polyhedron. We consider three well-known problems under polyhedral demand uncertainty all of which are posed as semi-in¯nite mixed integer program- ming problems. We develop explicit, compact formulations for all three problems as well as alternative formulations and exact solution methods. The ¯rst problem arises in the Virtual Private Network (VPN) design ¯eld. We present compact linear mixed-integer programming formulations for the prob- lem with the classical hose tra±c model and for a new, less conservative, robust variant relying on accessible tra±c statistics. Although we can solve these formu- lations for medium-to-large instances in reasonable times using o®-the-shelf MIP solvers, we develop a combined branch-and-price and cutting plane algorithm to handle larger instances. We also provide an extensive discussion of our numerical results. Next, we study the Open Shortest Path First (OSPF) routing enhanced with tra±c engineering tools under general demand uncertainty with the motivation to discuss if OSPF could be made comparable to the general unconstrained routing (MPLS) when it is provided with a less restrictive operating environment. To the best of our knowledge, these two routing mechanisms are compared for the ¯rst time under such a general setting. We provide compact formulations for both routing types and show that MPLS routing for polyhedral demands can be computed in polynomial time. Moreover, we present a specialized branch- and-price algorithm strengthened with the inclusion of cuts as an exact solution iv tool. Subsequently, we compare the new and more °exible OSPF routing with MPLS as well as the traditional OSPF on several network instances. We observe that the management tools we use in OSPF make it signi¯cantly better than the generic OSPF. Moreover, we show that OSPF performance can get closer to that of MPLS in some cases. Finally, we consider the Network Loading Problem (NLP) under a polyhe- dral uncertainty description of tra±c demands. After giving a compact multi- commodity formulation of the problem, we prove an unexpected decomposition property obtained from projecting out the °ow variables, considerably simplifying the resulting polyhedral analysis and computations by doing away with metric in- equalities, an attendant feature of most successful algorithms on NLP. Under the hose model of feasible demands, we study the polyhedral aspects of NLP, used as the basis of an e±cient branch-and-cut algorithm supported by a simple heuristic for generating upper bounds. We provide the results of extensive computational experiments on well-known network design instances. Keywords: Robust network design, polyhedral tra±c uncertainty, Virtual Pri- vate Network, Open Shortest Path First, Network Loading Problem, Branch- and-Price. v
Vadesiz amerikan tipi opsiyonların doğrusal programlama ile fiyatlandırılması ve en iyi kullanım değerlerinin belirlenmesi
An American option is the right but not the obligation to purchase or sell anunderlying equity at any time up to a predetermined expiration date for a predeterminedamount. A perpetual American option differs from a plain Americanoption in that it does not expire. In this study, we solve the optimal stoppingproblem of a perpetual American option with methods from the linear programmingliterature. Under the assumption that the underlying's price follows a discretetime and discrete state Markov process, we formulate the problem with aninfinite dimensional linear program using the excessive and majorant properties ofthe value function. This formulation allows us to solve complementary slacknessconditions efficiently, revealing an optimal stopping strategy which highlights theset of stock-prices for which the option should be exercised. Under two differentstock-price movement scenarios (simple and geometric random walks), we showthat the optimal strategy is to exercise the option when the stock-price hits a specialcritical value. The analysis also reveals that such a critical value exists onlyfor some special cases under the geometric random walk, dependent on a combinationof state-transition probabilities and the economic discount factor. Wefurther demonstrate that the method is useful for determining the optimal stoppingtime for combinations of plain vanilla options, by solving the same problemfor spread and strangle positions under simple random walks.
Niceliksel atama yöntemi ile nokta bulutu eşleştirme probleminin çözülmesi
Point cloud registration is a fundamental problem in computer vision with a wide range of applications. The problem mainly consists of three parts: feature estimation, correspondence matching and transformation estimation. We introduced the Quantile Assignment problem and proposed a solution algorithm to be used in a point cloud registration framework for establishing the correspondence set between the source and the target point clouds. We analyzed different common feature descriptors and transformation estimation methods to combine with our Quantile Assignment algorithm. The performance of these approaches together with our algorithm are tested with controlled experiments on a dataset we constructed using well-known 3D models. We detected the most suitable methods to combine with our approach and proposed a new end-to-end pairwise point cloud registration framework. Finally, we tested our framework on both indoor and outdoor benchmark datasets and compared our results with state-of-the-art point cloud registration methods in the literature.
Belirsizlik altında sağlamcı kaynak paylaştırma
Current methods for determining optimal capacity controls under uncertainty, such as stochastic optimization, often assume a known distribution for unknown parameters. This paper presents a novel approach using robust optimization to address the stochastic resource allocation problem in airline seat-inventory control. Our static formulations account for demand dependencies, offering a streamlined alternative to existing customer-choice models in revenue management literature. We analyze the structure of our proposed formulations, and provide insights on several robust counterparts of the seat-inventory control problem, considering various measures of robustness. We introduce algorithms based on these robust formulations to derive actionable results. Through extensive simulations focused on seat allocation problems within the revenue management domain, our proposed formulations demonstrate significantly improved worst-case performances. Notably, even under favorable scenarios, the performance of our solutions are comparable to those of the existing methods in the revenue management literature. By providing protection against forecasting errors in demand distribution parameters and offering improved booking limit controls when demand falls below expected value, our formulations demonstrate superior revenue retention compared to existing methods in our comparative analyses.