DSpace Community:http://hdl.handle.net/2440/142017-06-24T08:32:39Z2017-06-24T08:32:39ZLarge-scale binary quadratic optimization using semidefinite relaxation and applicationsWang, P.Shen, C.Van Den Hengel, A.Torr, P.http://hdl.handle.net/2440/1061482017-06-21T23:44:01Z2017-01-01T00:00:00ZTitle: Large-scale binary quadratic optimization using semidefinite relaxation and applications
Author: Wang, P.; Shen, C.; Van Den Hengel, A.; Torr, P.
Abstract: In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.2017-01-01T00:00:00ZTextile folded half-mode substrate-integrated cavity antennaLiu, F.Xu, Z.Ranasinghe, D.Fumeaux, C.http://hdl.handle.net/2440/1060622017-06-19T23:47:42Z2016-01-01T00:00:00ZTitle: Textile folded half-mode substrate-integrated cavity antenna
Author: Liu, F.; Xu, Z.; Ranasinghe, D.; Fumeaux, C.
Abstract: The half-mode substrate-integrated cavity antenna is a promising candidate for wearable applications because of its planar structure and high isolation from environmental effects. However, for operation at 2.45-GHz ISM band, the cavity dimensions are relatively large. To reduce the antenna size in one of the dimensions, a folded half-mode substrate-integrated cavity antenna is proposed and designed. Furthermore, as an additional significant advantage for practical applications, the folded geometry allows a planar feeding structure using a shielded stripline. A prototype of the folded cavity antenna has been fabricated using textile materials and computerized embroidery. The measured reflection coefficient and radiation patterns of the prototype compare well with the simulation results and demonstrate the feasibility of the design.
Description: Date of publication February 3, 2016; date of current version November 16, 2016.2016-01-01T00:00:00ZA framework for query refinement with user feedbackIslam, M.Liu, C.Zhou, R.http://hdl.handle.net/2440/1059632017-06-14T00:03:26Z2013-01-01T00:00:00ZTitle: A framework for query refinement with user feedback
Author: Islam, M.; Liu, C.; Zhou, R.
Abstract: Abstract not available2013-01-01T00:00:00ZTime complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulasDoerr, B.Neumann, F.Sutton, A.http://hdl.handle.net/2440/1058522017-06-07T23:48:47Z2017-01-01T00:00:00ZTitle: Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas
Author: Doerr, B.; Neumann, F.; Sutton, A.
Abstract: We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and the uniform model conditional on satisfiability. Denoting the number of variables by n, our main technical result is that the simple (1+1) evolutionary algorithm with high probability finds a satisfying assignment in time O(nlogn) when the clause-variable density is at least logarithmic. For low density instances, evolutionary algorithms seem to be less effective, and all we can show is a subexponential upper bound on the runtime for densities below 1k(kâ1). We complement these mathematical results with numerical experiments on a broader density spectrum. They indicate that, indeed, the (1+1)EA is less efficient on lower densities. Our experiments also suggest that the implicit constants hidden in our main runtime guarantee are low. Our main result extends and considerably improves the result obtained by Sutton and Neumann (Lect Notes Comput Sci 8672:942â951, 2014) in terms of runtime, minimum density, and clause length. These improvements are made possible by establishing a close fitness-distance correlation in certain parts of the search space. This approach might be of independent interest and could be useful for other average-case analyses of randomized search heuristics. While the notion of a fitness-distance correlation has been around for a long time, to the best of our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.2017-01-01T00:00:00Z