Gabriele Farina - Central path and interior-point methods

MIT 6.7220/15.084 — Nonlinear Optimization Tue, Apr 23th 2024
Lecture 15
Central path and interior-point methods
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful for any
reports of typos.
Having laid the foundations of self-concordant functions, we are ready to see one of the most impor-
tant applications of these functions: interior-point methods.
Since we will be working extensively with self-concordant functions, we will make the blanket as-
sumption that Ω is an open, convex, nonempty set.
1 Path-following interior-point methods: chasing the central path
Consider a problem of the form
min
𝑥
s.t.
⟨𝑐, 𝑥⟩
𝑥 ∈ Ω,
where 𝑐 ∈ ℝ𝑛 and Ω denotes the closure of the open,
convex, and nonempty set Ω ⊆ ℝ𝑛.
Unlike iterative methods that project onto the feasible
set (such as for example the projected gradient descent
and the mirror descent algorithm), interior-point meth-
ods work by constructing a sequence of feasible points
in Ω, whose limit is the solution to the problem. To do
so, interior-point methods consider a sequence of opti-
mization problems with objective
𝛾⟨𝑐, 𝑥⟩ + 𝑓(𝑥),
where 𝛾 ≥ 0 is a parameter and 𝑓 is a strongly nonde-
generate self-concordant function on Ω.
Ω
Central path
𝜋(𝛾)
𝛾 = 0
𝛾 = +∞
Figure: The central path traced by
the sequence of solutions to the reg-
ularized problem arg min{−𝛾 ⋅ (𝑥 + 𝑦) +
𝑓(𝑥) : 𝑥 ∈ Ω}, for increasing values of 𝛾 ≥
0. The self-concordant function 𝑓 is the
polyhedral barrier. The red dot, corre-
sponding to the solution at 𝛾 = 0, is called
analytic center.
As we saw in Lecture 14, self-concordant functions shoot to infinity at the boundary of their domain,
and hence the minimizer of the self-concordant function will guarantee that the solution is in the
interior of the feasible set. The parameter 𝛾 is increased over time: as 𝛾 grows, the original objec-
tive function ⟨𝑐, 𝑥⟩ becomes the dominant term, and the solution to the regularized problem will
approach more and more the boundary. The path of solutions traced by the regularized problems is
called the central path.
Definition 1.1 (Central path). Let 𝑓 : Ω → ℝ be a lower-bounded strongly nondegenerate self-
concordant function. The central path is the curve 𝜋 parameterized over 𝛾 ≥ 0, traced by the
solutions¹ to the regularized optimization problem
𝜋(𝛾) ≔ arg min
𝑥
𝛾⟨𝑐, 𝑥⟩ + 𝑓(𝑥)
s.t. 𝑥 ∈ Ω.
¹Remember that lower-bounded self-concordant functions always have a unique minimizer, as seen in Theorem 2.5
of Lecture 14.
1.1 Barriers and their complexity parameter
As it turns out, the performance of path-following interior-point methods depends crucially on a
parameter of the strongly nondegenerate self-concordant function used, which is called the complex-
ity parameter of the function.
Definition 1.2 (Complexity parameter). The complexity parameter of a strongly nondegenerate
self-concordant function 𝑓 : Ω → ℝ is defined as the supremum of the intrinsic squared norm of
the second-order descent direction (Newton step) at any point in the domain, that is,
𝜃𝑓 ≔ sup
𝑥∈Ω
‖𝑛(𝑥)‖2
𝑥.
Theorem 1.1 ([NN94], Corollary 2.3.3). The complexity parameter of a strongly nondegenerate
self-concordant function is at least 1.
We reserve the term barrier for only those self-concordant functions for which the complexity para-
meter is finite, as we make formal next.
Definition 1.3 (Barrier function). A strongly nondegenerate self-concordant barrier (for us, sim-
ply barrier) is a strongly nondegenerate self-concordant function 𝑓 whose complexity parameter
is finite.
For example, in the case of the log barrier for the positive orthant, we can bound the complexity
parameter as follows.
Example 1.1. The logarithmic barrier for the positive orthant ℝ𝑛
>0, defined as
𝑓 : ℝ𝑛
>0 → ℝ where 𝑓(𝑥) = − ∑
𝑛
𝑖=1
log(𝑥𝑖)
has complexity parameter 𝜃𝑓 = 𝑛.
Solution . The Hessian of the logarithmic barrier is
∇2𝑓(𝑥) = diag( 1
𝑥2
1
, ..., 1
𝑥2
𝑛
),
and the Newton step is
𝑛(𝑥) = −[∇2𝑓 (𝑥)]−1∇𝑓 (𝑥) =
⎝
⎜⎛𝑥1
⋮
𝑥𝑛⎠
⎟⎞.
Hence, the intrinsic norm of the Newton step satisfies
‖𝑛(𝑥)‖2
𝑥 = 𝑛(𝑥)⊤[∇2𝑓 (𝑥)]𝑛(𝑥) = ∑
𝑛
𝑖=1
1
𝑥2
𝑖
𝑥2
𝑖 = 𝑛
as we wanted to show. □
However, not all self-concordant functions are barriers.
Example 1.2. The function 𝑓(𝑥) = 𝑥 − log(𝑥) is strongly nondegenerate self-concordant on Ω ≔
ℝ>0, but it is not a barrier.
Solution . We already know that 𝑓 is self-concordant, since − log(𝑥) is self-concordant (see Lec-
ture 14), and addition of linear functions to self-concordant functions preserve self-concordance.
The Hessian of 𝑓 is ∇2𝑓(𝑥) = 1/𝑥2, and the Newton step is correspondingly
𝑛(𝑥) = −[∇2𝑓 (𝑥)]−1∇𝑓 (𝑥) = −𝑥2(1 −
1
𝑥).
Hence, the intrinsic norm of the Newton step is
‖𝑛(𝑥)‖2
𝑥 = 1
𝑥2 [𝑥2(1 −
1
𝑥 )]
2
= 𝑥2 − 2𝑥 + 1,
which is unbounded as 𝑥 → +∞. □
1.2 Complexity parameter and optimality gap of the central path
The complexity parameter of a barrier function is a crucial quantity that appears in the analysis of
interior-point methods. We now begin with its first application in providing an upper bound on the
optimality gap of the regularized problem.
Theorem 1.2. Let 𝑓 : Ω → ℝ be a barrier function. For any 𝛾 > 0, the point 𝜋(𝛾) on the central
path (see Definition 1.1), satisfies the inequality
⟨𝑐, 𝜋(𝛾)⟩ ≤ ( min
𝑥∈Ω
⟨𝑐, 𝑥⟩) + 1
𝛾 𝜃𝑓 .
The above result ensures that when 𝛾 becomes large enough, then the points on the central path
become arbitrarily close to the optimal value of the original problem. With little extra work, the
same can be said for approximate solutions to 𝜋(𝛾).
Theorem 1.3. Let 𝑓 : Ω → ℝ be a barrier function. For any 𝛾 > 0, and point 𝑥 ∈ Ω such that
‖𝑥 − 𝜋(𝛾)‖𝑥 ≤ 1
6 ,
⟨𝑐, 𝑥⟩ ≤ ( min
𝑥∈Ω
⟨𝑐, 𝑥⟩) + 6
5𝛾 ⋅ 𝜃𝑓 .
2 The (short-step) barrier method
The idea of the short-step barrier method is to chase the central path closely at every iteration.
This is conceptually the simplest interior point method, with more advanced versions being the long-
step barrier method and the predictor-corrector barrier method, which is what is implemented in
commercial solvers such as CPLEX and Gurobi. We will use the term short-step barrier method and
barrier method interchangeably today.
Assume that we know an initial point 𝑥1 ∈ Ω that is close to the point 𝜋(𝛾1) on the central path,
for some value of 𝛾1 > 0. The barrier algorithm now increases the parameter 𝛾1 to a value 𝛾2 = 𝛽𝛾1
(where 𝛽 > 1), and applies Newton’s method to approximate the solution 𝜋(𝛾2). As long as 𝑥1 was
sufficiently close to 𝜋(𝛾1), we expect that in switching from 𝛾1 to 𝛾2, the point 𝑥1 will still be in
the region of quadratic convergence. In this case, Newton’s method converges so fast, that (as we
will see formally in the next subsection) a single Newton step is sufficient to produce a point 𝑥2 ≔
𝑥1 + 𝑛𝛾2 (𝑥1) that is again very close to the central path at 𝜋(𝛾2). For the choice of parameter 𝛾2,
the Newton step is in particular
𝑥2 ≔ 𝑥1 − [∇2𝑓(𝑥1)]−1(𝛾2𝑐 + ∇𝑓(𝑥1)),
since the objective function we apply the second-order descent direction is by definition the problem
min
𝑥
s.t.
𝛾2⟨𝑐, 𝑥⟩ + 𝑓(𝑥)
𝑥 ∈ Ω.
Continuing this process indefinitely, that is,
𝛾𝑡+1 ≔ 𝛽𝛾𝑡, 𝑥𝑡+1 ≔ 𝑥𝑡 − [∇2𝑓 (𝑥𝑡)]−1(𝛾𝑡+1𝑐 + ∇𝑓 (𝑥𝑡))
we have the short-step barrier method.
2.1 Update of the parameter 𝛾
As we did in Lecture 14, we will denote the second-order direction of descent—that is, the Newton
step—starting from a point 𝑥 using the letter 𝑛. However, since we are now dealing with a continuum
of objective functions parameterized on 𝛾, we will need to also specify what objective (that is, what
value of 𝛾) we are applying the Newton step to. For this reason, we will introduce the notation
𝑛𝛾 (𝑥) ≔ −[∇2𝑓(𝑥)]−1(𝛾𝑐 + ∇𝑓 (𝑥)).
The main technical hurdle in analyzing the short-step barrier method is to quantify the proximity of
the iterates to the central path. As is common with self-concordant functions, we will measure such
proximity using the lengths of the Newton steps: 𝑥𝑡 is near 𝜋(𝛾𝑡) in the sense that the intrinsic norm
of the Newton step 𝑛𝛾𝑡 (𝑥𝑡) is small (this should feel natural recalling Theorem 3.1 in Lecture 14).
How close to the central path is close enough, so that the barrier method using a single Newton
update per iteration is guaranteed to work? As we move our attention from the objective 𝛾𝑡⟨𝑐, 𝑥⟩ +
𝑓(𝑥) to the objective 𝛾𝑡+1⟨𝑐, 𝑥⟩ + 𝑓(𝑥), we can expect that distance to optimality of 𝑥𝑡 to 𝜋(𝛾𝑡+1)
increases by a certain amount compared to the distance from 𝑥𝑡 to 𝜋(𝛾𝑡). If this amount is not too
large, then we can hope to use Theorem 3.2 in Lecture 14 to “recover” in a single Newton step the
distance lost, and close the induction. The following theorem operationalizes the idea we just stated,
and provides a concrete quantitative answer to what “close enough” means. In particular, we will
show that ‖𝑛𝛾𝑡 (𝑥𝑡)‖𝑥𝑡
≤ 1
9 is enough.
Theorem 2.1. If 𝑥𝑡 is close to the central path, in the sense that ‖𝑛𝛾𝑡 (𝑥𝑡)‖𝑥𝑡
≤ 1
9 , then by setting
𝛾𝑡+1 ≔ 𝛽𝛾𝑡 with 𝛽 ≔ (1 + 1
8√𝜃𝑓
),
the same proximity is guaranteed at time 𝑡 + 1, that is, ‖𝑛𝛾𝑡+1 (𝑥𝑡+1)‖𝑥𝑡+1
≤ 1
9 .
Proof . We need to go from a statement pertaining ‖𝑛𝛾𝑡 (𝑥𝑡)‖𝑥𝑡
to one pertaining ‖𝑛𝛾𝑡+1 (𝑥𝑡+1)‖𝑥𝑡+1
.
We will do so by combining two facts:
1. First, observe the equality (valid for all 𝛾𝑡+1 and 𝛾𝑡)
𝑛𝛾𝑡+1 (𝑥𝑡) = −[∇2𝑓 (𝑥𝑡)]−1(𝛾𝑡+1𝑐 + ∇𝑓 (𝑥𝑡))
= − 𝛾𝑡+1
𝛾𝑡
[∇2𝑓 (𝑥𝑡)]−1(𝛾𝑡𝑐 +
𝛾𝑡
𝛾𝑡+1
∇𝑓(𝑥𝑡))
= − 𝛾𝑡+1
𝛾𝑡
[∇2𝑓 (𝑥𝑡)]−1(𝛾𝑡𝑐 + ∇𝑓 (𝑥𝑡)) +
𝛾𝑡+1 − 𝛾𝑡
𝛾𝑡
[∇2𝑓 (𝑥𝑡)]−1∇𝑓 (𝑥𝑡)
= 𝛾𝑡+1
𝛾𝑡
𝑛𝛾𝑡 (𝑥𝑡) + (
𝛾𝑡+1
𝛾𝑡
− 1)[∇2𝑓 (𝑥𝑡)]−1∇𝑓 (𝑥𝑡).
Using the triangle inequality for norm ‖⋅‖𝑥𝑡
and plugging in the hypotheses of the statement,
we get
‖𝑛𝛾𝑡+1 (𝑥𝑡)‖𝑥𝑡
≤ 𝛾𝑡+1
𝛾𝑡
‖𝑛𝛾𝑡 (𝑥𝑡)‖𝑥𝑡
+ |𝛾𝑡+1
𝛾𝑡
− 1| ⋅ ‖[∇2𝑓 (𝑥𝑡)]−1∇𝑓 (𝑥𝑡)‖𝑥𝑡
≤ 𝛾𝑡+1
𝛾𝑡
‖𝑛𝛾𝑡 (𝑥𝑡)‖𝑥𝑡
+ |𝛾𝑡+1
𝛾𝑡
− 1| ⋅ √𝜃𝑓
≤ 1
9 (1 + 1
8√𝜃𝑓
) + 1
8√𝜃𝑓
√𝜃𝑓
≤ 1
9 ⋅ (1 + 1
8) + 1
8 = 1
4 (since 𝜃𝑓 ≥ 1).
However, the left-hand side of the inequality is ‖𝑛𝛾𝑡+1 (𝑥𝑡)‖𝑥𝑡
and not ‖𝑛𝛾𝑡+1 (𝑥𝑡+1)‖𝑥𝑡+1
. This
is where the second step comes in.
2. To complete the bound, we will convert from ‖𝑛𝛾𝑡+1 (𝑥𝑡)‖𝑥𝑡
to ‖𝑛𝛾𝑡+1 (𝑥𝑡)‖𝑥𝑡+1
. To do so, re-
member that 𝑥𝑡+1 is obtained from 𝑥𝑡 by taking a Newton step. Hence, using Theorem 3.2
of Lecture 14, we have
‖𝑛𝛾𝑡+1 (𝑥𝑡+1)‖𝑥𝑡+1
≤
⎝
⎜⎜⎛ ‖𝑛𝛾𝑡+1 (𝑥𝑡)‖𝑥𝑡
1 − ‖𝑛𝛾𝑡+1 (𝑥𝑡)‖𝑥𝑡 ⎠
⎟⎟⎞
2
≤ (
1
4
1 − 1
4
)
2
= 1
9 .
This completes the proof. □
Remark 2.1. Remarkably, a safe increase in 𝛾 depends only on the complexity parameter 𝜃𝑓 of
the barrier, and not on any property of the function. For example, for a linear program
min
𝑥
s.t.
𝑐⊤𝑥
𝐴𝑥 = 𝑏
𝑥 ≥ 0 ∈ ℝ𝑛,
using the polyhedral barrier function, the increase in 𝛾 is independent of the number of con-
straints of the problem or the sparsity of 𝐴, and we can increase 𝛾𝑡+1 = 𝛾𝑡 ⋅ (1 + 1
8√𝑛 ).
The result in Theorem 2.1 shows that at every iteration, it is safe to increase 𝛾 by a factor of 1 +
1
8√𝜃𝑓
> 1, which leads to an exponential growth in the weight given to the objective function of the
problem.
Hence, combining the previous result with Theorem 1.2 we find the following guarantee.
Theorem 2.2. Consider running the short-step barrier method with a barrier function 𝑓 with
complexity parameter 𝜃𝑓 , starting from a point 𝑥1 close to 𝜋(𝛾1), i.e., ‖𝑛𝛾1 (𝑥1)‖𝑥1
≤ 1/9, for
some 𝛾1 > 0. For any 𝜀 > 0, after
𝑇 = ⌈10√𝜃𝑓 log(
6𝜃𝑓
5𝜀𝛾1
)⌉
iterations, the solution computed by the short-step barrier method guarantees an 𝜀-suboptimal
objective value ⟨𝑐, 𝑥𝑇 ⟩ ≤ ( min𝑥∈Ω⟨𝑐, 𝑥⟩) + 𝜀.
Proof . Since at every time the value of 𝛾 is increased by the quantity 1 + 1
8√𝜃𝑓
, the number of
iterations required to increase the value from 𝛾1 to any value 𝛾 is given by
𝑇 =
⎢
⎢
⎢
⎢
⎡ log( 𝛾
𝛾1
)
log(1 + 1
8√𝜃𝑓
)⎥
⎥
⎥
⎥
⎤
≤ ⌈log( 𝛾
𝛾1
)5
4 ⋅ 8√𝜃𝑓 ⌉ (since 1
log(1 + 𝑥) ≤ 5
4𝑥 for all 0 ≤ 𝑥 ≤ 1
2)
= ⌈10√𝜃𝑓 log(
𝛾
𝛾1
)⌉.
On the other hand, we know from Theorem 1.3 that the optimality gap of 𝜋(𝛾) is given by
6𝜃𝑓 /(5𝛾) as long as ‖𝑥𝑇 − 𝜋(𝛾𝑇 )‖𝑥𝑇
≤ 1
6 . This is indeed the case from Remark 3.2 of Lecture
14. So, to reach an optimality gap of 𝜀, we need 𝛾 = 6𝜃𝑓 /(5𝜀). Substituting this value into the
previous bound yields the statement. □
2.2 Finding a good initial point
The result in Theorem 2.2 shows that, as long as we know a point 𝑥1 that is “close” (in the formal
sense of Theorem 2.1) to the central path, for a parameter 𝛾1 that is not too small, then we can
guarantee an 𝜀-suboptimal solution in roughly √𝜃𝑓 log(1/𝜀) iterations.
■ The analytic center. Intuitively, one might guess that a good initial point for the algorithm would
be a point close to 𝜁 ≔ 𝜋(0) (the minimizer of 𝑓 on Ω), which is often called the analytic center of
Ω. Let’s verify that that is indeed the case. By definition, such a point satisfies ∇𝑓(𝜁) = 0, and so
we have that
𝑛𝛾 (𝜁) = −𝛾[∇2𝑓(𝜁)]−1𝑐 ⟹ ‖𝑛𝛾 (𝜁)‖𝜁 = 𝛾 ⋅ ‖[∇2𝑓(𝜁)]−1𝑐‖𝜁 .
Hence, 𝑥1 = 𝜁 is within proximity 1/9 (in the sense of Theorem 2.1) of the central path for the
value of
𝛾1 = 1
9 ‖[∇2𝑓(𝜁)]−1𝑐‖𝜁
.
The only thing left to check is that 𝛾1 is not excessively small, so that the number of iterations pre-
dicted in Theorem 2.2 is not too large. We now show that indeed we can upper bound ‖[∇2𝑓(𝜁)]−1𝑐‖𝜁 .
Theorem 2.3. Let 𝜁 be the minimizer of the barrier 𝑓 on Ω. Then,
‖[∇2𝑓 (𝜁)]−1𝑐‖𝜁 ≤ ⟨𝑐, 𝜁⟩ − min
𝑥∈Ω
⟨𝑐, 𝑥⟩.
(So, in particular, ‖[∇2𝑓 (𝜁)]−1𝑐‖𝜁 ≤ max𝑥∈Ω ⟨𝑐, 𝑥⟩ − min𝑥∈Ω ⟨𝑐, 𝑥⟩.)
Proof . The direction −[∇2𝑓 (𝜁)]−1𝑐 is a descent direction for 𝑐, since
⟨𝑐, −[∇2𝑓 (𝜁)]−1𝑐⟩ = −‖[∇2𝑓 (𝜁)]−1𝑐‖
2
𝜁
≤ 0.
Hence, as we consider points 𝑥(𝜆) ≔ 𝜁 − 𝜆 ⋅ [∇2𝑓 (𝜁)]−1𝑐 for 𝜆 ≥ 0 such that 𝑥(𝜆) ∈ Ω, we have
that the value of the objective ⟨𝑐, 𝑥(𝜆)⟩ decreases monotonically, and in particular
⟨𝑐, 𝑥(𝜆)⟩ = ⟨𝑐, 𝜁⟩ − 𝜆 ⋅ ‖[∇2𝑓 (𝜁)]−1𝑐‖
2
𝜁
,
which implies that
‖[∇2𝑓 (𝜁)]−1𝑐‖
2
𝜁
= ⟨𝑐, 𝜁⟩ − ⟨𝑐, 𝑥(𝜆)⟩
𝜆 ≤ ⟨𝑐, 𝜁⟩ − min𝑥∈Ω⟨𝑐, 𝑥⟩
𝜆 .
To complete the proof, it suffices to show that we can move in the direction of −[∇2𝑓 (𝜁)]−1𝑐
for a meaningful amount 𝜆. For this, we will use the property of self-concordant function that
the Dikin ellipsoid 𝑊 (𝜁) ≔ {𝑥 ∈ Ω : ‖𝑥 − 𝜁‖𝜁 < 1} ⊆ Ω. In particular, this implies that any 𝜆 ≥
0 such that
1 > ‖𝜁 − 𝑥(𝜆)‖𝜁 = 𝜆‖[∇2𝑓 (𝜁)]−1𝑐‖
𝜁
generates a point 𝑥(𝜆) ∈ Ω. So, we must have
‖[∇2𝑓 (𝜁)]−1𝑐‖
2
𝜁
≤ inf
⎩
{
⎨
{
⎧⟨𝑐, 𝜁⟩ − min𝑥∈Ω⟨𝑐, 𝑥⟩
𝜆 : 0 < 𝜆 < 1
‖[∇2𝑓 (𝜁)]−1𝑐‖𝜁 ⎭
}
⎬
}
⎫
= (⟨𝑐, 𝜁⟩ − min
𝑥∈Ω
⟨𝑐, 𝑥⟩)‖[∇2𝑓 (𝜁)]−1𝑐‖
𝜁
,
which implies the statement. □
So, we have shown the following.
Theorem 2.4 (The analytic center 𝜁 is a good initial point). Let 𝑓 be a barrier function with
complexity parameter 𝜃𝑓 . If the short-step barrier method is initialized at the analytic center 𝜁,
then the number of iterations required to obtain an 𝜀-suboptimal solution is bounded by
𝑇 = ⌈10√𝜃𝑓 log(
11 𝜃𝑓
𝜀 (⟨𝑐, 𝜁⟩ − min
𝑥∈Ω
⟨𝑐, 𝑥⟩))⌉.
■ Path switching and the auxiliary central path. In practice, we might not know where the analytic
center is. In this case, the typical solution is to first approximate the analytic center, and then start
the short step barrier method from there as usual.
To approximate the analytic center, one can use the auxiliary central path. The idea is the following:
start from an arbitrary point 𝑥′ ∈ Ω. Such a point is on the central path traced by the solutions to
𝜋′(𝜈) ≔ arg min
𝑥
−𝜈⟨∇𝑓(𝑥′), 𝑥⟩ + 𝑓(𝑥)
s.t. 𝑥 ∈ Ω.
Indeed, note that 𝑥′ is the solution for 𝜈 = 1, that is, 𝑥′ = 𝜋′(1).
We can then run the short-step barrier method chasing 𝜋′ in reverse. At every step, we will de-
crease the value of 𝜈 by a factor of 1 − 1
8√𝜃𝑓
. Once the value of 𝜈 is sufficiently small that
‖[∇𝑓(𝑥)]−1∇𝑓 (𝑥)‖𝑥 ≤ 1/6, we will have reached a point that is close to the analytic center, and we
can start the regular short-step barrier method for 𝜋(𝛾) from there. This technique is called path
switching, since we follow two central paths (one from 𝑥′ to the analytic center, and one from the
analytic center to the solution), switching around the analytic center which path to follow. [▷ Try
to work out the details and convince yourself this works!]
3 Further readings
The short book by Renegar, J. [Ren01] and the monograph by Nesterov, Y. [Nes18] (Chapter 5)
provide a comprehensive introduction to self-concordant functions and their applications in opti-
mization.
I especially recommend the book by Renegar, J. [Ren01] for a concise yet rigorous account.
[NN94] Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Pro-
gramming. Philadelphia, PA: Society for Industrial, Applied Mathematics, 1994. doi:
10.1137/1.9781611970791.
[Ren01] J. Renegar, A Mathematical View of Interior-point Methods in Convex Optimization.
Philadelphia, PA, USA: SIAM, 2001. doi: 10.1137/1.9780898718812.
[Nes18] Y. Nesterov, Lectures on Convex Optimization. Springer International Publishing, 2018.
[Online]. Available: https://link.springer.com/book/10.1007/978-3-319-91578-4

Content

Typo or question?

Metadata