## Invited Session Wed.1.H 2053

#### Wednesday, 10:30 - 12:00 h, Room: H 2053

**Cluster 9: Global optimization** [...]

### Optimal hybrid control theory approaches to global optimization

**Chair: Zelda Zabinsky**

**Wednesday, 10:30 - 10:55 h, Room: H 2053, Talk 1**

**Zelda Zabinsky**

Solving non-linear discrete optimization problems via continualization: An interior-point algorithm

**Coauthor: Wolf Kohn**

**Abstract:**

Continuous optimization problems have a tremendous structural advantage over discrete optimization problems: continuity. Necessary conditions for optimality are expressed in terms of differentiability, convexity, and other structural properties. This makes developing algorithms for continuous problems an easier task than for discrete problems. In this talk, we present a continualization approach for transforming discrete optimization problems into a continuous formulation over a compact domain. The target formulation is amenable to an interior-point descent algorithm. We use a conditional sampling procedure to translate solutions of the continuous problem into approximate solutions of the original discrete problem. The interior-point descent algorithm is expressed by a set of coupled differential equations whose integration via numerical methods generates approximate solutions to the original problem in polynomial time. The continuous problem can be characterized by a variational formulation. The central element of this formulation is a Lagrangian with nonsingular Hessian. This leads to the differential equations in the descent algorithm.

**Wednesday, 11:00 - 11:25 h, Room: H 2053, Talk 2**

**Wolf Kohn**

Hybrid dynamic programming for rule constrained multi-objective optimization

**Coauthor: Zelda B. Zabinsky**

**Abstract:**

Many optimization problems associated with large-scale complex systems require a model definition that is almost impossible to specify completely. Further, real-world applications must evaluate trade-offs between multiple objectives, which demands set representation. We will present some preliminary results of our research on developing an optimal feedback control paradigm for solving optimization problems with multiple objectives in which the model defined by the constraints is incomplete, and a complete description of the system is not available. Our optimization paradigm includes active learning of the structure of the model that goes beyond parameter adaptation. The constraints include, algebraic relations, operational if-then rules, discrete- and continuous-time dynamics, and sensor-defined constraints. Our modeling approach is based on the theory of dynamic set inclusion, because this theory lends itself to construct efficient algorithms that include learning mechanisms. Our strategy is to convert all the constraints characterizing the model to continuous-time set dynamics using a continualization transformation developed in a previous paper by Kohn, et al.

**Wednesday, 11:30 - 11:55 h, Room: H 2053, Talk 3**

**Pengbo Zhang**

Stochastic control optimization of a binary integer program

**Abstract:**

We develop a discrete meta-control algorithm that provides a good approximation to large-scale binary integer programs with low polynomial time complexity. The key innovation to our optimal control approach is to map the vector of n binary decision variables into a scalar function defined over a discrete time interval *[0, n]* and define a linear quadratic tracking (LQT) problem that closely approximates the original problem. Our method uses an Aoki-based decomposition approach and an error correction with a Kalman filter technique that introduces less error than the continuous form used in our previous research, but maintains the primary computational advantage. We use the necessary conditions for optimality to prove that there exists an integer solution to the LQT version of the original BIP, with a bang-bang type solution. We prove that our meta-control algorithm converges to an approximate solution in polynomial time with regard to the time horizon, which is the number of binary variables *n*. The algorithm is illustrated with several large examples. The meta-control algorithm can be extended to mixed integer programs.