<s> """<STR_LIT>""" <EOL> from __future__ import division , print_function , absolute_import <EOL> import numpy as np <EOL> from numpy . linalg import norm , lstsq <EOL> from scipy . optimize import OptimizeResult <EOL> from . common import print_header_linear , print_iteration_linear <EOL> def compute_kkt_optimality ( g , on_bound ) : <EOL> """<STR_LIT>""" <EOL> g_kkt = g * on_bound <EOL> free_set = on_bound == <NUM_LIT:0> <EOL> g_kkt [ free_set ] = np . abs ( g [ free_set ] ) <EOL> return np . max ( g_kkt ) <EOL> def bvls ( A , b , x_lsq , lb , ub , tol , max_iter , verbose ) : <EOL> m , n = A . shape <EOL> x = x_lsq . copy ( ) <EOL> on_bound = np . zeros ( n ) <EOL> mask = x < lb <EOL> x [ mask ] = lb [ mask ] <EOL> on_bound [ mask ] = - <NUM_LIT:1> <EOL> mask = x > ub <EOL> x [ mask ] = ub [ mask ] <EOL> on_bound [ mask ] = <NUM_LIT:1> <EOL> free_set = on_bound == <NUM_LIT:0> <EOL> active_set = ~ free_set <EOL> free_set , = np . where ( free_set ) <EOL> r = A . dot ( x ) - b <EOL> cost = <NUM_LIT:0.5> * np . dot ( r , r ) <EOL> initial_cost = cost <EOL> g = A . T . dot ( r ) <EOL> cost_change = None <EOL> step_norm = None <EOL> iteration = <NUM_LIT:0> <EOL> if verbose == <NUM_LIT:2> : <EOL> print_header_linear ( ) <EOL> while free_set . size > <NUM_LIT:0> : <EOL> if verbose == <NUM_LIT:2> : <EOL> optimality = compute_kkt_optimality ( g , on_bound ) <EOL> print_iteration_linear ( iteration , cost , cost_change , step_norm , <EOL> optimality ) <EOL> iteration += <NUM_LIT:1> <EOL> x_free_old = x [ free_set ] . copy ( ) <EOL> A_free = A [ : , free_set ] <EOL> b_free = b - A . dot ( x * active_set ) <EOL> z = lstsq ( A_free , b_free ) [ <NUM_LIT:0> ] <EOL> lbv = z < lb [ free_set ] <EOL> ubv = z > ub [ free_set ] <EOL> v = lbv | ubv <EOL> if np . any ( lbv ) : <EOL> ind = free_set [ lbv ] <EOL> x [ ind ] = lb [ ind ] <EOL> active_set [ ind ] = True <EOL> on_bound [ ind ] = - <NUM_LIT:1> <EOL> if np . any ( ubv ) : <EOL> ind = free_set [ ubv ] <EOL> x [ ind ] = ub [ ind ] <EOL> active_set [ ind ] = True <EOL> on_bound [ ind ] = <NUM_LIT:1> <EOL> ind = free_set [ ~ v ] <EOL> x [ ind ] = z [ ~ v ] <EOL> r = A . dot ( x ) - b <EOL> cost_new = <NUM_LIT:0.5> * np . dot ( r , r ) <EOL> cost_change = cost - cost_new <EOL> cost = cost_new <EOL> g = A . T . dot ( r ) <EOL> step_norm = norm ( x [ free_set ] - x_free_old ) <EOL> if np . any ( v ) : <EOL> free_set = free_set [ ~ v ] <EOL> else : <EOL> break <EOL> if max_iter is None : <EOL> max_iter = n <EOL> max_iter += iteration <EOL> termination_status = None <EOL> optimality = compute_kkt_optimality ( g , on_bound ) <EOL> for iteration in range ( iteration , max_iter ) : <EOL> if verbose == <NUM_LIT:2> : <EOL> print_iteration_linear ( iteration , cost , cost_change , <EOL> step_norm , optimality ) <EOL> if optimality < tol : <EOL> termination_status = <NUM_LIT:1> <EOL> if termination_status is not None : <EOL> break <EOL> move_to_free = np . argmax ( g * on_bound ) <EOL> on_bound [ move_to_free ] = <NUM_LIT:0> <EOL> free_set = on_bound == <NUM_LIT:0> <EOL> active_set = ~ free_set <EOL> free_set , = np . nonzero ( free_set ) <EOL> x_free = x [ free_set ] <EOL> x_free_old = x_free . copy ( ) <EOL> lb_free = lb [ free_set ] <EOL> ub_free = ub [ free_set ] <EOL> A_free = A [ : , free_set ] <EOL> b_free = b - A . dot ( x * active_set ) <EOL> z = lstsq ( A_free , b_free ) [ <NUM_LIT:0> ] <EOL> lbv , = np . nonzero ( z < lb_free ) <EOL> ubv , = np . nonzero ( z > ub_free ) <EOL> v = np . hstack ( ( lbv , ubv ) ) <EOL> if v . size > <NUM_LIT:0> : <EOL> alphas = np . hstack ( ( <EOL> lb_free [ lbv ] - x_free [ lbv ] , <EOL> ub_free [ ubv ] - x_free [ ubv ] ) ) / ( z [ v ] - x_free [ v ] ) <EOL> i = np . argmin ( alphas ) <EOL> i_free = v [ i ] <EOL> alpha = alphas [ i ] <EOL> x_free *= <NUM_LIT:1> - alpha <EOL> x_free += alpha * z <EOL> if i < lbv . size : <EOL> on_bound [ free_set [ i_free ] ] = - <NUM_LIT:1> <EOL> else : <EOL> on_bound [ free_set [ i_free ] ] = <NUM_LIT:1> <EOL> else : <EOL> x_free = z <EOL> x [ free_set ] = x_free <EOL> step_norm = norm ( x_free - x_free_old ) <EOL> r = A . dot ( x ) - b <EOL> cost_new = <NUM_LIT:0.5> * np . dot ( r , r ) <EOL> cost_change = cost - cost_new <EOL> if cost_change < tol * cost : <EOL> termination_status = <NUM_LIT:2> <EOL> cost = cost_new <EOL> g = A . T . dot ( r ) <EOL> optimality = compute_kkt_optimality ( g , on_bound ) <EOL> if termination_status is None : <EOL> termination_status = <NUM_LIT:0> <EOL> return OptimizeResult ( <EOL> x = x , fun = r , cost = cost , optimality = optimality , active_mask = on_bound , <EOL> nit = iteration + <NUM_LIT:1> , status = termination_status , <EOL> initial_cost = initial_cost ) </s>
