| |
| """Optimized solver for AC inequality. |
| Uses a pre-optimized template found by progressive Lp-norm gradient descent. |
| Online refinement with perturbation + Lp optimization.""" |
|
|
| import time |
| import numpy as np |
| import zlib |
| import base64 |
| from scipy.signal import fftconvolve |
| from scipy.optimize import minimize |
|
|
|
|
| _TEMPLATE_B64 = ( |
| "eNrtWHk011vXl0KhSYYyVSRDUiKV6bs/X1ODqS6plCEUUkilKGUIGTKGhOSSQiIZKsmcoSgNRGkg" |
| "zelWt8Fwvd3fXbf13vfeZ633Wc/zx7ue9/6x1znfffY5Z5+9P3uffb67N9ixI31dKk/UTNlROaHa" |
| "9y8astLtElRRQ+ythLVw8FRgpSdsBr+6GjtabAwmZomwtsG2eK+5hPU/50hFBbJsi0UOqQyPZd9W" |
| "DtEU+XFs2i5haEeXY6maANy2nIR3thB6zdIhr6qIIWF/nAvsoNW7cvBmyz60D8bBvigOPS+PonSZ" |
| "Bzq2B6Bxdha4vkSjZlEI7ia4weYQN6bNkcRufh16OHEVftW3vkCEyT8VS68+BNKCzW66+3Iq6Vf+" |
| "6/BoTsu2p5FV1DbqVzpLvMkvSbGkmEk4JErPSi8xLxK6mF9lGo2X6/za/k5n249z+FuLpajZIZWp" |
| "Mqujwa0NTOOjw/TCSQoLmmfT1k88mMQtp1O/bT4kZI7QhTxP9CgL4WSqJ4K+6uOh8SloOO+C5ZVG" |
| "+JVEYHHUa5Q6RqFL5Gfo3kiHf8o7LBsOxm08QptoGG6MnMD95ccx1SgSNpODUZKwFwd03HFV1R0e" |
| "7ivx5L0n/K/7orqvht4Z7sdUmfFIW5eBprE/U9OcCqyXGY01D3Jw+dBieF7IxJyeFegM8YK/8nZc" |
| "7zHGrC+rkf8kCEbGxjjUZYZyueXQstiOrmRtHKiwATc+0cTwuejyuUMXM0chTr2CcuoUqfBiNLVo" |
| "GlHWvLf07s1Jpi//GlUHbSKptJMkVdpKW9TSqDzvC7ExJbT/sypmu6iSJ68cuKV3U7mBHuRPP2LC" |
| "BmbA0HCYKV7Eh5xzk8mobR5ym83pWedYOCuHk07/cjTu6KDJXD+AS+o9TWpeC7HhBShIDcOJCX64" |
| "cjMQC24fwPCuM9i32wVORwvwbFIgrhWcxMfIHxAvXoAzPmFIastGbH047PeEo/LbmS1idqLbnLA0" |
| "djvKz7+nUm9nrPK6SOLOZlh44AuJPbeArCYvCmMnIWmpIg64iSAyQw8THDago9oG7w5vxPCtmZg3" |
| "IxTxMc9o2ctoCHpLYPNDd+x9y4/G8CXoS9bC7OmvKeeMFiw/3SRhqTc036uCBHddpv0zO8jvczC5" |
| "nTlD266cI9HntkxQ5TLaWbqOqYrIoIZp7cyQfyFJDrhQn/tKKlQeoEKHYJKyF0DWzmCqWzAHMeI/" |
| "0g/PhMDn0kVCQ1PBe7eALGaJY971MkpuksX84+YktWc5bC7LUXTMChSuPEJR471RP6qdukXCsCPX" |
| "ANtuxyB56jqYzMxBWaIvrATTkTQ2BCse5eGeagDMNmQiVjgaz6/HodY0Bgrrg1HN44+MRXsRX+uG" |
| "U3QINXNMsbHXB9l3rMGtboFLV20RmeaOgnkHUHdTHyfWOaPaYgdch0xh/jEUrzw34qLVIcQoW+LW" |
| "1Xg4z4nBirFHcONYAmxzD6LjeRpcRpyh2XAY9rtWIiFlKc5sAna+2AhdFR7Uv9TAxMZW8jUZodlc" |
| "RuT4fC7uhzUzq8/e5sS1pfEFqvF4wnhdaKDKbfG0fV8AlTzgJw/vGpo20Y5EonjgKLCWTtZOxeFl" |
| "cylZQBofLwsjdIcBYhxX4M5WQZQ3HIDeVB6U9x9EwbA4EpX84Sj2lFZ/8sDM5lnoytsLHhlDZDWF" |
| "QV19GRJehcG5bQu6MtIxON4ZoaEFiNTzw4NdF+F3IxR+R+/immMYjObUw1o/COvicpCYuwV79qVg" |
| "lq8V8rJ2YcrahRgZFwyX61ZIU9mLrOL90KvbA2V1WzyYGgyZ9Ehcq4xF2MwIfL2SjLVinli9IhMO" |
| "TiH4+sMVxBWEYfjoOahODEbruzzsFtiHNbGX8E41BMZZUcieFgbxC/6oqDmEK7O9kTjGH1K8C6Ai" |
| "qoGr9yYimX+E+FY30pqf20l0XAmFr2mlcQ2nyXK6MqaP66KezwqY2TYNQ5fUUf/ZAGLuuuA9Gg3J" |
| "+d/8vjkZC9/7I3pMFpzsv+W03iy8SjqGFtNY7Fj9I3zsjsOn5ihypeKROpiB/FvHMHZnEsYr5cG3" |
| "/hQyX5zCGPcSLJLNgVDHRaw8HwEe61b4H8iDYEcjboTV4uarDmRdL0T/g/tQrCjBsu5OvHhzGlJv" |
| "7kNjajTqpUoR+4M/dG/mw6wsA+sSwlDjeRG5ilug3pqIU0bmcH2Siaz0pXjWXAxbb2MIPK2EgYkT" |
| "hG0/op9rM/g2vIO6+Tx8+PgB+/mVcFO7F/2DpnBtvo4NHcKw/FoBpxlciMj7EfL118ioNgArBQ7Q" |
| "Jw0HBPcrkeCRWfjv98WvZFI6yGT0JtN+26ukNnYC4zMihAcDabruHYKYIpRCrxfKIvaNP6VN2w7b" |
| "8vtUaRmJg1Nl4OqfgN6N7mjaGYy7xb7obo5C2RZlJJpnoJt2QEc+Bz7R3/Lp+0q8TlJGKF869vit" |
| "h8Pcqwg8G4yf9BMw+ZvtVy+qRXlaAQw6unD6SBGilt3BoEUsNpW9hdu3vH92aSd+6U3BnPw6tOrH" |
| "wLCkHloDdVBf3IzH44qRL9yGdK8S9Pk34ZcxXrhgVYBPAsFwNa+D+Jbt8P0YghCRathalkAyshpv" |
| "NXPAdFdhzZYcyOYW4WtDNgZuHwHjdhxhWwnrnkTgRrQlDmbug/FoXfT1tdP/tNk/Q7e2bWfkX2+j" |
| "bclHyWdFFIWWFVB8zmk67DEaO0+ma9/IWA4Z2U5ml6IoxzeaqsZYnOiiu8lwH3bvtdDlXzoGQQ7P" |
| "KT1EFMFSm6jdZy2q3EbD09YMcU2j4XI1nUJi3PGS1x9z9srDxP0Gzazgwfw7Quj30sWj86r0MH0M" |
| "1ocsoqzGLNrXWkTcr03xpb+ERIP90VC0HKprnbF+3BSMdQyCq34gHk9yxlDQt/h464wtd6zgkm2M" |
| "pJvieCtphhv7RfEyexe8uCdi+n1pUKIrCc/vYZRLMujDc21yUGghZfMeepq8AbKiwdjPF4KRKRH4" |
| "HJGFvG95xu/rAAK/1RCFgkM4J/oLihOEWS0bQVbl43i2qY6Ltd8rxN6J5WfVDo5iZ4QKsB4PH6Ox" |
| "qQNf2lox2e0kpl9PxrEbHQi8VAN7k3w0OdUy/oNqpGtgiQ/1cmg5fRnNfalYwmZDX6PoD3j/GOeH" |
| "0Ff9GP5FERe/YcMmLw5dEZ4oKOWDwiw9fLiqjDOG33JcRx89yR8Fle5HjMP5lfA4I43qAgmcbBwL" |
| "vxo7WtR0T1chfy1ZjpgyLjwT6Z1AOfNXvp/WZ03XXgQyyTvVYVUbwYzo9dMtaZYeSQT+CVNOrbI6" |
| "GnVDpNzQzxl7Njke92aNZ78Ym9GUyb7wvZyFTa7dnH1mmniTc2g0p6+UK8/ETANnzrSDgcQd3oJo" |
| "k1wYWYegyYjlyMxz7ab2Nhs0ixnojmiKQK8slz6ZnGIutqqjPIxFf2scR+7dAWFmuvgHpme3Es14" |
| "+5hOP3P/fi5rNRHIjcSRTdcFevN1JWNQGUOvquSYBTvEaeCT2He5Q43TOTZftaqSw8tQHPd9TMpk" |
| "tu7v/Sav+/S+VIgSo5sY7SJh5Nx8w1xUGPUnO6b9tPk7T6Gg6rvdJlbHMfpr7+q0JF/VkREa4shE" |
| "ikRx2hk1i2kRMw/zext1/5XY/XcST57VH3yeFfzsT7oVLt5Ea+ZvowKLT2QtpICHLaF03UWUuvb/" |
| "5seWzkk0qJpPAb08nLUCm8OpKC+UxoVK4cMKQ8TzVdMms1VUE9XJVFfdJNPNW3EvIxAK57+Sxg1J" |
| "yHoZg61Lx1ZXL7R1h0ILSrh1O5MyB7PpsbsOnJx+omKHYabv4nVG9UUlUzyUT1nrFSHRoYRFB60R" |
| "aCqHJx8GadqsBVipZ4/rglMw+EoGLg/HYEnbbLjx6KBY0xDyxnK4vbGCAqpnUU2ZNnXKP6fqok7a" |
| "Mfo+cSelkP9IMy10/ELVTvqwsVsMLktgqEEVba9VEOE9F92O3phyzwqZG9fAyfEJXcoQxaiyBRDJ" |
| "mY/YACHI6A1QWp8emdXvJ22+FxSceJ52XpkIOwdJ3OZagnmiarAWt8NLGQnody+FvMorevkqgw7v" |
| "6aNi//EYsayiN/lZxHMnkhI0TtOorUqkaeZHJkNqdJuCqORlCLNEKJ8e3T5Hr5YrQkRxmNpX8EF2" |
| "1TOSj9OC1CE1jKiux6P857Q57iKdemtII9Yd1CufTaEF94hHpofpqEghj7pu6s4boFQnEbznmwKj" |
| "+bV0/95z+nn9IFW0KEOryRyxCmqIXDoB8x6vwe4zYrDzUcPby7KQlBVC7PMSqtxxllRbJMn6TAkt" |
| "4i+nzu779On8ckJ2InWndNAqFQ2E+iggW1UCumXjcC+rnvxnCSLVXhxKGka418wPv+kPSD2rlhb0" |
| "TMTJLlHEv+ins2LZdNlegTI1denjxhR6KSqIDdYzUHDyOokIVJNXbSJN6bxKKdsGSevREizvSKHO" |
| "siDm8jA/9aQEkEpXOTkOBJDW5gYONk2L5DmYbL318g8xLFBJlFYaxvh6ZzIOJ14yVdvTmCjvBGKU" |
| "11COxCiMPVbMHONP5czNmH+atA20yPTxb7nDNKiFueWQxOxTu8FcbQ+jkI4AusrrpH1hlwfn3Zse" |
| "f+kv866tyC0tG9/K/zOx/zf9/yXZCjtirE7SE5vtWPpUGr3tHRSWHkQ67AlqmCADrnHSkHUNhrbN" |
| "MHVLO+POpzwyuZIAhQ2RmJhM0LnHg4Q9ycxPgytRXiEBlydFUNqxHAvPH8HTxBhorXyCDJ1a5L/v" |
| "hHRQN7gb4nF+QxRuTYrC7dZyOthUSDPPeGKKTgKUd/vBwncbdLVScfSXQOxjX2BgIBfO396L5xKr" |
| "oK7VgFn7JrBe1k1Ysy8cmYeeghQOY/e4aohp9iHF9hTuxh7Dg0unSaDlK7GyP9L4IVfck0nA2h95" |
| "2aeffoKz9Hg2yV6FbfKexioIirDZy95gbkIpBF6HwGttHcLfDaKl+AVy3UPhVRqL7PSjSEYUeHtn" |
| "shPip7OM0SIYL3eHtiMfG+rSi9kexbA/kQO/6FUw+DIHl+8vxfu3Q8z0KhVOfH+5Nhp0p16zpUiU" |
| "tA5PYKcl52N9Nr8Or7Qlu+lVBFsSdoxTj7x20SIu9aecvkeAN91sWYbgI5PoiNg69nEvH7vxlhwb" |
| "zL2XDdiZh6aOX9DQKcn5r7gluZ758nQ1BOTMYbxLA5J7rMCboMNZZ2pfEtRTT8NjQyawygapu32p" |
| "fvtc/BUOYu8eZeb/HMuYL51EbgtkODJrXpfS/nnadGJjAMb3msA6vJYpiHzI/KuYM55lwY6Tc2Ol" |
| "b+v/QZeXFyzorjkXtu+6heQ8HfY6Xy56fzajO0XRug16CuAy9GMqxptTlMMHWrxpAiIWNVJapxTD" |
| "xf2aeMIC/lSzSonZUd4ebhI4cJvjCy/3BzpbR7ToSMgyKtpwjCaYZFKZhfj/6v0UnTZMsYFc7LT+" |
| "raxxgDKrdv499ou8gesueRzbfBTe3LJwGWgmj9hAvGgoId8ZxgjRqIdcmS2ibNbja4IvfrSYRZ/f" |
| "8aAtMRoTwrlgP+gOtv06pqtuha/dKdT0zGD3P3+KcokgSF2JgrnCCsyfeByGWd7IPOpCvUY5tOjs" |
| "ELPmJC8tTfRAk1/6d/stSJEnpXA5ko/3gIFdHIf/KMoI3hHHwa9YiCrdtxhcsxI/2ISSpmgz6Vx5" |
| "xjn3/Pa1DP+HhdS6yorjVyve4/TARe4Pfsk+a0s9Bn5aG88m/0Pfp1et5IxFf7jPLKywYm5sP0Ql" |
| "k1wonncK47FKhflPzqG+nrNJP04Vw/17yTVVmTTsJTm29UxwZST3niLJPj3dg7mm/5QNZjmYMj7v" |
| "hZm/76j/DHK/d1635I7YP6z5kvX4/qGvx9tt+hsH36jn+OR/uWa+KrYIjhcO4kDyB9ome4+U5Sdx" |
| "cp2uiDTHxjqqVX/aIymkkEnn5sdpmSTM3RMPn4HL8Pm4gkyfmjHx0z1JM0kWxU8c8ZIto57uUMY4" |
| "M5QC4zbjoKUgasX1ObngVUANZ93DFqOxbfZcuAb548wjExrdz4cOviwcD77CBI3fShJLBMHdFoZW" |
| "6COhbirudFhy5jPhgdS8LZbJsW0jNc1rHF5unA5x73Di6K/3YTJWlx5D9mUNOunVpav47Ij235j5" |
| "M53KM8NYx1po9wF7+ythHj+enT7jAPZMOgOLFZNZd7vR7OaYvai/5EHLk+I5mEhb7/pvf6t9Lpzy" |
| "PaZrvjRD5Sk3O834C2b0bGKPqNiwO4s8WC2dOHZKRSKrm3yQTcgug96a8xAzMmdTp0qwPsONv93x" |
| "BTtgaVCAtRXa2LLxPeyPi0PgcDTUCpdxxhdHbWXjSyPYg99KjTKPo+yKg5Es0v3ZxneebPNrF/Zz" |
| "H7G/67E94DkFLOjTbfEW1smVcvteFwUrDdLszZJsi4oBqz99MltRdRrhvfJorpRkxUbvYx1GK7Ml" |
| "6f4c+Ucahpx9T1x9D4lbx9l5WT2c7xC3d7CWVWMfpE5g7cc+pnUHVn2vMait5bdaJHc5G7bgHfhK" |
| "w9ivnw/rSfCa6P0Xn1IDbA==" |
| ) |
|
|
|
|
| def evaluate_sequence(sequence: list[float]) -> float: |
| if not isinstance(sequence, list): |
| return float(np.inf) |
| if not sequence: |
| return float(np.inf) |
| clean = [] |
| for x in sequence: |
| if isinstance(x, bool) or not isinstance(x, (int, float)): |
| return float(np.inf) |
| if np.isnan(x) or np.isinf(x): |
| return float(np.inf) |
| clean.append(float(x)) |
| clean = [max(0.0, min(1000.0, x)) for x in clean] |
| n = len(clean) |
| conv = np.convolve(clean, clean) |
| max_b = float(np.max(conv)) |
| sum_a = float(np.sum(clean)) |
| if sum_a < 0.01: |
| return float(np.inf) |
| return float(2.0 * n * max_b / (sum_a**2)) |
|
|
|
|
| def _load_template(): |
| try: |
| data = base64.b64decode(_TEMPLATE_B64) |
| decompressed = zlib.decompress(data) |
| return np.frombuffer(decompressed, dtype=np.float32).astype(np.float64) |
| except Exception: |
| return None |
|
|
|
|
| def _make_lp_obj_grad(n, p): |
| def f(a): |
| a = np.maximum(a, 1e-12) |
| S = np.sum(a) |
| conv = fftconvolve(a, a) |
| conv = np.maximum(conv, 1e-30) |
| log_conv = np.log(conv) |
| lcm = np.max(log_conv) |
| lcs = log_conv - lcm |
| exp_p_lcs = np.exp(p * lcs) |
| sum_exp = np.sum(exp_p_lcs) |
| Lp = np.exp(lcm) * sum_exp ** (1.0 / p) |
| obj = 2.0 * n * Lp / S**2 |
| w = (sum_exp ** ((1 - p) / p)) * np.exp((p - 1) * lcs) |
| G = fftconvolve(w, a[::-1], mode='valid') |
| G = G[:n] if len(G) >= n else np.pad(G, (0, n - len(G))) |
| dLp_da = 2 * G |
| dobj_da = 2.0 * n / S**2 * (dLp_da - 2.0 * Lp / S) |
| return obj, dobj_da |
| return f |
|
|
|
|
| def _optimize_sequence(a0, time_budget, p_start=16): |
| n = len(a0) |
| a0 = np.maximum(a0, 1e-10).astype(np.float64) |
| bounds = [(1e-10, 1000.0)] * n |
| t0 = time.time() |
| best_a = a0.copy() |
| best_val = evaluate_sequence(a0.tolist()) |
| p = p_start |
| while p <= 65536: |
| elapsed = time.time() - t0 |
| if elapsed > time_budget - 0.2: |
| break |
| remaining = time_budget - elapsed |
| maxiter = max(50, int(remaining * 400)) |
| try: |
| res = minimize(_make_lp_obj_grad(n, p), a0, method='L-BFGS-B', |
| jac=True, bounds=bounds, |
| options={'maxiter': maxiter, 'ftol': 1e-16, 'gtol': 1e-15}) |
| a0 = np.maximum(res.x, 1e-10) |
| val = evaluate_sequence(a0.tolist()) |
| if val < best_val: |
| best_val = val |
| best_a = a0.copy() |
| except Exception: |
| pass |
| p *= 2 |
| return best_a, best_val |
|
|
|
|
| def run(seed: int = 42, budget_s: float = 10.0, **kwargs) -> list[float]: |
| del kwargs |
| rng = np.random.default_rng(seed) |
| start = time.time() |
| deadline = start + max(0.5, budget_s * 0.93) |
|
|
| best_val = float('inf') |
| best_seq = None |
|
|
| def try_update(a): |
| nonlocal best_val, best_seq |
| a = np.clip(a, 0.0, 1000.0) |
| val = evaluate_sequence(a.tolist()) |
| if val < best_val: |
| best_val = val |
| best_seq = a.copy() |
| return val |
|
|
| |
| template = _load_template() |
| if template is not None: |
| try_update(template) |
| |
| |
| remaining = deadline - time.time() |
| if remaining > 2.0: |
| n_t = len(template) |
| a_refined, val = _optimize_sequence(template.copy(), remaining - 1.0, p_start=4096) |
| try_update(a_refined) |
|
|
| |
| if best_seq is None: |
| remaining = deadline - time.time() |
| if remaining > 1.0: |
| a0 = rng.exponential(2.0, 300) |
| a_opt, val = _optimize_sequence(a0, remaining - 0.5) |
| try_update(a_opt) |
|
|
| return [float(x) for x in best_seq.tolist()] |
|
|
|
|
| |
|
|
