Class: LpSolver::QuadraticExpression

Inherits:
Object
  • Object
show all
Defined in:
lib/lpsolver/quadratic_expression.rb

Overview

Note:

The Hessian is stored in a normalized form where off-diagonal entries (i ≠ j) are stored once as [i, j, coefficient], and the LP format automatically applies the ½ factor.

Represents a quadratic expression: linear terms + quadratic terms.

Quadratic expressions extend linear expressions by including second-order terms (products of two variables). They are used to model quadratic objectives in Quadratic Programming (QP) problems, such as portfolio variance, least-squares residuals, or convex penalty functions.

A quadratic expression has the mathematical form:

c₀ + Σᵢ cᵢ·xᵢ + ½ Σᵢⱼ Qᵢⱼ·xᵢ·xⱼ

where c₀ is the constant, cᵢ are linear coefficients, and Q is the symmetric Hessian matrix of quadratic coefficients.

Examples:

Building a quadratic expression

x = model.add_variable(:x, lb: 0)
y = model.add_variable(:y, lb: 0)
quad = x * x + y * y + (x * y) * 2   # x² + 2xy + y² = (x+y)²
quad.linear_terms      # => {}
quad.quadratic_terms   # => [[0, 0, 1.0], [1, 1, 1.0], [0, 1, 2.0]]

Using in a QP model

model.minimize
model.set_objective(x * x + y * y)
solution = model.solve

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(linear_terms = {}, quadratic_terms = []) ⇒ QuadraticExpression

Creates a new QuadraticExpression.

Parameters:

  • linear_terms (Hash{Integer => Float}) (defaults to: {}) —

    Maps variable indices to linear coefficients.

  • quadratic_terms (Array<[Integer, Integer, Float]>) (defaults to: []) —

    Quadratic term pairs.



51
52
53
54
 
# File 'lib/lpsolver/quadratic_expression.rb', line 51

def initialize(linear_terms = {}, quadratic_terms = [])
  @linear_terms = linear_terms
  @quadratic_terms = quadratic_terms
end

Instance Attribute Details

#linear_terms ⇒ Hash{Integer => Float} (readonly)

Returns Maps variable indices to linear coefficients. The keys are internal variable indices, and the values are the coefficients of the linear terms (e.g., 2x + 3y → => 2.0, y_idx => 3.0).

Returns:

  • (Hash{Integer => Float}) —

    Maps variable indices to linear coefficients. The keys are internal variable indices, and the values are the coefficients of the linear terms (e.g., 2x + 3y → => 2.0, y_idx => 3.0).



36
37
38
 
# File 'lib/lpsolver/quadratic_expression.rb', line 36

def linear_terms
  @linear_terms
end

#quadratic_terms ⇒ Array<[Integer, Integer, Float]> (readonly)

Returns Quadratic term pairs. Each element is [var1_index, var2_index, coefficient], representing coefficient * var1 * var2. For diagonal terms (var1 == var2), this represents coefficient * var1².

Examples:

(x * x).quadratic_terms  # => [[0, 0, 1.0]]
(x * y).quadratic_terms  # => [[0, 1, 1.0]]

Returns:

  • (Array<[Integer, Integer, Float]>) —

    Quadratic term pairs. Each element is [var1_index, var2_index, coefficient], representing coefficient * var1 * var2. For diagonal terms (var1 == var2), this represents coefficient * var1².



45
46
47
 
# File 'lib/lpsolver/quadratic_expression.rb', line 45

def quadratic_terms
  @quadratic_terms
end

Instance Method Details

#*(other) ⇒ QuadraticExpression

Multiplies this expression by a scalar.

Scales both linear coefficients and quadratic coefficients by the given factor.

Examples:

(x * x + y * y) * 2  # => QuadraticExpression with [[0,0,2.0], [1,1,2.0]]

Parameters:

  • scalar (Numeric) —

    The scalar multiplier.

  • other (Object)

Returns:



122
123
124
125
126
127
128
 
# File 'lib/lpsolver/quadratic_expression.rb', line 122

def *(other)
  s = other.to_f
  new_linear = @linear_terms.transform_values { |c| c * s }
  new_linear.reject! { |_, v| v.zero? }
  new_quad = @quadratic_terms.map { |i1, i2, c| [i1, i2, c * s] }
  QuadraticExpression.new(new_linear, new_quad)
end

#+(other) ⇒ QuadraticExpression

Adds another expression, variable, constant, or quadratic expression.

Examples:

Adding two quadratic expressions

(x * x) + (y * y)  # => QuadraticExpression with [[0,0,1.0], [1,1,1.0]]

Adding a linear expression

(x * x) + (x * 2 + 1)  # => QuadraticExpression with linear: {x => 2}, constant: 1

