ccevolve/tx_workspace/ac1_ours/program_v1.py

# EVOLVE-BLOCK-START
"""Optimized solver for the AC inequality task using Lp gradient descent."""

import time
import numpy as np
from scipy.signal import fftconvolve


def evaluate_sequence(sequence: list[float]) -> float:
    if not isinstance(sequence, list):
        return float(np.inf)
    if not sequence:
        return float(np.inf)
    clean: list[float] = []
    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 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 + 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

    def fast_obj(a):
        conv = fftconvolve(a, a)
        s = np.sum(a)
        if s < 1e-10:
            return float('inf')
        return 2.0 * len(a) * np.max(conv) / s**2

    def lp_gradient_descent(a, time_limit, p_start=4, p_end=32):
        """Projected Lp gradient descent on the convolution peak."""
        n = len(a)
        a = np.maximum(a, 1e-12).astype(np.float64)
        target_sum = np.sum(a)

        best_a = a.copy()
        best_obj = fast_obj(a)

        lr = 0.01
        no_improve = 0
        t_start = time.time()
        t_end = t_start + time_limit

        step = 0
        while time.time() < t_end:
            step += 1
            # Adaptive p
            progress = min(1.0, step / 2000.0)
            p = p_start + (p_end - p_start) * progress

            # Compute convolution
            conv = fftconvolve(a, a)
            conv = np.maximum(conv, 0)  # numerical safety

            # Lp weights
            conv_max = np.max(conv)
            if conv_max < 1e-20:
                break

            # Normalized weights for numerical stability
            w = (conv / conv_max) ** (p - 1)

            # Gradient: correlate(w, a) gives grad[i] = sum_k w[k]*a[k-i]
            a_rev = a[::-1]
            grad = fftconvolve(w, a_rev, mode='valid')

            if len(grad) != n:
                # Adjust if sizes don't match perfectly
                grad = grad[:n] if len(grad) > n else np.pad(grad, (0, n - len(grad)))

            # Project: remove mean to preserve sum
            grad -= np.mean(grad)

            # Normalize gradient
            gnorm = np.linalg.norm(grad)
            if gnorm < 1e-20:
                break
            grad = grad / gnorm

            # Line search with backtracking
            step_size = lr
            improved = False
            for _ in range(5):
                a_new = a - step_size * grad * np.sqrt(n)
                a_new = np.maximum(a_new, 1e-12)
                a_new = a_new / np.sum(a_new) * target_sum

                new_obj = fast_obj(a_new)
                if new_obj < best_obj:
                    a = a_new
                    best_a = a.copy()
                    best_obj = new_obj
                    lr = step_size * 1.05
                    improved = True
                    no_improve = 0
                    break
                step_size *= 0.5

            if not improved:
                no_improve += 1
                lr *= 0.8
                if no_improve > 50:
                    # Restart with perturbation
                    a = best_a + rng.normal(0, 0.01 * np.mean(best_a), n)
                    a = np.maximum(a, 1e-12)
                    a = a / np.sum(a) * target_sum
                    lr = 0.01
                    no_improve = 0

        return best_a, best_obj

    # Phase 1: Quick evaluation of many starting points
    candidates = []

    for n in [500, 1000, 2000, 4000]:
        j = np.arange(n, dtype=np.float64)

        # Best analytical: c + exp(beta * j/n)
        for beta in [3.0, 4.0, 5.0, 6.0, 8.0]:
            exp_part = np.exp(beta * j / n)
            for c_ratio in [0.1, 0.3, 0.5, 0.8, 1.0, 2.0]:
                c = c_ratio * np.max(exp_part) / beta
                a = c + exp_part
                candidates.append(a.copy())

        # Exponential only
        for beta in [0.8, 1.0, 1.2, 1.5, 2.0]:
            a = np.exp(beta * j / n)
            candidates.append(a.copy())

    # Evaluate all candidates quickly
    scored = []
    for a in candidates:
        val = fast_obj(a)
        scored.append((val, a))
    scored.sort(key=lambda x: x[0])

    # Phase 2: Optimize top candidates
    num_to_optimize = min(8, len(scored))
    time_per = max(0.3, (deadline - time.time() - 2.0) / num_to_optimize)

    for i in range(num_to_optimize):
        if time.time() > deadline - 2:
            break
        val_init, a_init = scored[i]
        a_opt, val_opt = lp_gradient_descent(a_init.copy(), time_per)
        try_update(a_opt)

    # Phase 3: Final refinement of best solution
    remaining = deadline - time.time()
    if remaining > 1.0 and best_seq is not None:
        # Try also changing length (upsample/downsample)
        a = best_seq.copy()
        for factor in [0.5, 0.75, 1.5, 2.0]:
            new_n = max(100, int(len(a) * factor))
            a_resized = np.interp(np.linspace(0, 1, new_n), np.linspace(0, 1, len(a)), a)
            a_opt, val = lp_gradient_descent(a_resized, min(0.5, remaining / 6))
            try_update(a_opt)
            if time.time() > deadline - 1:
                break

        remaining = deadline - time.time()
        if remaining > 0.5:
            a_opt, val = lp_gradient_descent(best_seq.copy(), remaining - 0.3, p_start=16, p_end=64)
            try_update(a_opt)

    return [float(x) for x in best_seq.tolist()]


# EVOLVE-BLOCK-END