Given a vector decision variable x and vectors a, b of real scalars, I am trying to model the following quantity to be used inside an optimization objective:
b’*(abs(x - a).^(3/2))
I am wondering if cvx would represent the above quantity (i.e., in absolute value raised to (3/2)) as a power cone once Mosek is used as the solver? [mosek documentation](https://docs.mosek.com/modeling-cookbook/powo.html#powers)]
Or, any way around this would be appreciated!
You can do
b*pow_pos(abs(x-a),3/2)
which is convex (concave) if b is nonnegative (nonpositive).
I think CVX will reformulate this using rotated quadratic cones, perhaps along the lines of the Mosek Modeling Cookbook exposition https://docs.mosek.com/modeling-cookbook/powo.html
While this model can be solved using Mosek under CVX, .CVX will not exploit the native power cone capability of Mosek 9.0 (nor its native exponential cone capability, for that matter).
For the power 3/2 the rewriting it to using two quadratic cones works well. Using a true power cone instead is more convenient but will not buy you any performance in my experience.
The story is different for powers p/q where p and q are not small integers.
Thank you very much for your suggestion! I would be extremely appreciative if you can kindly show how I can re-write the expression Mark provided as two quadratic cones. Thank you.
The representation with two quadratic cones is in https://docs.mosek.com/modeling-cookbook/cqo.html#simple-sets-involving-power-functions
CVX will do something like it for you if you use power 3/2 and Mosek as solver, if I understand correctly.
Below you can see it implemented in Mosek Fusion around slide 25:
https://github.com/MOSEK/Courses/blob/master/2016_UPC/conic2.pdf
You can explicitly write your model in CVX using the quadratic cones. However, that is nor necessary. If you use pow_pos, as in my first post in this thread, CVX does the reformulation for you - that is part of the benefit of CVX - to save human effort and reduce human error propensity.
Many thanks! One quick Q: if I wanted to define a new variable w = x / sum(x) inside cvx_begin, then, how could I do that? Basically, I have constraints on w even though x is my decision variable. I was trying:
cvx_begin
variable x(n)
variable w(n);
maximize( - sum_square_abs(w) )
subject to
w == x / sum(x);
0 <= sum_square_abs(w) <= 1/10;
........
cvx_end
I seem to get the error
Disciplined convex programming error:
Invalid constraint: {constant} <= {convex}
Maybe because of the LHS of my constraint? Any suggestions on this? I also have additional objectives + constraints on x. Thank you.
How does x come into play? You (sort of) define w in terms of x, but x is not otherwise used at least in what you show of the program; and so is irrelevant, except for triggering a CVX violation.
CVX objects to 0 <= sum_square_abs(w) because it is a non-convex constraint. However, the lower bound of zero must be trivially satisfied, and therefore that constraint need not be included at all. Getting rid of that plus the two lines involving x, yields a rather trivial problem which CVX accepts and solves. Of course, I don’t know what’s in the part of the program you have not shown.
Presuming you really do need sum_square(x./sum(x)) <= 1/10, that is a non-convex constraint according to my calculations, and so you will be out of luck with CVX.
At this point, you will benefit from a careful reading of Why isn't CVX accepting my model? READ THIS FIRST! and http://cvxr.com/cvx/doc/
Thank you again for your help. Is there a way that I can specify custom tolerance for my soln? for example, I just need the solution to be accurate to the hundreds, tens place. The reason being that I run into Inaccurate/Solved situations. currently, I am using cvx_precision low but any other way to do this? I am calling for mosek as the solver. Should I place this new tolerance after cvx_begin or before? Thank you.
You can use cvx_solver_settings http://cvxr.com/cvx/doc/solver.html#advanced-solver-settings to specify values for any solver (Mosek) parameters.
However, if you only care about accuracy in the hundreds place, it suggests your problem is poorly scaled, which might be the root cause of why you are getting inaccurate solved. Changing solver tolerances might not do you much good, but re-scaling so that coefficients, objective value and argmin elements are either exactly zero or within a small number of orders of magnitude of one might help. Perhaps if you show all the Mosek solver output and solution, the Mosek guys (two of whom have already posted in this thread) can give you some more specific advice.
Thank you again for your help! Below is a sample output for a solved situation just to get an idea of the order of magnitude:
Calling Mosek 8.0.0.60: 28336 variables, 11637 equality constraints
For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------
NOTE: custom settings have been set for this solver.
------------------------------------------------------------
MOSEK Version 8.0.0.60 (Build date: 2017-3-1 13:09:33)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 11637
Cones : 6651
Scalar variables : 28336
Matrix variables : 0
Integer variables : 0
Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 3325
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.02
Lin. dep. - number : 0
Presolve terminated. Time: 0.03
Optimizer - threads : 4
Optimizer - solved problem : the primal
Optimizer - Constraints : 6649
Optimizer - Cones : 6651
Optimizer - Scalar variables : 25011 conic : 21684
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.05 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 1.55e+005 after factor : 3.57e+005
Factor - dense dim. : 75 flops : 3.19e+007
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 1.0e+000 3.9e+005 3.9e+005 0.00e+000 6.400210018e+009 -2.782299437e+003 1.0e+000 0.11
1 1.8e-001 7.2e+004 3.1e+004 -1.00e+000 6.396369143e+009 -3.930912055e+003 1.8e-001 0.17
2 6.0e-002 2.3e+004 5.7e+003 -9.98e-001 6.385384951e+009 -6.859354411e+003 6.0e-002 0.19
3 3.0e-002 1.2e+004 2.0e+003 -9.95e-001 6.366376179e+009 -1.119867508e+004 3.0e-002 0.22
4 1.3e-002 5.0e+003 5.8e+002 -9.88e-001 6.315284101e+009 -2.246086256e+004 1.3e-002 0.23
5 5.9e-003 2.3e+003 1.8e+002 -9.72e-001 6.213581898e+009 -4.499927636e+004 5.9e-003 0.27
6 1.2e-003 4.9e+002 1.9e+001 -9.41e-001 5.598613725e+009 -1.825256152e+005 1.2e-003 0.28
7 2.2e-004 8.4e+001 2.0e+000 -7.54e-001 3.520458318e+009 -6.502044719e+005 2.2e-004 0.31
8 3.4e-005 1.3e+001 3.7e-001 -1.02e-001 1.012272516e+009 -1.175907491e+006 3.4e-005 0.33
9 5.1e-006 2.0e+000 1.8e-001 7.70e-001 1.638053117e+008 -1.113784977e+006 5.1e-006 0.36
10 4.2e-007 1.6e-001 8.1e-002 1.27e+000 1.064602601e+007 -4.018514963e+005 4.2e-007 0.38
11 5.0e-008 2.0e-002 2.9e-002 1.15e+000 1.183400346e+006 -6.781713622e+004 5.0e-008 0.41
12 1.8e-009 7.1e-004 5.2e-003 1.02e+000 6.050470980e+003 -3.904609072e+004 1.8e-009 0.42
13 1.2e-009 4.6e-004 4.1e-003 9.95e-001 2.407058557e+003 -2.678061230e+004 1.2e-009 0.45
14 5.3e-010 2.1e-004 2.6e-003 1.00e+000 -1.283262097e+004 -2.577674210e+004 5.3e-010 0.47
15 1.3e-010 4.2e-005 1.1e-003 1.00e+000 -1.906667940e+004 -2.171202815e+004 1.1e-010 0.50
16 2.8e-011 1.1e-005 5.7e-004 1.02e+000 -1.949364083e+004 -2.015757276e+004 2.8e-011 0.52
17 1.7e-011 4.8e-006 3.8e-004 1.03e+000 -1.791555271e+004 -1.820435279e+004 1.2e-011 0.53
Interior-point optimizer terminated. Time: 0.55.
Optimizer terminated. Time: 0.56
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -1.7915552707e+004 nrm: 3e+003 Viol. con: 1e-005 var: 5e-006 cones: 4e-006
Dual. obj: -1.8204352666e+004 nrm: 5e+006 Viol. con: 0e+000 var: 2e+000 cones: 0e+000
Optimizer summary
Optimizer - time: 0.56
Interior-point - iterations : 17 time: 0.55
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5819.47
cvx_slvtol =
1.2207e-04
However, I am running the above with
cvx_precision low
cvx_solver_settings('MSK_DPAR_INTPNT_CO_TOL_REL_GAP', 1e-2)
Are there any other tolerances that I could add on?
(I see the full list here https://docs.mosek.com/9.0/toolbox/param-groups.html#doc-param-groups)
Finally, if there might be a way for me to reduce the tolerances from [ϵ^3/8,ϵ^1/4,ϵ^1/4] then would be much appreciated. Thank you.
Termination tolerances is discussed at
https://docs.mosek.com/9.0/toolbox/solving-conic.html
In general reducing the requested accuracy is not going to change much.
Finally, most likely the time cvx spends generating the model is bigger than the Mosek solution time. Have you verified that Mosek solution time is the bottleneck?