Project

Part of the grade (30%) in this course is based on a project to be handed in during the course. The project will consist of two unequal parts, dealing with unconstrained and constrained optimization. The first part will be published in the beginning of February, and the second part at the end of March.

You may work on the project either alone or in groups of up to three students.

The idea is that you are done with part 1 (unconstrained) roughly as we begin with constrained optimization (end of February/beginning of March), and with part 2 (constrained) by the end of this semester (beginning of May).

Tentatively the projects will be weighed as 10% and 20% in the final grade.

Project 1

The project description is here. We will deal with a least squares type problem which has a simple geometric interpretations, thereby making it very simple to understand and vizualize.

  • Deadline: 04.03.2018
  • You can work in groups of 1-3 students
  • You can use any programming language, but Python or Matlab is recommended (in particular, vizualization is easy)
  • Submit your reports via https://ovsys.math.ntnu.no/
  • Only one report per group, please!
  • Do not write your names in the report. Please mark them with either student or candidate numbers.
  • Please submit your report as PDF and zip all the accompanying code into one file.

Project 2

The project description is here. Basically we look at the same problem as in project 1, but with further restrictions on the eigenvalues.

  • Deadline: 04.05.2018
  • Otherwise: same guidelines as for project 1
  • By "the standard form" I mean equation 1.1 in the book by N&W
  • Slater's constraint qualification has been discussed during the lectures, but apparently it is not in N&W. It holds when the constraints \(c_i\) are concave for all \(i\in \mathcal{I}\), linear for all \(i \in \mathcal{E}\), and there is a feasible point \(\hat{x}\) such that \(c_i(\hat{x}) >0\), for all \(i\in \mathcal{I}\). Slater's CQ implies that the cone \(\mathring{\mathcal{F}}(x) = \{\, p \mid \nabla c_i(x)^\mathrm{T} p > 0, \forall i \in \mathcal{A}(x) \cap \mathcal{I}, \nabla c_i(x)^\mathrm{T} p = 0, \forall i \in \mathcal{E}\,\} \) is not empty for all feasible \(x\): indeed, it must at least contain the direction \(\hat{x}-x\). This cone is contained in the radial cone, which is in turn contained in the tangent cone, which in turn is contained in the cone of linearized feasible directions. Further, the closure of \(\mathring{\mathcal{F}}(x)\) equals \(\mathcal{F}(x)\), the cone of linearized feasible directions. Finally, the tangent cone is already closed, and therefore all the tangent cone must be equal with \(\mathcal{F}(x)\). Owing Farkas' lemma this implies the necessity of the KKT conditions for local optimality.
2018-04-09, Anton Evgrafov