AI505/AI801, Optimization – Obligatory Assignment 2

Published

May 4, 2026

Case 1: Interior Point Methods for Linear Programming

Introduction

Interior Point Methods for linear programming and quadratic programming (e.g., Karmarkar-type methods) work differently from the simplex method. They do not jump from vertex to vertex on the boundary of the feasible region. Instead, they follow a central path inside the feasible region. They sole a barrier problem, which is a smooth approximation of the original problem, and the solution of the barrier problem converges to the solution of the original problem as the barrier parameter goes to zero. As we will see it is possible to rescale the problem so that a feasible point becomes available but starting from an arbitrary feasible point is often a poor choice because it might be close to the boundary, which leads to Newton steps become ill-conditioned, step sizes become tiny and convergence becomes slow.

The goal of this assignment is devising a method for finding a good starting point for interior-point methods by formulating, analyzing, and solving an optimization problem that identifies a “central” point in a polyhedron defined by linear inequalities.

Problem Setting

Let
\[ P = \{\vec x \in \mathbb{R}^n \mid \vec a_i^T \vec x \leq b_i,\; i = 1, \dots, m\} \]
be a nonempty, bounded polyhedron with nonempty interior.

Task 1

Propose a notion of a “center” of \(P\) by defining a point \(\vec x^\star \in P\) that satisfies the following qualitative properties:

  • It lies strictly inside \(P\) (i.e., satisfies all inequalities with strict inequality)
  • It is “far” from all constraint boundaries
  • It treats all constraints equally, i.e., it does not favor some constraints over others

Formulate an unconstrained optimization problem of the form: \[ \min_{\vec x \in \mathbb{R}^n} f(\vec x) \] whose solution corresponds to your notion of center.

Your objective function \(f(x)\) should:

  • penalize proximity to constraint boundaries,
  • diverge to infinity as \(x\) approaches any boundary,
  • be smooth on its domain,
  • be suitable for second-order methods.

Report the explicit expression of \(f(x)\), its domain of definition, and a short justification of your modelling choices.

Task 2 — Analytical Properties

Let \(f(\vec x)\) be your objective function.

  1. Compute: \(\nabla f(\vec x)\) and \(\nabla^2 f(\vec x)\)

  2. Prove that \(f(\vec x)\) is convex on its domain.

  3. Under the assumption that \(P\) is bounded with nonempty interior, argue that:

    • a minimizer exists
    • the minimizer is unique

Task 3

Task 3.1

Consider the polyhedron in \(\mathbb{R}^2\): \[ P = \{\vec x \in \mathbb{R}^2 \mid A \vec x \leq \vec b\} \] with \[ A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ -1 & 0 \\ 0 & -1\\ 1 & 1 \end{bmatrix},\quad \vec b = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\1.5\end{bmatrix} \]

  • Formulate the optimization problem you proposed in Task 1 for this specific polyhedron.

  • Use the Newton method to compute the center point \(\vec x^\star\).

  • Report the center point \(\vec x^\star\) and the minimum slack

  • Plot:

    • the feasible region.
    • the center point \(\vec x^\star\).

Task 3.2

Modify the last constraint \[\vec a_5^T \vec x\leq 1.5\] to \[\gamma\vec a_5^T \vec x\leq \gamma 1.5\] with \(\gamma=10\):

  • Verify that the feasible set is unchanged.
  • Recompute the center point.
  • Compare the new center point \(\vec x^\star_{\text{new}}\) with the previous one at Task 3.1 \(\vec x^\star_{\text{old}}\) and calculate the distance between them \(\|\vec x^\star_{\text{old}} - \vec x^\star_{\text{new}}\|\).
  • Plot both centers on the same figure as Task 3.1.
  • Extend this analysis to \(\gamma\in\{0.1,1,10,100\}\) and plot the centers for all \(\gamma\) on the same figure.

Task 3.3

Normalize all constraints to the form: \[ \vec a_i^T \vec x \leq 1,\quad i=1,\dots,m \]
and compare the center point obtained from the original formulation with the one obtained from the normalized formulation.

What do you observe? Can you explain the difference?

Task 4 — Numerical Solution, Implementation and Experiments

The center point is only well-defined if the feasible region is bounded as we assumed so far. If we drop the boundedness assumption, we can add to the normalized constraints other constraints of the form \(\|x_i\| \leq 1, \quad i=1..m\) to make the center point again well defined.

In this more general setting, the problem becomes finding the center point with variables \(\vec x\in \mathbb{R}^n\) and set of linear inequalities \[ \vec a_i^T \vec x \leq 1, \quad i=1,\dots,m, \quad |\vec x_i| \leq 1, \quad i=1,\dots,n. \]

Formulate this problem as an unconstrained optimization problem as in Task 1 and argue that the properties of Task 2 still hold.

Note that we can now choose \(\vec x(0) = \vec 0\) as our initial point.

In the following, you can generate instances of this problem by choosing \(\vec a_i\) from some distribution on \(\mathbb{R}^n\) with varying \(n\) and \(m\).

Design a gradient method and a Newton-type method to minimize \(f(x)\). Your methods should include:

  • Search direction
  • Backtracking line search
  • A mechanism to ensure feasibility (iterates remain in domain)
  • A stopping criterion based on optimality measures: ie, \(\|\nabla f(\vec x)\|_2\leq \eta\).

(You can reuse the implementation from Assignment 1 or from the exercise classes.)

For several instances of the problem of different sizes, assess the convergence behavior of gradient descent and Newton methods by plotting the objective function and step length versus iteration number.