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