What is General Optimization?
Optimization is a broad term that refers to the problem of finding the set of variables within predefined bounds, that extremizes (i.e. minimizes or maximizes) a derived quantity.
Terminology
An optimization problem can be divided into the following parts.
Decision Variables
These refer to the independant variables that you can vary to find the optimal solution. The decision variables can be of different forms - continuous (ie. real numbers), discrete (ie, integers), binary (0 or 1) or a mix of these. The decision variables may span the entire domain, or may be bounded to a subset of the numbers.
Objective
This refers to the value that is to be extremized. The objective must be derived from the decision variables.
Note: BQPhy assumes the optimization problem to be a minimization problem. Hence, the objective must be modified accordingly.
Constraints
Along with the bounds in the decision variables, the problem definition may impose bounds on some derived quantities for acceptable solutions. These are called feasible solutions, and the domain of the decision variables is restricted by the imposed constraints.
The constraints provided are generally of two kinds, inequality constraints and equality constraints, with the latter restricting the domain more, and is more difficult to solve.
Essential Parameters for the BQPhy Platform
BQPhy uses the Quantum-Inspired Evolutionary Optimization (QIEO) algorithm for solving optimization problems. It is a metaheuristic algorithm, which can solve most form of problems - from linear to nonlinear, convex or non-convex, NP-hard and multimodal problems.
The QIEO takes the input as a chromosome, which refers to a list of binary numbers. The decision variables must be mapped onto the chromosome for optimization.
The current version of BQPhy allows users to work with chromosome containing all continuous values or all binary values.
For effective and fast solving of the problems, QIEO takes in certain parameters from the user
Population
Population represents a group of chromosomes, representing candidate solutions for the problem. Each member of the population represents a distinct point in the search space, encoded according to the problem representation.
Generation
A generation refers to one complete update cycle of the population. During each generation, the best solution among the population is found and the chromosomes are modified to direct towards the global optima in the most efficient manner.
The optimization problem is run until the population or fitness value satisfies a convergence criteria or a specified number of generations are run.
Theta
Theta refers to the hyperparameter that controls the convergence rate of the QIEO algorithm. It loosely quantifies the extent to which the chromosomes of a particular generation are to be directed to the best chromosome of that generation. A lower value of theta signifies less effect, which leads to more exploration of search space (hence a higher chance to get global optima) but slower convergence. High values of theta causes the population to move towards the best chromosome, which leads to faster convergence but risks falling into a local minima due to low exploration.
The value of theta can be varied so as to get the global optima in the fastest and most efficient manner.
For balanced usage, theta of 0.05 or 0.1 is generally used.
Trial
A trial represents an independant run of the optimization problem (from initialization to convergence). Since metaheuristic algorithms (like QIEO) do not guarantee global optima and can depend on the intiial population, it is preferred to run the problem for multiple trials and select the best fitness value among them.