Optimization Methods and Algorithms for Classes of Black-Box and Grey-Box Problems

There are many optimization problems in physics, chemistry, finance, computer science, engineering and operations research for which the analytical expressions of the objective and/or the constraints are unavailable. These are black-box problems where the derivative information are often not available or too expensive to approximate numerically. When the derivative information is absent, it becomes challenging to optimize and guarantee optimality of the solution. The objective of this Ph.D. work is to propose methods and algorithms to address some of the challenges of blackbox optimization (BBO). A top-down approach is taken by first addressing an easier class of black-box and then the difficulty and complexity of the problems is gradually increased. In the first part of the dissertation, a class of grey-box problems is considered for which the closed form of the objective and/or constraints are unknown, but it is possible to obtain a global upper bound on the diagonal Hessian elements. This allows the construction of an edge-concave underestimator with vertex polyhedral solution. This lower bounding technique is implemented within a branch-and-bound framework with guaranteed convergence to global optimality. The technique is applied for the optimization of problems with embedded system of ordinary differential equations (ODEs). Time dependent bounds on the state variables and the diagonal elements of the Hessian are computed by solving auxiliary set of ODEs that are derived using differential inequalities. In the second part of the dissertation, general box-constrained black-box problems are addressed for which only simulations can be performed. A novel optimization method, UNIPOPT (Univariate Projection-based Optimization) based on projection onto a univariate space is proposed. A special function is identified in this space that also contains the global minima of the original function. Computational experiments suggest that UNIPOPT often have better space exploration features compared to other approaches. The third part of the dissertation addresses general black-box problems with constraints of both known and unknown algebraic forms. An efficient two-phase algorithm based on trust-region framework is proposed for problems particularly involving high function evaluation cost. The performance of the approach is illustrated through computational experiments which evaluate its ability to reduce a merit function and find the optima