Browsing by Author "Kannan, Rohit"

Now showing 1 - 8 of 8
  • Thumbnail Image
    The cluster problem in constrained global optimization
    Kannan, Rohit; Barton, Paul I. (Springer, 2017-05-11)
    Deterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the cluster problem in unconstrained global optimization (Du and Kearfott 1994; Wechsung et al. in J Glob Optim 58(3):429–438, 2014) to the constrained setting based on a recently-developed notion of convergence order for convex relaxation-based lower bounding schemes. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer. In contrast to the case of unconstrained optimization, where at least second-order convergent schemes of relaxations are required to mitigate the cluster problem when the minimizer sits at a point of differentiability of the objective function, it is shown that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided. This analysis reduces to previous analyses of the cluster problem for unconstrained optimization under suitable assumptions.
  • Thumbnail Image
    Convergence-order analysis of branch-and-bound algorithms for constrained problems
    Kannan, Rohit; Barton, Paul I. (Springer, 2017-06-01)
    The performance of branch-and-bound algorithms for deterministic global optimization is strongly dependent on the ability to construct tight and rapidly convergent schemes of lower bounds. One metric of the efficiency of a branch-and-bound algorithm is the convergence order of its bounding scheme. This article develops a notion of convergence order for lower bounding schemes for constrained problems, and defines the convergence order of convex relaxation-based and Lagrangian dual-based lower bounding schemes. It is shown that full-space convex relaxation-based lower bounding schemes can achieve first-order convergence under mild assumptions. Furthermore, such schemes can achieve second-order convergence at KKT points, at Slater points, and at infeasible points when second-order pointwise convergent schemes of relaxations are used. Lagrangian dual-based full-space lower bounding schemes are shown to have at least as high a convergence order as convex relaxation-based full-space lower bounding schemes. Additionally, it is shown that Lagrangian dual-based full-space lower bounding schemes achieve first-order convergence even when the dual problem is not solved to optimality. The convergence order of some widely-applicable reduced-space lower bounding schemes is also analyzed, and it is shown that such schemes can achieve first-order convergence under suitable assumptions. Furthermore, such schemes can achieve second-order convergence at KKT points, at unconstrained points in the reduced-space, and at infeasible points under suitable assumptions when the problem exhibits a specific separable structure. The importance of constraint propagation techniques in boosting the convergence order of reduced-space lower bounding schemes (and helping mitigate clustering in the process) for problems which do not possess such a structure is demonstrated.
  • Thumbnail Image
    Data-Driven Sample Average Approximation with Covariate Information
    Kannan, Rohit; Bayraksan, Guezin; Luedtke, James R. (INFORMS, 2025-01-06)
    We study optimization for data-driven decision-making when we have observations of the uncertain parameters within an optimization model together with concurrent observations of covariates. The goal is to choose a decision that minimizes the expected cost conditioned on a new covariate observation. We investigate two data-driven frameworks that integrate a machine learning prediction model within a stochastic programming sample average approximation (SAA) for approximating the solution to this problem. One SAA framework is new and uses leave-one-out residuals for scenario generation. The frameworks we investigate are flexible and accommodate parametric, nonparametric, and semiparametric regression techniques. We derive conditions on the data generation process, the prediction model, and the stochastic program under which solutions of these data-driven SAAs are consistent and asymptotically optimal, and also derive finite sample guarantees. Computational experiments validate our theoretical results, demonstrate examples where our datadriven formulations have advantages over existing approaches (even if the prediction model is misspecified), and illustrate the benefits of our data-driven formulations in the limited data regime.
  • Thumbnail Image
    Design of PID controllers using semi-infinite programming
    Turan, Evren Mert; Kannan, Rohit; Jäschke, Johannes (Elsevier, 2022)
    The PID controller is widely used, and several methods have been proposed for choosing the controller parameters to achieve good performance. The controller tuning problem is set up as a semi-infinite program (SIP), with the integrated squared error (ISE) or the H∞ norm of the frequency domain error function (|𝐸(𝑠)|∞) as the objective function, and H∞ constraints for robustness and noise attenuation. Previous authors considered discrete points to enforce the H∞ constraints, however this is an outer approximation that does not guarantee a feasible point. When a feasible point can be found, it may require multiple iterations with a finer and finer discretisation. Here, the SIP is solved using a global optimisation algorithm. Several numerical experiments show that the proposed formulation converges quickly (<10 seconds) and gives sensible controller tuning values without the need to apply expert knowledge to the tuning problem. These results suggest that this is an attractive method for automated controller tuning.
  • Thumbnail Image
    Optimization under uncertainty of a hybrid waste tire and natural gas feedstock flexible polygeneration system using a decomposition algorithm
    Subramanian, Avinash S. R.; Kannan, Rohit; Holtorf, Flemming; Adams II, Thomas A.; Gundersen, Truls; Barton, Paul I. (Pergamon-Elsevier, 2023-12-01)
    Market uncertainties motivate the development of flexible polygeneration systems that are able to adjust operating conditions to favor production of the most profitable product portfolio. However, this operational flexibility comes at the cost of higher capital expenditure. A scenario-based two-stage stochastic nonconvex Mixed-Integer Nonlinear Programming (MINLP) approach lends itself naturally to optimizing these trade-offs. This work studies the optimal design and operation under uncertainty of a hybrid feedstock flexible polygeneration system producing electricity, methanol, dimethyl ether, olefins or liquefied (synthetic) natural gas. A recently developed C++ based software framework (named GOSSIP) is used for modeling the optimization problem as well as its efficient solution using the Nonconvex Generalized Benders Decomposition (NGBD) algorithm. Two different cases are studied: The first uses estimates of the means and variances of the uncertain parameters from historical data, whereas the second assesses the impact of increased uncertain parameter volatility. The value of implementing flexible designs characterized by the value of the stochastic solution (VSS) is in the range of 260–405 M$ for a scale of approximately 893 MW of thermal input. Increased price volatility around the same mean results in higher expected net present value and VSS as operational flexibility allows for asymmetric exploitation of price peaks.
  • Thumbnail Image
    Residuals-based distributionally robust optimization with covariate information
    Kannan, Rohit; Bayraksan, Guezin; Luedtke, James R. (Springer, 2023-09-26)
    We consider data-driven approaches that integrate a machine learning prediction model within distributionally robust optimization (DRO) given limited joint observations of uncertain parameters and covariates. Our framework is flexible in the sense that it can accommodate a variety of regression setups and DRO ambiguity sets. We investigate asymptotic and finite sample properties of solutions obtained using Wasserstein, sample robust optimization, and phi-divergence-based ambiguity sets within our DRO formulations, and explore cross-validation approaches for sizing these ambiguity sets. Through numerical experiments, we validate our theoretical results, study the effectiveness of our approaches for sizing ambiguity sets, and illustrate the benefits of our DRO formulations in the limited data regime even when the prediction model is misspecified.
  • Thumbnail Image
    A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs
    Kannan, Rohit; Luedtke, James R. (Springer, 2021-01-23)
    We propose a stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs. Our approach is based on a bi-objective viewpoint of chance-constrained programs that seeks solutions on the efficient frontier of optimal objective value versus risk of constraints violation. To this end, we construct a reformulated problem whose objective is to minimize the probability of constraints violation subject to deterministic convex constraints (which includes a bound on the objective function value). We adapt existing smoothing-based approaches for chance-constrained problems to derive a convergent sequence of smooth approximations of our reformulated problem, and apply a projected stochastic subgradient algorithm to solve it. In contrast with exterior sampling-based approaches (such as sample average approximation) that approximate the original chance-constrained program with one having finite support, our proposal converges to stationary solutions of a smooth approximation of the original problem, thereby avoiding poor local solutions that may be an artefact of a fixed sample. Our proposal also includes a tailored implementation of the smoothing-based approach that chooses key algorithmic parameters based on problem data. Computational results on four test problems from the literature indicate that our proposed approach can efficiently determine good approximations of the efficient frontier.
  • Thumbnail Image
    Stochastic DC optimal power flow with reserve saturation
    Kannan, Rohit; Luedtke, James R.; Roald, Line A. (Elsevier, 2020-12)
    We propose an optimization framework for stochastic optimal power flow with uncertain loads and renewable generator capacity. Our model follows previous work in assuming that generator outputs respond to load imbalances according to an affine control policy, but introduces a model of saturation of generator reserves by assuming that when a generator's target level hits its limit, it abandons the affine policy and produces at that limit. This is a particularly interesting feature in models where wind power plants, which have uncertain upper generation limits, are scheduled to provide reserves to balance load fluctuations. The resulting model is a nonsmooth nonconvex two-stage stochastic program, and we use a stochastic approximation method to find stationary solutions to a smooth approximation. Computational results on 6-bus and 118-bus test instances demonstrate that by considering the effects of saturation, our model can yield solutions with lower expected generation costs (at the same target line violation probability level) than those obtained from a model that enforces the affine policy to stay within generator limits with high probability.