How to minimize an quadratic objective function with constraint violation using penalty method

[mahesh kumar]

I want to minimize an indefinite quadratic function with both equality and inequality constraints that may get violated depending on various factors. So I want to use l1 penalty method that penalizes the violating constraints.

for example,

I have modified an  example, to violate the constraints.

import osqp
import scipy.sparse as sparse
import numpy as np


# Define problem data
P = sparse.csc_matrix([[4., 1.], [1., 2.]])
q = np.array([1., 1.])
A = sparse.csc_matrix([[1., 0.], [0., 1.], [1., 0.], [0., 1.]])
l = np.array([0., 0., 0.2, 1.1])
u = np.array([1., 1., 0.2, 1.1])


# Create an OSQP object
prob = osqp.OSQP()


# Setup workspace and change alpha parameter
prob.setup(P, q, A, l, u, alpha=1.0)


# Solve problem
res = prob.solve()
print res.x

Obviously, this is an infeasible problem, so we need to change the objective function to penalize the error. So, I need help to formulate this problem that can be solved using osqp's python interface.

[Bartolomeo Stellato]

As I said in the github issue, the problem you posted can be easily modeled using CVXPY 1.0. This code works for the example below:

import cvxpy

import scipy.sparse as sparse

import numpy as np

# Define problem data

P = sparse.csc_matrix([[4., 1.], [1., 2.]])

q = np.array([1., 1.])

A = sparse.csc_matrix([[1., 0.], [0., 1.], [1., 0.], [0., 1.]])

l = np.array([0., 0., 0.2, 1.1])

u = np.array([1., 1., 0.2, 1.1])

mu = 1  # Penalty parameter

# Define CVXPY problem

x = cvxpy.Variable(2)

# Standard objective

objective = .5 * cvxpy.quad_form(x, P) + q * x 

# Penalty part of the objective

objective += mu * (cvxpy.norm1(A * x - u) + cvxpy.norm1(-A * x + l))

problem = cvxpy.Problem(cvxpy.Minimize(objective), [])

results = problem.solve(solver=cvxpy.OSQP, verbose=True)

The problem needs to be convex, otherwise OSQP cannot solve it. Indefinite quadratic forms cannot be handled.

Bartolomeo

[Bartolomeo Stellato]

Also, the quadratic form you are trying to minimize from the github issue is upper triangular

P = sparse.csc_matrix([[2., -4., 0.],
                       [0., 4., -4.],
                       [0., 0., 2.]])

It sounds a bit strange to me. Please check if it really represents your problem.

Bartolomeo

[mahesh kumar]

For eg,

following code works with the OSQP but not with the CVXPY. Can you please tell me, how can model the same problem to make make it work with cvxpy.

import cvxpy

import scipy.sparse as sparse
import numpy as np

import osqp


# Define problem data

P = sparse.csc_matrix([[2., -4., 0.],
                       [0., 4., -4.],

                       [0., 0., 2.]])
q = np.array([1., 1., 0.])
A = sparse.csc_matrix([[-1., 1., 0.],
                       [0., -1., 1.],
                       [1., 0., 0.],
                       [0., 0., 1.],
                       [1., 0., 0.],
                       [0., 1., 0.],
                       [0., 0., 1.]])
l = np.array([-0.3, -0.3, 0.2, 0.7, -0.3, -0.3, -0.3])
u = np.array([0.3, 0.3, 0.2, 0.7, 1.1, 1.1, 1.1])

mu = 1  # Penalty parameter

mu = 15  # Penalty parameter

P_csc =  .5 * (P + P.transpose())

m = osqp.OSQP()
m.setup(P=P_csc, q=q, A=A, l=l, u=u, max_iter = 1000, verbose=True)
# m.warm_start(x=initialX)

results = m.solve()  # this works
print results.x

# Define CVXPY problem
x = cvxpy.Variable(P.shape[1])

