Chee-Khian Sim
Chee-Khian Sim has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Mabel C. Chou
National University of Singapore
3 shared publications - Xue-Ming Yuan
Centre for Maritime Studies, National University of Singapore (NUS), Singapore 119077, Singapore
3 shared publications - Chung-Piaw Teo
Institute of Operations Research and Analytics, National University of Singapore, Singapore 117602
2 shared publications - Jiaming Liang
Goergen Institute for Data Science and Artificial Intelligence (GIDS-AI) Department of Computer Science University of Rochester 14620 Rochester NY
2 shared publications - Renato D. C. Monteiro
Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA
2 shared publications - Renato D. C. Monteiro
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA
2 shared publications
Latest Publications
- Open Access
First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex
We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is a sum of a possibly nonconvex function, with Lipschitz continuous gradient, and a convex function which can be nonsmooth. The algorithm is shown to have an iteration complexity of $\mathcal{O}(ε^{-2})$ to find an $ε$-approximate solution to the problem, and this complexity improves to $\mathcal{O}(ε^{-2/3})$ when the objective function turns out to be convex. We further provide asymptotic convergence rate for the algorithm of worst case $o(ε^{-2})$ iterations to find an $ε$-approximate solution to the problem, with worst case $o(ε^{-2/3})$ iterations when its objective function is convex.Open AccessFirst Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex
We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is a sum of a possibly nonconvex function, with Lipschitz continuous gradient, and a convex function which can be nonsmooth. The algorithm is shown to have an iteration complexity of $\mathcal{O}(ε^{-2})$ to find an $ε$-approximate solution to the problem, and this complexity improves to $\mathcal{O}(ε^{-2/3})$ when the objective function turns out to be convex. We further provide asymptotic convergence rate for the algorithm of worst case $o(ε^{-2})$ iterations to find an $ε$-approximate solution to the problem, with worst case $o(ε^{-2/3})$ iterations when its objective function is convex. - Open Access
Superlinear Convergence of an Interior Point Algorithm on Linear Semi-definite Feasibility Problems with Application to Linear Matrix Inequalities
In the literature, besides the assumption of strict complementarity, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual or the NT direction, to solve semi-definite programs (SDPs) is shown by (i) assuming that the given SDP is nondegenerate and making modifications to these algorithms [10], or (ii) considering special classes of SDPs, such as the class of linear semi-definite feasibility problems (LSDFPs) and requiring the initial iterate to the algorithm to satisfy certain conditions [26, 27]. Otherwise, these algorithms are not easy to implement even though they are shown to have polynomial iteration complexities and superlinear convergence [14]. The conditions in [26, 27] that the initial iterate to the algorithm is required to satisfy to have superlinear convergence when solving LSDFPs however are not practical. In this paper, we propose a practical initial iterate to an implementable infeasible interior point algorithm that guarantees superlinear convergence when the algorithm is used to solve the homogeneous feasibility model of an LSDFP.
Open AccessSuperlinear Convergence of an Interior Point Algorithm on Linear Semi-definite Feasibility Problems with Application to Linear Matrix Inequalities
In the literature, besides the assumption of strict complementarity, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual or the NT direction, to solve semi-definite programs (SDPs) is shown by (i) assuming that the given SDP is nondegenerate and making modifications to these algorithms [10], or (ii) considering special classes of SDPs, such as the class of linear semi-definite feasibility problems (LSDFPs) and requiring the initial iterate to the algorithm to satisfy certain conditions [26, 27]. Otherwise, these algorithms are not easy to implement even though they are shown to have polynomial iteration complexities and superlinear convergence [14]. The conditions in [26, 27] that the initial iterate to the algorithm is required to satisfy to have superlinear convergence when solving LSDFPs however are not practical. In this paper, we propose a practical initial iterate to an implementable infeasible interior point algorithm that guarantees superlinear convergence when the algorithm is used to solve the homogeneous feasibility model of an LSDFP.
- Open Access
- 2 December 2022
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 196 (1) , 298-323
Convergence Rates for the Relaxed Peaceman-Rachford Splitting Method on a Monotone Inclusion Problem
We consider the convergence behavior using the relaxed Peaceman–Rachford splitting method to solve the monotone inclusion problem $$0 \in (A + B)(u)$$ , where $$A, B: \Re ^n \rightrightarrows \Re ^n$$ are maximal $$\beta $$ -strongly monotone operators, $$n \ge 1$$ and $$\beta > 0$$ . Under a technical assumption, convergence of iterates using the method on the problem is proved when either A or B is single-valued, and the fixed relaxation parameter $$\theta $$ lies in the interval $$(2 + \beta , 2 + \beta + \min \{ \beta , 1/\beta \})$$ . With this convergence result, we address an open problem that is not settled in Monteiro et al. (Computat Optim Appl 70:763–790, 2018) on the convergence of these iterates for $$\theta \in (2 + \beta , 2 + \beta + \min \{ \beta , 1/\beta \})$$ . Pointwise convergence rate results and R-linear convergence rate results when $$\theta $$ lies in the interval $$[2 + \beta , 2 + \beta + \min \{\beta , 1/\beta \})$$ are also provided in the paper. Our analysis to achieve these results is atypical and hence novel. Numerical experiments on the weighted Lasso minimization problem are conducted to test the validity of the assumption.- 2 December 2022
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 196 (1) , 298-323
Open AccessConvergence Rates for the Relaxed Peaceman-Rachford Splitting Method on a Monotone Inclusion Problem
We consider the convergence behavior using the relaxed Peaceman–Rachford splitting method to solve the monotone inclusion problem $$0 \in (A + B)(u)$$ , where $$A, B: \Re ^n \rightrightarrows \Re ^n$$ are maximal $$\beta $$ -strongly monotone operators, $$n \ge 1$$ and $$\beta > 0$$ . Under a technical assumption, convergence of iterates using the method on the problem is proved when either A or B is single-valued, and the fixed relaxation parameter $$\theta $$ lies in the interval $$(2 + \beta , 2 + \beta + \min \{ \beta , 1/\beta \})$$ . With this convergence result, we address an open problem that is not settled in Monteiro et al. (Computat Optim Appl 70:763–790, 2018) on the convergence of these iterates for $$\theta \in (2 + \beta , 2 + \beta + \min \{ \beta , 1/\beta \})$$ . Pointwise convergence rate results and R-linear convergence rate results when $$\theta $$ lies in the interval $$[2 + \beta , 2 + \beta + \min \{\beta , 1/\beta \})$$ are also provided in the paper. Our analysis to achieve these results is atypical and hence novel. Numerical experiments on the weighted Lasso minimization problem are conducted to test the validity of the assumption. - Open Access
Solution to a Monotone Inclusion Problem using the Relaxed Peaceman-Rachford Splitting Method: Convergence and its Rates
We consider the convergence behavior using the relaxed Peaceman-Rachford splitting method to solve the monotone inclusion problem $0 \in (A + B)(u)$, where $A, B: \Re^n \rightrightarrows \Re^n$ are maximal $\beta$-strongly monotone operators, $n \geq 1$ and $\beta > 0$. Under a technical assumption, convergence of iterates using the method on the problem is proved when either $A$ or $B$ is single-valued, and the fixed relaxation parameter $\theta$ lies in the interval $(2 + \beta, 2 + \beta + \min \{ \beta, 1/\beta \})$. With this convergence result, we address an open problem that is not settled in [20] on the convergence of these iterates for $\theta \in (2 + \beta, 2 + \beta + \min \{ \beta, 1/\beta\})$. Pointwise convergence rate results and $R$-linear convergence rate results when $\theta$ lies in the interval $[2 + \beta, 2 + \beta + \min \{ \beta, 1/\beta\})$ are also provided in the paper. Our analysis to achieve these results is atypical and hence novel. Numerical experiments are conducted on the weighted Lasso minimization problem to test the validity of the assumption .Open AccessSolution to a Monotone Inclusion Problem using the Relaxed Peaceman-Rachford Splitting Method: Convergence and its Rates
We consider the convergence behavior using the relaxed Peaceman-Rachford splitting method to solve the monotone inclusion problem $0 \in (A + B)(u)$, where $A, B: \Re^n \rightrightarrows \Re^n$ are maximal $\beta$-strongly monotone operators, $n \geq 1$ and $\beta > 0$. Under a technical assumption, convergence of iterates using the method on the problem is proved when either $A$ or $B$ is single-valued, and the fixed relaxation parameter $\theta$ lies in the interval $(2 + \beta, 2 + \beta + \min \{ \beta, 1/\beta \})$. With this convergence result, we address an open problem that is not settled in [20] on the convergence of these iterates for $\theta \in (2 + \beta, 2 + \beta + \min \{ \beta, 1/\beta\})$. Pointwise convergence rate results and $R$-linear convergence rate results when $\theta$ lies in the interval $[2 + \beta, 2 + \beta + \min \{ \beta, 1/\beta\})$ are also provided in the paper. Our analysis to achieve these results is atypical and hence novel. Numerical experiments are conducted on the weighted Lasso minimization problem to test the validity of the assumption . - 13 May 2021
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 79 (3) , 649-679
A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
- 13 May 2021
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 79 (3) , 649-679
A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
- Open Access
A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
In this paper, we describe and establish iteration-complexity of two accelerated composite gradient (ACG) variants to solve a smooth nonconvex composite optimization problem whose objective function is the sum of a nonconvex differentiable function $ f $ with a Lipschitz continuous gradient and a simple nonsmooth closed convex function $ h $. When $f$ is convex, the first ACG variant reduces to the well-known FISTA for a specific choice of the input, and hence the first one can be viewed as a natural extension of the latter one to the nonconvex setting. The first variant requires an input pair $(M,m)$ such that $f$ is $m$-weakly convex, $\nabla f$ is $M$-Lipschitz continuous, and $m \le M$ (possibly $m<M$), which is usually hard to obtain or poorly estimated. The second variant on the other hand can start from an arbitrary input pair $(M,m)$ of positive scalars and its complexity is shown to be not worse, and better in some cases, than that of the first variant for a large range of the input pairs. Finally, numerical results are provided to illustrate the efficiency of the two ACG variants.Open AccessA FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
In this paper, we describe and establish iteration-complexity of two accelerated composite gradient (ACG) variants to solve a smooth nonconvex composite optimization problem whose objective function is the sum of a nonconvex differentiable function $ f $ with a Lipschitz continuous gradient and a simple nonsmooth closed convex function $ h $. When $f$ is convex, the first ACG variant reduces to the well-known FISTA for a specific choice of the input, and hence the first one can be viewed as a natural extension of the latter one to the nonconvex setting. The first variant requires an input pair $(M,m)$ such that $f$ is $m$-weakly convex, $\nabla f$ is $M$-Lipschitz continuous, and $m \le M$ (possibly $m<M$), which is usually hard to obtain or poorly estimated. The second variant on the other hand can start from an arbitrary input pair $(M,m)$ of positive scalars and its complexity is shown to be not worse, and better in some cases, than that of the first variant for a large range of the input pairs. Finally, numerical results are provided to illustrate the efficiency of the two ACG variants. - Open Access
- 24 February 2020
- Published by Springer Nature in Annals of Operations Research
- Vol. 288 (1) , 137-180
Policies for inventory models with product returns forecast from past demands and past sales
Finite horizon periodic review backlog models are considered in this paper for an inventory system that remanufactures two types of cores: buyback cores and normal cores. Returns of used products as buyback cores are modelled to depend on past demands and past sales. We derive an optimal inventory policy for the model in which returns are forecast to depend on past demands, and analyze properties of the optimal cost and optimal policy we derived. As the structure of the optimal inventory policy for the model in which returns are forecast from past sales is unlikely to be tractable, we instead consider a feasible inventory policy with a nice structure for this model. We investigate how close this policy is to optimality and find that in the worst case, the difference in system costs between the feasible policy and the optimal inventory policy is bounded by a constant that is dependent only on cost parameters, mean demands and a discount factor, and is independent of the planning horizon and initial inventories. We also perform numerical experiments to study the difference between system costs under the feasible policy and those under the optimal policy.
- 24 February 2020
- Published by Springer Nature in Annals of Operations Research
- Vol. 288 (1) , 137-180
Open AccessPolicies for inventory models with product returns forecast from past demands and past sales
Finite horizon periodic review backlog models are considered in this paper for an inventory system that remanufactures two types of cores: buyback cores and normal cores. Returns of used products as buyback cores are modelled to depend on past demands and past sales. We derive an optimal inventory policy for the model in which returns are forecast to depend on past demands, and analyze properties of the optimal cost and optimal policy we derived. As the structure of the optimal inventory policy for the model in which returns are forecast from past sales is unlikely to be tractable, we instead consider a feasible inventory policy with a nice structure for this model. We investigate how close this policy is to optimality and find that in the worst case, the difference in system costs between the feasible policy and the optimal inventory policy is bounded by a constant that is dependent only on cost parameters, mean demands and a discount factor, and is independent of the planning horizon and initial inventories. We also perform numerical experiments to study the difference between system costs under the feasible policy and those under the optimal policy.
- Open Access
- 22 May 2019
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 74 (2) , 583-621
Interior point method on semi-definite linear complementarity problems using the Nesterov–Todd (NT) search direction: polynomial complexity and local convergence
- 22 May 2019
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 74 (2) , 583-621
Open AccessInterior point method on semi-definite linear complementarity problems using the Nesterov–Todd (NT) search direction: polynomial complexity and local convergence
- 1 April 2018
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 66 (2) , 500-513
Profit Sharing Agreements in Decentralized Supply Chains: A Distributionally Robust Approach
How should decentralized supply chains set the profit sharing terms using minimal information on demand and selling price? We develop a distributionally robust Stackelberg game model to address this question. Our framework uses only the first and second moments of the price and demand attributes, and thus can be implemented using only a parsimonious set of parameters. More specifically, we derive the relationships among the optimal wholesale price set by the supplier, the order decision of the retailer, and the corresponding profit shares of each supply chain partner, based on the information available. Interestingly, in the distributionally robust setting, the correlation between demand and selling price has no bearing on the order decision of the retailer. This allows us to simplify the solution structure of the profit sharing agreement problem dramatically. Moreover, the result can be used to recover the optimal selling price when the mean demand is a linear function of the selling price (cf. Raza 2014) [Raza SA (2014) A distribution free approach to newsvendor problem with pricing. 4OR—A Quart. J. Oper. Res. 12(4):335–358.]. The online appendix is available at https://doi.org/10.1287/opre.2017.1677 .
- 1 April 2018
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 66 (2) , 500-513
Profit Sharing Agreements in Decentralized Supply Chains: A Distributionally Robust Approach
How should decentralized supply chains set the profit sharing terms using minimal information on demand and selling price? We develop a distributionally robust Stackelberg game model to address this question. Our framework uses only the first and second moments of the price and demand attributes, and thus can be implemented using only a parsimonious set of parameters. More specifically, we derive the relationships among the optimal wholesale price set by the supplier, the order decision of the retailer, and the corresponding profit shares of each supply chain partner, based on the information available. Interestingly, in the distributionally robust setting, the correlation between demand and selling price has no bearing on the order decision of the retailer. This allows us to simplify the solution structure of the profit sharing agreement problem dramatically. Moreover, the result can be used to recover the optimal selling price when the mean demand is a linear function of the selling price (cf. Raza 2014) [Raza SA (2014) A distribution free approach to newsvendor problem with pricing. 4OR—A Quart. J. Oper. Res. 12(4):335–358.]. The online appendix is available at https://doi.org/10.1287/opre.2017.1677 .