糖心视频

The first talk was given by ). When this is the case, exact methods, those for which convergence to a true optimal solution is proven, are not practical or will get stuck at a local rather than a global minimum. Some of the examples that Epitropakis has worked on included optimising the trajectory of a probe between planets and aircraft scheduling. There are many types of metaheuristcs including evolutionary algorithms such as genetic algorithms that adapt to the problem as it is running, and population based searches like Ant Colony Algorithms. Whilst I have no doubt as to the effectiveness of these Metaheuristic approaches, they still lack mathematical proof and this leaves me with reservations about the topic.

The design of a SSOA requires three different parts, representation, a search strategy and a fitness function. The representation is the requirement that every possible state of the system must be represented. The search strategy gives the rules for how to move around the space of states. The fitness function is a way of assessing the states and how good they are. One question being researched is that of automatic design. If a program is given a problem, it should be able to choose what to do and how to approach it. The advantages of this idea is that is it is more flexible and can get a better fit to a general problem. However, the many components can make it difficult to assess the performance of a state.

The second talk was on Multi-Objective Mathematical Programming Optimisation and was given by , who described the problem as a generalisation of Linear Programming. First a little bit of background on cones. A cone, $\mathcal{C}\subset\mathbb{R}^n$, is defined such that if $x\in\mathcal{C}$, then $\lambda x\in\mathcal{C}$ for all $\lambda>0$. In particular, we are interested in pointed and symmetric cones (in 3 dimensions it looks like an ice cream cone). Many different shapes and curves can be made by intersecting hyperplanes with cones. Circles can be made if the plane is normal to the cone axis, hyperbolae if the plane is parallel to the axis, and inbetween are ellipses and parabolas. In $\mathbb{R}^n$, a second order cone is one that satisifies $$x_n = \sqrt{x_1^2 + ... + x_{n-1}^2}.$$

What, you may ask, have cones and intersections and shapes got to do with optimisation? A Conic Programme is an optimisation problem of the form $$\text{inf}\left\lbrace c^Tx : Ax \leq b , x\in\mathcal{C}\right\rbrace.$$ The restriction to the cone, if a hyperplane is chosen well, is equivalent to the inclusion of a quadratic or hyperbolic constraint, such as the one above, as well as the linear constraints. This now means that an optimum solution can be found to the problem, as in the case of linear programming. The use of the second order cone equation as a constraint makes this a Second Order Cone Program (SOCP). There are also other forms of conic programming that can be used.

Importantly, this is far better than other non-linear programming methods, which only approximate the optimum, for the particular problems it is applicable to. However, whereas currently LPs can be used for 10$^5$ variables pretty quickly, SOCP can only be used on about 1000 variables. And where as the LPs can be solved in $\mathcal{O}(n^3)$ time, SOCPs have an order of $\mathcal{O}(n^4)$. It is still polynomial, but if you can get away with an LP, you probably should. I think Conic Programming appeals to me as it is cleverly using mathematical structures to solve problems a little beyond the scope of linear programming in an exact and rigorous way.