1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
/*
* ECOS - Embedded Conic Solver.
* Copyright (C) 2012-2015 A. Domahidi [domahidi@embotech.com],
* Automatic Control Lab, ETH Zurich & embotech GmbH, Zurich, Switzerland.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
/* The KKT module.
* Handles all computation related to KKT matrix:
* - updating the matrix
* - its factorization
* - solving for search directions
* - etc.
*/
#ifndef __KKT_H__
#define __KKT_H__
#include "glblopts.h"
#include "spla.h"
#include "cone.h"
typedef struct kkt{
spmat* PKPt; /* Permuted KKT matrix, upper part only */
spmat* L; /* LDL factor L */
pfloat* D; /* diagonal matrix D */
pfloat* work1; /* workspace needed for factorization */
pfloat* work2; /* workspace needed for factorization */
pfloat* work3; /* workspace needed for factorization */
pfloat* work4; /* workspace needed for factorization */
pfloat* work5; /* workspace needed for factorization */
pfloat* work6; /* workspace needed for factorization */
pfloat* RHS1; /* Right hand side 1 */
pfloat* RHS2; /* Right hand side 2 */
pfloat* dx1; /* search direction of size n */
pfloat* dx2; /* search direction of size n */
pfloat* dy1; /* search direction of size p */
pfloat* dy2; /* search direction of size p */
pfloat* dz1; /* search direction of size m */
pfloat* dz2; /* search direction of size m */
idxint* P; /* permutation */
idxint* Pinv; /* reverse permutation */
idxint* PK; /* permutation of row indices of KKT matrix */
idxint* Parent; /* Elimination tree of factorization */
idxint* Sign; /* Permuted sign vector for regularization */
idxint* Pattern; /* idxint workspace needed for factorization */
idxint* Flag; /* idxint workspace needed for factorization */
idxint* Lnz; /* idxint workspace needed for factorization */
pfloat delta; /* size of regularization */
} kkt;
/* Return codes */
#define KKT_PROBLEM (0)
#define KKT_OK (1)
/* METHODS */
/**
* Factorization of KKT matrix. Just a convenient wrapper for the LDL call.
* The second argument delta determindes the threshold of dynamic regularization,
* while the last argument is the regularization parameter if it becomes active.
*
* If detailed profiling is turned on, the function returns the accumulated times
* for sparsity pattern computation in t1 and for numerical solve in t2.
*/
#if PROFILING > 1
idxint kkt_factor(kkt* KKT, pfloat eps, pfloat delta, pfloat *t1, pfloat *t2);
#else
idxint kkt_factor(kkt* KKT, pfloat eps, pfloat delta);
#endif
/**
* Solves the permuted KKT system and returns the unpermuted search directions.
*
* On entry, the factorization of the permuted KKT matrix, PKPt,
* is assumed to be up to date (call kkt_factor beforehand to achieve this).
* The right hand side, Pb, is assumed to be already permuted.
*
* On exit, the resulting search directions are written into dx, dy and dz,
* where these variables are permuted back to the original ordering.
*
* KKT->nitref iterative refinement steps are applied to solve the linear system.
*
* Returns the number of iterative refinement steps really taken.
*/
idxint kkt_solve(kkt* KKT,
spmat* A, spmat* G,
pfloat* Pb,
pfloat* dx, pfloat* dy, pfloat* dz,
idxint n, idxint p, idxint m,
cone* C,
idxint isinit,
idxint nitref);
/**
* Updates the permuted KKT matrix by copying in the new scalings.
*/
void kkt_update(spmat* PKP, idxint* P, cone *C);
/**
* Initializes the (3,3) block of the KKT matrix to produce the matrix
*
* [0 A' G']
* K = [A 0 0 ]
* [G 0 -I ]
*
* It is assumed that the A,G have been already copied in appropriately,
* and that enough memory has been allocated (this is done in preproc.c module).
*
* Note that the function works on the permuted KKT matrix.
*/
void kkt_init(spmat* PKP, idxint* P, cone *C);
#endif
|
