vendor/scs/include/scs.h in scs-0.2.3 vs vendor/scs/include/scs.h in scs-0.3.0

- old
+ new

@@ -4,157 +4,317 @@ #ifdef __cplusplus extern "C" { #endif #include <string.h> -#include "glbopts.h" + #include "aa.h" +#include "glbopts.h" -/* private data structs (that you define) containing any necessary data to solve - * linear system, etc. this defines the matrix A, only the linear system solver - * interacts with this struct */ -typedef struct SCS_A_DATA_MATRIX ScsMatrix; -/* stores the necessary private workspace, only the linear system solver - * interacts with this struct */ -typedef struct SCS_LIN_SYS_WORK ScsLinSysWork; - -typedef struct SCS_PROBLEM_DATA ScsData; -typedef struct SCS_SETTINGS ScsSettings; -typedef struct SCS_SOL_VARS ScsSolution; -typedef struct SCS_INFO ScsInfo; -typedef struct SCS_SCALING ScsScaling; -typedef struct SCS_WORK ScsWork; -typedef struct SCS_RESIDUALS ScsResiduals; -typedef struct SCS_CONE ScsCone; +/** Struct containing acceleration workspace. Implemented by acceleration. */ typedef struct SCS_ACCEL_WORK ScsAccelWork; +/** Struct containing cone projection workspace. Implemented by cones. */ typedef struct SCS_CONE_WORK ScsConeWork; +/** Struct containing linear system workspace. Implemented by linear solver. */ +typedef struct SCS_LIN_SYS_WORK ScsLinSysWork; -/* struct containing problem data */ -struct SCS_PROBLEM_DATA { - /* these cannot change for multiple runs for the same call to SCS(init) */ - scs_int m, n; /* A has m rows, n cols */ - ScsMatrix *A; /* A is supplied in data format specified by linsys solver */ +/** This defines the data matrices which should be supplied in column compressed + * format with zero based indexing. + */ +typedef struct { + /** Matrix values, size: number of non-zeros. */ + scs_float *x; + /** Matrix row indices, size: number of non-zeros. */ + scs_int *i; + /** Matrix column pointers, size: `n+1`. */ + scs_int *p; + /** Number of rows. */ + scs_int m; + /** Number of columns. */ + scs_int n; +} ScsMatrix; - /* these can change for multiple runs for the same call to SCS(init) */ - scs_float *b, *c; /* dense arrays for b (size m), c (size n) */ +/** Struct containing all settings. */ +typedef struct { + /** Whether to heuristically rescale the data before solve. */ + scs_int normalize; + /** Initial dual scaling factor (may be updated if adaptive_scale is on). */ + scs_float scale; + /** Whether to adaptively update `scale`. */ + scs_int adaptive_scale; + /** Primal constraint scaling factor. */ + scs_float rho_x; + /** Maximum iterations to take. */ + scs_int max_iters; + /** Absolute convergence tolerance. */ + scs_float eps_abs; + /** Relative convergence tolerance. */ + scs_float eps_rel; + /** Infeasible convergence tolerance. */ + scs_float eps_infeas; + /** Douglas-Rachford relaxation parameter. */ + scs_float alpha; + /** Time limit in secs (can be fractional). */ + scs_float time_limit_secs; + /** Whether to log progress to stdout. */ + scs_int verbose; + /** Whether to use warm start (put initial guess in ScsSolution struct). */ + scs_int warm_start; + /** Memory for acceleration. */ + scs_int acceleration_lookback; + /** Interval to apply acceleration. */ + scs_int acceleration_interval; + /** String, if set will dump raw prob data to this file. */ + const char *write_data_filename; + /** String, if set will log data to this csv file (makes SCS very slow). */ + const char *log_csv_filename; +} ScsSettings; - ScsSettings *stgs; /* contains solver settings specified by user */ -}; +/** Struct containing problem data. */ +typedef struct { + /** A has `m` rows. */ + scs_int m; + /** A has `n` cols, P has `n` cols and `n` rows. */ + scs_int n; + /** A is supplied in CSC format (size `m` x `n`). */ + ScsMatrix *A; + /** P is supplied in CSC format (size `n` x `n`), must be symmetric positive + * semidefinite. Only pass in the upper triangular entries. If `P = 0` then + * set `P = SCS_NULL`. */ + ScsMatrix *P; + /** Dense array for b (size `m`). */ + scs_float *b; + /** Dense array for c (size `n`). */ + scs_float *c; +} ScsData; -/* ScsSettings struct */ -struct SCS_SETTINGS { - /* settings parameters: default suggested input */ +/** Cone data. Rows of data matrix `A` must be specified in this exact order. */ +typedef struct { + /** Number of linear equality constraints (primal zero, dual free). */ + scs_int z; + /** Number of positive orthant cones. */ + scs_int l; + /** Upper box values, `len(bu) = len(bl) = max(bsize-1, 0)`. */ + scs_float *bu; + /** Lower box values, `len(bu) = len(bl) = max(bsize-1, 0)`. */ + scs_float *bl; + /** Total length of box cone (includes scale `t`). */ + scs_int bsize; + /** Array of second-order cone constraints. */ + scs_int *q; + /** Length of second-order cone array `q`. */ + scs_int qsize; + /** Array of semidefinite cone constraints. */ + scs_int *s; + /** Length of semidefinite constraints array `s`. */ + scs_int ssize; + /** Number of primal exponential cone triples. */ + scs_int ep; + /** Number of dual exponential cone triples. */ + scs_int ed; + /** Array of power cone params, must be in `[-1, 1]`, negative values are + * interpreted as specifying the dual cone. */ + scs_float *p; + /** Number of (primal and dual) power cone triples. */ + scs_int psize; +} ScsCone; - /* these *cannot* change for multiple runs with the same call to SCS(init) */ - scs_int normalize; /* boolean, heuristic data rescaling: 1 */ - scs_float scale; /* if normalized, rescales by this factor: 5 */ - scs_float rho_x; /* x equality constraint scaling: 1e-3 */ +/** Contains primal-dual solution arrays or a certificate of infeasibility. + * Check the exit flag to determine whether this contains a solution or a + * certificate. */ +typedef struct { + /** Primal variable. */ + scs_float *x; + /** Dual variable. */ + scs_float *y; + /** Slack variable. */ + scs_float *s; +} ScsSolution; - /* these can change for multiple runs with the same call to SCS(init) */ - scs_int max_iters; /* maximum iterations to take: 2500 */ - scs_float eps; /* convergence tolerance: 1e-3 */ - scs_float alpha; /* relaxation parameter: 1.8 */ - scs_float cg_rate; /* for indirect, tolerance goes down like - (1/iter)^cg_rate: 2 */ - scs_int verbose; /* boolean, write out progress: 1 */ - scs_int warm_start; /* boolean, warm start (put initial guess in ScsSolution - struct): 0 */ - scs_int acceleration_lookback; /* memory for acceleration */ - const char* write_data_filename; /* string, if set will dump data */ -}; +/** Contains information about the solve run at termination. */ +typedef struct { + /** Number of iterations taken. */ + scs_int iter; + /** Status string, e.g. 'solved'. */ + char status[128]; + /** Status as scs_int, defined in glbopts.h. */ + scs_int status_val; + /** Number of updates to scale. */ + scs_int scale_updates; + /** Primal objective. */ + scs_float pobj; + /** Dual objective. */ + scs_float dobj; + /** Primal equality residual. */ + scs_float res_pri; + /** Dual equality residual. */ + scs_float res_dual; + /** Duality gap. */ + scs_float gap; + /** Infeasibility cert residual. */ + scs_float res_infeas; + /** Unbounded cert residual. */ + scs_float res_unbdd_a; + /** Unbounded cert residual. */ + scs_float res_unbdd_p; + /** Time taken for setup phase (milliseconds). */ + scs_float setup_time; + /** Time taken for solve phase (milliseconds). */ + scs_float solve_time; + /** Final scale parameter. */ + scs_float scale; + /** Complementary slackness. */ + scs_float comp_slack; + /** Number of rejected AA steps. */ + scs_int rejected_accel_steps; + /** Number of accepted AA steps. */ + scs_int accepted_accel_steps; + /** Total time (milliseconds) spent in the linear system solver. */ + scs_float lin_sys_time; + /** Total time (milliseconds) spent in the cone projection. */ + scs_float cone_time; + /** Total time (milliseconds) spent in the acceleration routine. */ + scs_float accel_time; +} ScsInfo; -/* NB: rows of data matrix A must be specified in this exact order */ -struct SCS_CONE { - scs_int f; /* number of linear equality constraints */ - scs_int l; /* length of LP cone */ - scs_int *q; /* array of second-order cone constraints */ - scs_int qsize; /* length of SOC array */ - scs_int *s; /* array of SD constraints */ - scs_int ssize; /* length of SD array */ - scs_int ep; /* number of primal exponential cone triples */ - scs_int ed; /* number of dual exponential cone triples */ - scs_float *p; /* array of power cone params, must be \in [-1, 1], - negative values are interpreted as specifying the - dual cone */ - scs_int psize; /* number of (primal and dual) power cone triples */ -}; +/* the following structs are not exposed to user */ -/* contains primal-dual solution arrays */ -struct SCS_SOL_VARS { - scs_float *x, *y, *s; -}; +/** Contains normalization variables. */ +typedef struct { + scs_float *D, *E; /* for normalization */ + scs_float primal_scale, dual_scale; +} ScsScaling; -/* contains terminating information */ -struct SCS_INFO { - scs_int iter; /* number of iterations taken */ - char status[32]; /* status string, e.g. 'Solved' */ - scs_int status_val; /* status as scs_int, defined in glbopts.h */ - scs_float pobj; /* primal objective */ - scs_float dobj; /* dual objective */ - scs_float res_pri; /* primal equality residual */ - scs_float res_dual; /* dual equality residual */ - scs_float res_infeas; /* infeasibility cert residual */ - scs_float res_unbdd; /* unbounded cert residual */ - scs_float rel_gap; /* relative duality gap */ +/** Holds residual information. */ +typedef struct { + scs_int last_iter; + scs_float xt_p_x; /* x' P x */ + scs_float xt_p_x_tau; /* x'Px * tau^2 *not* divided out */ + scs_float ctx; + scs_float ctx_tau; /* tau *not* divided out */ + scs_float bty; + scs_float bty_tau; /* tau *not* divided out */ + scs_float pobj; /* primal objective */ + scs_float dobj; /* dual objective */ + scs_float gap; /* pobj - dobj */ + scs_float tau; + scs_float kap; + scs_float res_pri; + scs_float res_dual; + scs_float res_infeas; + scs_float res_unbdd_p; + scs_float res_unbdd_a; + /* tau NOT divided out */ + scs_float *ax, *ax_s, *px, *aty, *ax_s_btau, *px_aty_ctau; +} ScsResiduals; + +/** Workspace for SCS */ +typedef struct { + /* x_prev = x from previous iteration */ + scs_int time_limit_reached; /* set if the time-limit is reached */ + scs_float *u, *u_t; + scs_float *v, *v_prev; + scs_float *rsk; /* rsk [ r; s; kappa ] */ + scs_float *h; /* h = [c; b] */ + scs_float *g; /* g = (I + M)^{-1} h */ + scs_float *lin_sys_warm_start; /* linear system warm-start (indirect only) */ + scs_float *rho_y_vec; /* vector of rho y parameters (affects cone project) */ + AaWork *accel; /* struct for acceleration workspace */ + scs_float *b_orig, *c_orig; /* original b and c vectors */ + scs_float *b_normalized, *c_normalized; /* normalized b and c vectors */ + scs_int m, n; /* A has m rows, n cols */ + ScsMatrix *A; /* (possibly normalized) A matrix */ + ScsMatrix *P; /* (possibly normalized) P matrix */ + ScsLinSysWork *p; /* struct populated by linear system solver */ + ScsScaling *scal; /* contains the re-scaling data */ + ScsConeWork *cone_work; /* workspace for the cone projection step */ + scs_int *cone_boundaries; /* array with boundaries of cones */ + scs_int cone_boundaries_len; /* total length of cones */ + /* normalized and unnormalized residuals */ + ScsResiduals *r_orig, *r_normalized; + /* track x,y,s as alg progresses, tau *not* divided out */ + ScsSolution *xys_orig, *xys_normalized; + /* updating scale params workspace */ + scs_float sum_log_scale_factor; + scs_int last_scale_update_iter, n_log_scale_factor, scale_updates; + /* aa norm stat */ + scs_float aa_norm; + scs_int rejected_accel_steps, accepted_accel_steps; scs_float setup_time; /* time taken for setup phase (milliseconds) */ - scs_float solve_time; /* time taken for solve phase (milliseconds) */ -}; + scs_float scale; /* current scale parameter */ + const ScsData *d; + const ScsCone *k; + const ScsSettings *stgs; /* contains solver settings specified by user */ +} ScsWork; -/* contains normalization variables */ -struct SCS_SCALING { - scs_float *D, *E; /* for normalization */ - scs_float mean_norm_row_a, mean_norm_col_a; -}; - /* - * main library api's: - * SCS(init): allocates memory etc (e.g., factorize matrix [I A; A^T -I]) - * SCS(solve): can be called many times with different b,c data per init call - * SCS(finish): cleans up the memory (one per init call) + * main library API */ -ScsWork *SCS(init)(const ScsData *d, const ScsCone *k, ScsInfo *info); -scs_int SCS(solve)(ScsWork *w, const ScsData *d, const ScsCone *k, - ScsSolution *sol, ScsInfo *info); + +/** + * Initialize SCS and allocate memory. + * + * All the inputs must be already allocated in memory before calling. + * + * It performs: + * - data and settings validation + * - problem data scaling + * - automatic parameters tuning (if enabled) + * - setup linear system solver: + * - direct solver: KKT matrix factorization is performed here + * - indirect solver: KKT matrix preconditioning is performed here + * - solve the linear system for the `r` vector in the paper. + * + * + * @param d Problem data. + * @param k Cone data. + * @param stgs SCS solver settings. + * @return Solver work struct. + */ +ScsWork *SCS(init)(const ScsData *d, const ScsCone *k, const ScsSettings *stgs); + +/** + * Solve quadratic cone program initialized by SCS(init). + * + * @param w Workspace allocated by init. + * @param sol Solver solution struct, will contain solution at termination. + * @param info Solver info reporting. + * @return Flag containing problem status (see \a glbopts.h). + */ +scs_int SCS(solve)(ScsWork *w, ScsSolution *sol, ScsInfo *info); + +/** + * Clean up allocated SCS workspace. + * + * @param w Workspace allocated by init, will be deallocated. + */ void SCS(finish)(ScsWork *w); -/* scs calls SCS(init), SCS(solve), and SCS(finish) */ -scs_int scs(const ScsData *d, const ScsCone *k, ScsSolution *sol, - ScsInfo *info); +/** + * Solve quadratic cone program defined by data in d and cone k. + * + * All the inputs must already be allocated in memory before calling. + * + * @param d Problem data. + * @param k Cone data. + * @param stgs SCS solver settings. + * @param sol Solution will be stored here. + * @param info Information about the solve will be stored here. + * @return Flag that determines solve type (see \a glbopts.h). + */ +scs_int scs(const ScsData *d, const ScsCone *k, const ScsSettings *stgs, + ScsSolution *sol, ScsInfo *info); + +/** + * Helper function to set all settings to default values (see \a glbopts.h). + * + * @param stgs Settings struct that will be populated. + */ +void SCS(set_default_settings)(ScsSettings *stgs); + const char *SCS(version)(void); size_t SCS(sizeof_int)(void); size_t SCS(sizeof_float)(void); - -/* the following structs are not exposed to user */ - -/* workspace for SCS */ -struct SCS_WORK { - /* x_prev = x from previous iteration */ - scs_float *u, *u_best, *v, *v_best, *u_t, *u_prev, *v_prev; - scs_float *h, *g, *pr, *dr; - scs_float g_th, sc_b, sc_c, nm_b, nm_c, best_max_residual; - scs_float *b, *c; /* (possibly normalized) b and c vectors */ - scs_int m, n; /* A has m rows, n cols */ - ScsMatrix *A; /* (possibly normalized) A matrix */ - ScsLinSysWork *p; /* struct populated by linear system solver */ - ScsSettings *stgs; /* contains solver settings specified by user */ - ScsScaling *scal; /* contains the re-scaling data */ - ScsConeWork *cone_work; /* workspace for the cone projection step */ - AaWork *accel; /* Struct for acceleration workspace */ -}; - -/* to hold residual information (unnormalized) */ -struct SCS_RESIDUALS { - scs_int last_iter; - scs_float res_dual; - scs_float res_pri; - scs_float res_infeas; - scs_float res_unbdd; - scs_float rel_gap; - scs_float ct_x_by_tau; /* not divided by tau */ - scs_float bt_y_by_tau; /* not divided by tau */ - scs_float tau; - scs_float kap; -}; #ifdef __cplusplus } #endif #endif