Parameters:

Returns:



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/lpsolver/quadratic_expression.rb', line 64

def +(other)
  if other.is_a?(Variable)
    new_linear = @linear_terms.dup
    new_linear[other.index] = (new_linear[other.index] || 0) + 1
    QuadraticExpression.new(new_linear, @quadratic_terms.dup)
  elsif other.is_a?(LinearExpression)
    new_linear = @linear_terms.dup
    other.terms.each { |idx, coeff| new_linear[idx] = (new_linear[idx] || 0) + coeff }
    QuadraticExpression.new(new_linear.reject { |_, v| v.zero? }, @quadratic_terms.dup)
  elsif other.is_a?(QuadraticExpression)
    new_linear = @linear_terms.dup
    other.linear_terms.each { |idx, coeff| new_linear[idx] = (new_linear[idx] || 0) + coeff }
    new_linear.reject! { |_, v| v.zero? }
    QuadraticExpression.new(new_linear, @quadratic_terms + other.quadratic_terms)
  else
    new_linear = @linear_terms.dup
    new_linear[0] = (new_linear[0] || 0) + other.to_f
    QuadraticExpression.new(new_linear, @quadratic_terms.dup)
  end
end

#-(other) ⇒ QuadraticExpression

Subtracts another expression, variable, constant, or quadratic expression.

Examples:

(x * x + y * y) - (x * y)  # => QuadraticExpression with [[0,0,1.0], [1,1,1.0], [0,1,-1.0]]

Parameters:

Returns:



91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/lpsolver/quadratic_expression.rb', line 91

def -(other)
  if other.is_a?(Variable)
    new_linear = @linear_terms.dup
    new_linear[other.index] = (new_linear[other.index] || 0) - 1
    QuadraticExpression.new(new_linear.reject { |_, v| v.zero? }, @quadratic_terms.dup)
  elsif other.is_a?(LinearExpression)
    new_linear = @linear_terms.dup
    other.terms.each { |idx, coeff| new_linear[idx] = (new_linear[idx] || 0) - coeff }
    QuadraticExpression.new(new_linear.reject { |_, v| v.zero? }, @quadratic_terms.dup)
  elsif other.is_a?(QuadraticExpression)
    new_linear = @linear_terms.dup
    other.linear_terms.each { |idx, coeff| new_linear[idx] = (new_linear[idx] || 0) - coeff }
    new_linear.reject! { |_, v| v.zero? }
    neg_quad = other.quadratic_terms.map { |i1, i2, c| [i1, i2, -c] }
    QuadraticExpression.new(new_linear, @quadratic_terms + neg_quad)
  else
    new_linear = @linear_terms.dup
    new_linear[0] = (new_linear[0] || 0) - other.to_f
    QuadraticExpression.new(new_linear, @quadratic_terms.dup)
  end
end

#-@ ⇒ QuadraticExpression

Returns a QuadraticExpression with all coefficients negated.

Examples:

-(x * x + y * y)  # => QuadraticExpression with [[0,0,-1.0], [1,1,-1.0]]

Returns:



135
136
137
138
139
140
 
# File 'lib/lpsolver/quadratic_expression.rb', line 135

def -@
  QuadraticExpression.new(
    @linear_terms.transform_values { |c| -c }.reject { |_, v| v.zero? },
    @quadratic_terms.map { |i1, i2, c| [i1, i2, -c] }
  )
end

#hessian_entries ⇒ Array<[Integer, Integer, Float]>

Converts quadratic terms to HiGHS Hessian entries.

Combines symmetric entries (e.g., x*y and y*x) and multiplies by 2 to account for the ½ factor in the HiGHS LP format:

[ 2·Qᵢⱼ·xᵢ·xⱼ ] / 2 = Qᵢⱼ·xᵢ·xⱼ

Examples:

(x * x).hessian_entries  # => [[0, 0, 2.0]]  → LP: [2x²]/2 = x²
(x * y + y * x).hessian_entries  # => [[0, 1, 4.0]]  → LP: [4xy]/2 = 2xy

Returns:

  • (Array<[Integer, Integer, Float]>) —

    Hessian entries as [var1_idx, var2_idx, coefficient]. Each coefficient represents the value that will be divided by 2 in the LP format.



153
154
155
156
157
158
159
160
161
162
 
# File 'lib/lpsolver/quadratic_expression.rb', line 153

def hessian_entries
  # Normalize: combine symmetric entries
  pairs = {}
  @quadratic_terms.each do |i1, i2, c|
    key = [i1, i2].sort
    pairs[key] = (pairs[key] || 0) + c
  end
  # Multiply by 2 to account for the "/ 2" in the LP format
  pairs.map { |key, c| [key[0], key[1], c * 2.0] }
end