# Standard objective
objective = cvxpy.quad_form(x, P) + q * x

# Penalty part of the objective
objective += mu * (cvxpy.norm1(A * x - u) + cvxpy.norm1(-A * x + l))


problem = cvxpy.Problem(cvxpy.Minimize(objective), [])

results = problem.solve(solver=cvxpy.OSQP, verbose=False)
print results
print x.value

[Bartolomeo Stellato]

I seriously doubt this code can work with OSQP. Please check my previous replies. The matrix P has to be symmetric positive semidefinite.

[mahesh kumar]

I use this,

P_csc =  .5 * (P + P.transpose())

to convert P to be symmetric positive semidefinite. Its already there in the code.

But same P_csc is not working with CVXPY. 

[mahesh kumar]

Yes, it is my problem representation and it is indefinite, which grows with various factors

On Wednesday, November 1, 2017 at 11:56:34 AM UTC+1, Bartolomeo Stellato wrote:

[Bartolomeo Stellato]

You were defining P_csc and not using it. The following code should work

import cvxpy

import osqp

import scipy.sparse as sparse

import numpy as np

# Define problem data

P = sparse.csc_matrix([[2., -4., 0.],

                       [0., 4., -4.],

                       [0., 0., 2.]])

# Make symmetric and not indefinite

P = .5 * (P + P.T) + 1e-08 * sparse.eye(3)

q = np.array([1., 1., 0.])

A = sparse.csc_matrix([[-1., 1., 0.],

                       [0., -1., 1.],

                       [1., 0., 0.],

                       [0., 0., 1.],

                       [1., 0., 0.],

                       [0., 1., 0.],

                       [0., 0., 1.]])

l = np.array([-0.3, -0.3, 0.2, 0.7, -0.3, -0.3, -0.3])

u = np.array([0.3, 0.3, 0.2, 0.7, 1.1, 1.1, 1.1])

mu = 15  # Penalty parameter

m = osqp.OSQP()

m.setup(P=P, q=q, A=A, l=l, u=u, verbose=True)

results_osqp = m.solve()  # this works

# Define CVXPY problem

x = cvxpy.Variable(P.shape[1])

# Standard objective

objective = cvxpy.quad_form(x, P) + q * x

# Penalty part of the objective

objective += mu * (cvxpy.norm1(A * x - u) + cvxpy.norm1(-A * x + l))

problem = cvxpy.Problem(cvxpy.Minimize(objective))

objective_osqp_cvxpy = problem.solve(solver=cvxpy.OSQP, verbose=True)

print "Result OSQP Python x =", np.round(results_osqp.x, 3)

print "Results OSQP CVXPY x =", np.round(x.value, 3)

[mahesh kumar]

Thank you so much, now it works.

This, 

P = .5 * (P + P.T) + 1e-08 * sparse.eye(3)

did a trick. 

But can I know, why without adding 1e-08 * sparse.eye(3), same code didn't work?

[Bartolomeo Stellato]

It seems that it is a bug with the current version of cvxpy 1.0. If you compute the eigenvalues of P in Python, one of them very small (in the order of 1e-16), but negative.

The actual eivenvalue is 0, which is compatible with our formulation.

Even though the problem is convex, cvxpy raises an error. I have reported it here: https://github.com/cvxgrp/cvxpy/issues/407

Bartolomeo

--
You received this message because you are subscribed to the Google Groups "OSQP" group.
To unsubscribe from this group and stop receiving emails from it, send an email to osqp+unsubscribe@googlegroups.com.
To post to this group, send email to os...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/osqp/26ad2b60-08ac-495d-8c4b-7be765513c65%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[mahesh kumar]

Oh, good to know. Hope they resolve it with next release.

Thank you so much for replying. 

To unsubscribe from this group and stop receiving emails from it, send an email to osqp+uns...@googlegroups.com.

To post to this group, send email to os...@googlegroups.com.