Minimizing norm subject to linear constraint, using quadratic programming/minimization in Python

Question

I need to solve the following quadratic minimization subject to linear inequality constraint;

Where

||ξ|| is the Euclidean norm of ξ,

ξ and vk are vectors

and λk is a scalar.

I think this can be done with CVXOPT, but I don't have any experience with quadratic minimization so I am a bit lost, some help or just pointers would be greatly appreciated!.

solve ξ? = argmin||ξ|| subject to z.T ξ ≥ ?λk

question from:https://stackoverflow.com/questions/65837531/minimizing-norm-subject-to-linear-constraint-using-quadratic-programming-minimi

Answer 1

cvxopt.solvers.qp seems to be able to solve

1/2 x^T P x + q^T x

subject to

Ax ≤ B

For your case,

||ξ||² = ξ² = ξ^T I ξ = 1/2 ξ^T (2 × I) ξ + 0 x ξ

where I is an identity matrix. So your P and q are (2 × I) and 0 and A = -z_k, b = l_k.

With the given z_k and l_k (λ), you can solve matrix inequality by

import numpy
from cvxopt import matrix

P  = matrix([
    [2., 0., 0.],
    [0., 2., 0.],
    [0., 0., 2.]
])

q   = matrix([[0., 0., 0.]])

z_k = matrix([
    [1.],
    [2.],
    [3.]
])

l_k = matrix([4.])

from cvxopt import solvers

sol = solvers.qp(P, q, -z_k, l_k)

print(sol['x'])                 # argmin ξ
print(sol['primal objective'])  # min ξ^2

Check this.

If you need min ||ξ||, the norm:

import math
print(math.sqrt(sol['primal objective']))