CVXMOD – Problems

Objectives

Before introducing problems, we briefly discuss problem objectives. These are formed by using the functions maximize(expr) or minimize(expr). The expr must have size (1, 1). The function classify(objv) will return convex objective or non-convex objective, as appropriate.

Allowing a slight abuse of terminology, the function value(objv) will evaluate and return the current value of the expr embedded within objv.

Objectives are not very useful by themselves — they are designed for attachment to problems.

>>> x = optvar('x', 3)
>>> maximize(sum(x))
<objective maximize(sum(x)); optvars: x>

>>> minimize(-sum(log(x)))
<objective minimize(-sum(log{x})); optvars: x>

>>> classify(maximize(sum(log(x))))
convex objective.

>>> classify(maximize(-sum(log(x))))
non-convex objective.

Problems

Problems are holders for specifying, testing and solving convex optimization problems. Only verifiably convex problems will be processed and sent to solvers. (We will later extend CVXMOD to handle non-verifiably convex problems.)

Problems have three different attributes. All are optional.

• objective may contain an objective created by minimize or maximize. If omitted (value None), the problem is a feasibility problem.

• constr may contain a list of optimization constraints.

Using print p where p is a problem will produce a nicely formatted description of the problem.

>>> A = param('A', value=randn(3, 5))
>>> b = param('b', value=randn(3, 1))
>>> x = optvar('x', 5)
>>> p = problem()

>>> p
<problem with no contraints and no assertions; optvars: None>

>>> p.objective = minimize(sum(x))
>>> p.constr = [A*x == b, x >= 0]
# could also specify in one pass with
#     p = problem(minimize(sum(x)), [A*x == b, x >= 0]).
>>> p
<problem with 1 constraint and no assertions; optvars: x>

>>> print p
minimize(sum(x)), subject to
  A*x == b
  x >= 0

Problem analysis

The following methods are provided by the problem class.

• validateassertions() returns True if all of a problem’s assertions evaluate to True, otherwise raising an AssertionError.

• validateparams() checks that all the params referred to in a problem have a specified value, and that the params and their values have consistent sizes, otherwise raising a ParamValueError.

• validateconvex() checks that a problem is convex, ie, that p.objective is empty (as in a feasibility problem), is minimization of a convex expression, or is maximization of a concave expression; and that all constraints are restrictions of optvars to convex sets. If these do not hold, it raises a ConvexityError.

• classify() (also callable in the form classify(prob)) tests a problem with all of the above methods, and provides a detailed textual summary. None of the aforementioned errors will be raised, making this suitable for interactive use.

Testing the value of a problem with value(prob) will return the current value of the optimization objective.

>>> A = param('A', value=randn(3, 5))
>>> b = param('b', value=randn(3, 1))
>>> x = optvar('x', 5)
>>> p = problem(minimize(sum(x)), [A*x == b, x >= 0])
>>> classify(p)
Assertion check: pass.
Parameter check: pass.
Convexity check: pass.

Detailed convexity check:
  convex objective: minimize(sum(x))
  convex constraint: A*x == b
  convex constraint: x >= 0

Solving problems

The problem class provides a solve() method. When solve() is called, CVXMOD uses the following procedure.

1. Run the validateassertions(), validateparams() and validateconvex() methods for the problem. Proceed only if all three return True.

2. Transform the problem into the (internal) standard form. (For debugging or demonstration purposes, printexpand() will demonstrate this step.)

3. Choose which solver to use. At this stage, there are two; a linear solver and a general nonlinear solver. Print a short message describing which solver is being used.

4. Call the appropriate solver in CVXOPT.

5. If solution succeeded (with status 'optimal'), update the value parameter of each optvar to reflect their optimal values. In all other cases, set the optvar values to None.

6. Return a short status string. Possible strings are 'optimal', 'primal infeasible', 'dual infeasible' and 'unknown'.

Variable values can be changed at any time. Thus, optimality of the value is guaranteed only immediately after the solve call returns 'optimal'. At that point, value(prob) will return the optimal value of the problem, value(constr) will return True for any constraint in the problem’s list of constraints, and value(varbl) will return the optimal value of any optvar referenced in the problem.

To silence extraneous output, use p.solve(True).

A = param(’A’, value=randn(50, 8)) b = param(’b’, value=rand(50, 1) + Arandn(8, 1)) x = optvar(’x’, 8) p = problem(maximize(sum(log(b - Ax))), >= -10, x <= 10) p.solve()

>>> A = param('A', value=randn(50, 8))
>>> b = param('b', value=rand(50, 1) + A*randn(8, 1))
>>> x = optvar('x', 8)

>>> p = problem()
>>> p.objective = maximize(sum(log(b - A*x)))
>>> p.solve()
using nonlinear solver.
     pcost       dcost       gap    pres   dres
 0:  1.0000e+00 -1.3466e+02  1e+02  1e+00  1e+00
 1: -9.8343e-02 -4.0252e+01  5e+01  5e-01  6e-01
 2:  2.6766e+00 -1.6423e+01  4e+01  4e-01  5e-01
 3:  1.0124e+01  6.5993e+00  3e+01  2e-01  4e-01
 4:  2.1403e+01  2.9461e+01  9e+00  6e-02  2e+00
 5:  2.6158e+01  3.2832e+01  7e+00  4e-02  1e+00
 6:  3.9929e+01  3.5893e+01  6e+00  9e-03  6e-01
 7:  3.9239e+01  3.8362e+01  1e+00  2e-03  2e-01
 8:  3.9131e+01  3.9060e+01  1e-01  3e-04  5e-02
 9:  3.9139e+01  3.9138e+01  3e-03  9e-06  2e-03
10:  3.9140e+01  3.9140e+01  3e-05  1e-07  2e-05
11:  3.9140e+01  3.9140e+01  3e-07  1e-09  2e-07
12:  3.9140e+01  3.9140e+01  3e-09  1e-11  2e-09
'optimal'

>>> print p
maximize(sum(log(b - A*x)))
optimization variables:
  <8x1 optvar symbol x>
parameters:
  <50x8 param symbol A>
  <50x1 param symbol b>

>>> q = problem()
>>> q.constr = [A*x <= b]
>>> print q
find x, subject to
  A*x <= b
optimization variables:
  <8x1 optvar symbol x>
parameters:
  <50x8 param symbol A>
  <50x1 param symbol b>