6.10 Quadratic Optimization¶
MOSEK can solve quadratic and quadratically constrained problems, as long as they are convex. This class of problems can be formulated as follows:
Without loss of generality it is assumed that \(Q^o\) and \(Q^k\) are all symmetric because
This implies that a non-symmetric \(Q\) can be replaced by the symmetric matrix \(\half(Q+Q^T)\).
The problem is required to be convex. More precisely, the matrix \(Q^o\) must be positive semi-definite and the \(k\)th constraint must be of the form
with a negative semi-definite \(Q^k\) or of the form
with a positive semi-definite \(Q^k\). This implies that quadratic equalities are not allowed. Specifying a non-convex problem will result in an error when the optimizer is called.
A matrix is positive semidefinite if all the eigenvalues of \(Q\) are nonnegative. An alternative statement of the positive semidefinite requirement is
If the convexity (i.e. semidefiniteness) conditions are not met MOSEK will not produce reliable results or work at all.
6.10.1 Example: Quadratic Objective¶
We look at a small problem with linear constraints and quadratic objective:
The matrix formulation of (6.42) has:
with the bounds:
Please note the explicit \(\half\) in the objective function of (6.40) which implies that diagonal elements must be doubled in \(Q\), i.e. \(Q_{11}=2\) even though \(1\) is the coefficient in front of \(x_1^2\) in (6.42).
Setting up the linear part
The linear parts (constraints, variables, objective) are set up using exactly the same methods as for linear problems, and we refer to Sec. 6.1 (Linear Optimization) for all the details. The same applies to technical aspects such as defining an optimization task, retrieving the solution and so on.
Setting up the quadratic objective
The quadratic objective is specified using the function Task.put_q_obj. Since \(Q^o\) is symmetric only the lower triangular part of \(Q^o\) is inputted. In fact entries from above the diagonal may not appear in the input.
The lower triangular part of the matrix \(Q^o\) is specified using an unordered sparse triplet format (for details, see Sec. 15.1.4 (Matrix Formats)):
let qsubi = vec![ 0, 1, 2, 2 ];
let qsubj = vec![ 0, 1, 0, 2 ];
let qval = vec![ 2.0,0.2,-1.0,2.0 ];
Please note that
only non-zero elements are specified (any element not specified is 0 by definition),
the order of the non-zero elements is insignificant, and
only the lower triangular part should be specified.
Finally, this definition of \(Q^o\) is loaded into the task:
task.put_q_obj(&qsubi,&qsubj,&qval)?;
Source code
extern crate mosek;
use mosek::{Task,Boundkey,Streamtype,Solsta,Soltype};
const INF : f64 = 0.0;
const NUMCON : usize = 1; /* Number of constraints. */
const NUMVAR : usize = 3; /* Number of variables. */
fn main() -> Result<(),String> {
let c = vec![ 0.0,-1.0,0.0 ];
let bkc = vec![ mosek::Boundkey::LO ];
let blc = vec![ 1.0 ];
let buc = vec![ INF ];
let bkx = vec![ Boundkey::LO,
Boundkey::LO,
Boundkey::LO ];
let blx = vec![ 0.0,
0.0,
0.0 ];
let bux = vec![ INF,
INF,
INF ];
let aptrb = vec![ 0, 1, 2 ];
let aptre = vec![ 1, 2, 3 ];
let asub = vec![ 0, 0, 0 ];
let aval = vec![ 1.0, 1.0, 1.0 ];
let qsubi = vec![ 0, 1, 2, 2 ];
let qsubj = vec![ 0, 1, 0, 2 ];
let qval = vec![ 2.0,0.2,-1.0,2.0 ];
/* Create the optimization task. */
let mut task = match Task::new() {
Some(e) => e,
None => return Err("Failed to create task".to_string()),
}.with_callbacks();
task.put_stream_callback(Streamtype::LOG, |msg| print!("{}",msg))?;
//r = MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr);
task.append_cons(NUMCON as i32)?;
/* Append 'NUMVAR' variables.
* The variables will initially be fixed at zero (x=0). */
task.append_vars(NUMVAR as i32)?;
/* Optionally add a constant term to the objective. */
task.put_cfix(0.0)?;
for j in 0..NUMVAR
{
/* Set the linear term c_j in the objective.*/
task.put_c_j(j as i32,c[j])?;
/* Set the bounds on variable j.
* blx[j] <= x_j <= bux[j] */
task.put_var_bound(j as i32, /* Index of variable.*/
bkx[j], /* Bound key.*/
blx[j], /* Numerical value of lower bound.*/
bux[j])?; /* Numerical value of upper bound.*/
/* Input column j of A */
task.put_a_col(j as i32, /* Variable (column) index.*/
&asub[aptrb[j]..aptre[j]], /* Pointer to row indexes of column j.*/
&aval[aptrb[j]..aptre[j]])?; /* Pointer to Values of column j.*/
}
/* Set the bounds on constraints.
* for i=1, ...,NUMCON : blc[i] <= constraint i <= buc[i] */
for i in 0..NUMCON
{
task.put_con_bound(i as i32, /* Index of constraint.*/
bkc[i], /* Bound key.*/
blc[i], /* Numerical value of lower bound.*/
buc[i])?; /* Numerical value of upper bound.*/
/*
* The lower triangular part of the Q
* matrix in the objective is specified.
*/
/* Input the Q for the objective. */
task.put_q_obj(&qsubi,&qsubj,&qval)?;
}
let _trmcode = task.optimize()?;
/* Run optimizer */
/* Print a summary containing information
about the solution for debugging purposes*/
task.solution_summary(Streamtype::MSG)?;
let solsta = task.get_sol_sta(Soltype::ITR)?;
match solsta
{
Solsta::OPTIMAL =>
{
let mut xx = vec![0.0, 0.0, 0.0];
task.get_xx(Soltype::ITR, /* Request the interior solution. */
& mut xx[..])?;
println!("Optimal primal solution");
for j in 0..NUMVAR
{
println!("x[{}]: {}",j,xx[j]);
}
}
Solsta::DUAL_INFEAS_CER |
Solsta::PRIM_INFEAS_CER =>
{
println!("Primal or dual infeasibility certificate found.");
}
Solsta::UNKNOWN =>
{
println!("The status of the solution could not be determined.");
}
_ =>
{
println!("Other solution status.");
}
}
return Ok(());
} /* main */
6.10.2 Example: Quadratic constraints¶
In this section we show how to solve a problem with quadratic constraints. Please note that quadratic constraints are subject to the convexity requirement (6.41).
Consider the problem:
This is equivalent to
where
The linear parts and quadratic objective are set up the way described in the previous tutorial.
Setting up quadratic constraints
To add quadratic terms to the constraints we use the function Task.put_q_con_k.
{
let qsubi = &[0, 1, 2, 2 ];
let qsubj = &[0, 1, 2, 0 ];
let qval = &[-2.0, -2.0, -0.2, 0.2];
/* put Q^0 in constraint with index 0. */
task.put_q_con_k(0,
qsubi,
qsubj,
qval)?;
}
While Task.put_q_con_k adds quadratic terms to a specific constraint, it is also possible to input all quadratic terms in one chunk using the Task.put_q_con function.
Source code
here to download.¶extern crate mosek;
extern crate itertools;
use mosek::{Task,Boundkey,Objsense,Streamtype,Solsta,Soltype};
use itertools::izip;
const INF : f64 = 0.0;
fn main() -> Result<(),String> {
const NUMCON : i32 = 1; /* Number of constraints. */
const NUMVAR : i32 = 3; /* Number of variables. */
let c = [0.0, -1.0, 0.0];
let bkc = [Boundkey::LO];
let blc = [1.0];
let buc = [INF];
let bkx = [Boundkey::LO,
Boundkey::LO,
Boundkey::LO ];
let blx = [0.0,
0.0,
0.0 ];
let bux = [INF,
INF,
INF ];
let asub = [ &[0i32], &[0i32], &[0i32] ];
let aval = [ &[1.0], &[1.0], &[1.0] ];
let mut task = Task::new().unwrap().with_callbacks();
task.put_stream_callback(Streamtype::LOG, |msg| print!("{}",msg))?;
// Give MOSEK an estimate of the size of the input data.
// This is done to increase the speed of inputting data.
// However, it is optional.
// Append 'numcon' empty constraints.
// The constraints will initially have no bounds.
task.append_cons(NUMCON)?;
// Append 'numvar' variables.
// The variables will initially be fixed at zero (x=0).
task.append_vars(NUMVAR)?;
for (j,cj,bkj,blj,buj) in izip!(0..NUMVAR,c,bkx,blx,bux) {
// Set the linear term c_j in the objective.
task.put_c_j(j, cj)?;
// Set the bounds on variable j.
// blx[j] <= x_j <= bux[j]
task.put_var_bound(j, bkj, blj, buj)?;
}
for (j,asubj,avalj) in izip!(0..NUMVAR, asub, aval) {
/* Input column j of A */
task.put_a_col(j, /* Variable (column) index.*/
asubj, /* Row index of non-zeros in column j.*/
avalj)?; /* Non-zero Values of column j. */
}
// Set the bounds on constraints.
// for i=1, ...,numcon : blc[i] <= constraint i <= buc[i]
for (i,bki,bli,bui) in izip!(0..NUMCON,bkc,blc,buc) {
task.put_con_bound(i, bki, bli, bui)?;
}
{
// The lower triangular part of the Q
// matrix in the objective is specified.
let qosubi = &[ 0, 1, 2, 2 ];
let qosubj = &[ 0, 1, 0, 2 ];
let qoval = &[ 2.0, 0.2, -1.0, 2.0 ];
// Input the Q for the objective.
task.put_q_obj(qosubi, qosubj, qoval)?;
}
// The lower triangular part of the Q^0
// matrix in the first constraint is specified.
// This corresponds to adding the term
// x0^2 - x1^2 - 0.1 x2^2 + 0.2 x0 x2
{
let qsubi = &[0, 1, 2, 2 ];
let qsubj = &[0, 1, 2, 0 ];
let qval = &[-2.0, -2.0, -0.2, 0.2];
/* put Q^0 in constraint with index 0. */
task.put_q_con_k(0,
qsubi,
qsubj,
qval)?;
}
task.put_obj_sense(Objsense::MINIMIZE)?;
/* Solve the problem */
let _trm = task.optimize()?;
// Print a summary containing information
// about the solution for debugging purposes
task.solution_summary(Streamtype::MSG)?;
/* Get status information about the solution */
let solsta = task.get_sol_sta(Soltype::ITR)?;
let mut xx = vec![0.0; NUMVAR as usize];
task.get_xx(Soltype::ITR, // Interior solution.
xx.as_mut_slice())?;
match solsta {
Solsta::OPTIMAL => {
println!("Optimal primal solution");
for (j,xj) in izip!(0..NUMVAR,xx) {
println!("x[{}]: {}",j,xj);
}
},
Solsta::DUAL_INFEAS_CER|
Solsta::PRIM_INFEAS_CER =>
println!("Primal or dual infeasibility.\n"),
Solsta::UNKNOWN =>
println!("Unknown solution status.\n"),
_ =>
println!("Other solution status")
}
Ok(())
} /* Main */
