KKTNecessarySufficientConditions.java

package org.drip.sample.optimizer;

import org.drip.function.definition.RdToR1;
import org.drip.function.rdtor1solver.*;
import org.drip.optimization.constrained.*;
import org.drip.service.env.EnvManager;

/*
 * -*- mode: java; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 */

/*!
 * Copyright (C) 2018 Lakshmi Krishnamurthy
 * Copyright (C) 2017 Lakshmi Krishnamurthy
 * Copyright (C) 2016 Lakshmi Krishnamurthy
 * 
 *  This file is part of DRIP, a free-software/open-source library for buy/side financial/trading model
 *  	libraries targeting analysts and developers
 *  	https://lakshmidrip.github.io/DRIP/
 *  
 *  DRIP is composed of four main libraries:
 *  
 *  - DRIP Fixed Income - https://lakshmidrip.github.io/DRIP-Fixed-Income/
 *  - DRIP Asset Allocation - https://lakshmidrip.github.io/DRIP-Asset-Allocation/
 *  - DRIP Numerical Optimizer - https://lakshmidrip.github.io/DRIP-Numerical-Optimizer/
 *  - DRIP Statistical Learning - https://lakshmidrip.github.io/DRIP-Statistical-Learning/
 * 
 *  - DRIP Fixed Income: Library for Instrument/Trading Conventions, Treasury Futures/Options,
 *  	Funding/Forward/Overnight Curves, Multi-Curve Construction/Valuation, Collateral Valuation and XVA
 *  	Metric Generation, Calibration and Hedge Attributions, Statistical Curve Construction, Bond RV
 *  	Metrics, Stochastic Evolution and Option Pricing, Interest Rate Dynamics and Option Pricing, LMM
 *  	Extensions/Calibrations/Greeks, Algorithmic Differentiation, and Asset Backed Models and Analytics.
 * 
 *  - DRIP Asset Allocation: Library for model libraries for MPT framework, Black Litterman Strategy
 *  	Incorporator, Holdings Constraint, and Transaction Costs.
 * 
 *  - DRIP Numerical Optimizer: Library for Numerical Optimization and Spline Functionality.
 * 
 *  - DRIP Statistical Learning: Library for Statistical Evaluation and Machine Learning.
 * 
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *   	you may not use this file except in compliance with the License.
 *   
 *  You may obtain a copy of the License at
 *  	http://www.apache.org/licenses/LICENSE-2.0
 *  
 *  Unless required by applicable law or agreed to in writing, software
 *  	distributed under the License is distributed on an "AS IS" BASIS,
 *  	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  
 *  See the License for the specific language governing permissions and
 *  	limitations under the License.
 */

/**
 * KKTNecessarySufficientConditions carries out the Zero and the First Order Necessary and the Second Order
 * 	Sufficiency Checks for a Constrained KKT Optimization Problem. The References are:
 * 
 * 	- Boyd, S., and L. van den Berghe (2009): Convex Optimization, Cambridge University Press, Cambridge UK.
 * 
 * 	- Eustaquio, R., E. Karas, and A. Ribeiro (2008): Constraint Qualification for Nonlinear Programming,
 * 		Technical Report, Federal University of Parana.
 * 
 * 	- Karush, A. (1939): Minima of Functions of Several Variables with Inequalities as Side Constraints,
 * 		M. Sc., University of Chicago, Chicago IL.
 * 
 * 	- Kuhn, H. W., and A. W. Tucker (1951): Nonlinear Programming, Proceedings of the Second Berkeley
 * 		Symposium, University of California, Berkeley CA 481-492.
 * 
 * 	- Ruszczynski, A. (2006): Nonlinear Optimization, Princeton University Press, Princeton NJ.
 * 
 * @author Lakshmi Krishnamurthy
 */

public class KKTNecessarySufficientConditions
{

	private static final RdToR1 ObjectiveFunction (
		final double x0,
		final double x1,
		final double x2)
		throws Exception
	{
		return new RdToR1 (
			null
		)
		{
			@Override public int dimension()
			{
				return 3;
			}

			@Override public double evaluate (
				final double[] variateArray)
				throws Exception
			{
				return (variateArray[0] - x0) * (variateArray[0] - x0) +
					(variateArray[1] - x1) * (variateArray[1] - x1) +
					(variateArray[2] - x2) * (variateArray[2] - x2);
			}

			@Override public double[] jacobian (
				final double[] variateArray)
			{
				return new double[]
				{
					2. * (x0 - variateArray[0]),
					2. * (x1 - variateArray[1]),
					2. * (x2 - variateArray[2])
				};
			}

			@Override public double[][] hessian (
				final double[] variateArray)
			{
				return new double[][]
				{
					{2., 0., 0.},
					{0., 2., 0.},
					{0., 0., 2.}
				};
			}
		};
	}

	private static final RdToR1 RightConstraintFunction (
		final double deadCenter,
		final int dimension,
		final double halfWidth,
		final boolean signFlip)
		throws Exception
	{
		return new RdToR1 (
			null
		)
		{
			@Override public int dimension()
			{
				return 3;
			}

			@Override public double evaluate (
				final double[] variateArray)
				throws Exception
			{
				return (signFlip ? -1. : 1.) * (deadCenter + halfWidth - variateArray[dimension]);
			}

			@Override public double[] jacobian (
				final double[] variateArray)
			{
				return new double[]
				{
					dimension == 0 ? (signFlip ? -1. : 1.) * -1. : 0.,
					dimension == 1 ? (signFlip ? -1. : 1.) * -1. : 0.,
					dimension == 2 ? (signFlip ? -1. : 1.) * -1. : 0.
				};
			}

			@Override public double[][] hessian (
				final double[] variateArray)
			{
				return new double[][]
				{
					{0., 0., 0.},
					{0., 0., 0.},
					{0., 0., 0.}
				};
			}
		};
	}

	private static final RdToR1 LeftConstraintFunction (
		final double deadCenter,
		final int dimension,
		final double halfWidth,
		final boolean signFlip)
		throws Exception
	{
		return new RdToR1 (
			null
		)
		{
			@Override public int dimension()
			{
				return 3;
			}

			@Override public double evaluate (
				final double[] variateArray)
				throws Exception
			{
				return (signFlip ? -1. : 1.) * (variateArray[dimension] - deadCenter + halfWidth);
			}

			@Override public double[] jacobian (
				final double[] variateArray)
			{
				return new double[]
				{
					dimension == 0 ? (signFlip ? -1. : 1.) * 1. : 0.,
					dimension == 1 ? (signFlip ? -1. : 1.) * 1. : 0.,
					dimension == 2 ? (signFlip ? -1. : 1.) * 1. : 0.
				};
			}

			@Override public double[][] hessian (
				final double[] variateArray)
			{
				return new double[][]
				{
					{0., 0., 0.},
					{0., 0., 0.},
					{0., 0., 0.}
				};
			}
		};
	}

	private static final RdToR1[] ConstraintFunctionArray (
		final double x0,
		final double x1,
		final double x2,
		final double halfWidth,
		final boolean signFlip)
		throws Exception
	{
		return new RdToR1[] {
			LeftConstraintFunction (
				x0,
				0,
				halfWidth,
				signFlip
			),
			RightConstraintFunction (
				x0,
				0,
				halfWidth,
				signFlip
			),
			LeftConstraintFunction (
				x1,
				1,
				halfWidth,
				signFlip
			),
			RightConstraintFunction (
				x1,
				1,
				halfWidth,
				signFlip
			),
			LeftConstraintFunction (
				x2,
				2,
				halfWidth,
				signFlip
			),
			RightConstraintFunction (
				x2,
				2,
				halfWidth,
				signFlip
			)
		};
	}
	public static final void main (
		final String[] argumentArray)
		throws Exception
	{
		EnvManager.InitEnv (
			""
		);

		double x0 = 1.;
		double x1 = 2.;
		double x2 = 3.;
		double halfWidth = 1.;

		RdToR1 objectiveFunction = ObjectiveFunction (
			x0,
			x1,
			x2
		);

		double[] variateArray = new double[]
		{
			x0,
			x1,
			x2
		};

		FritzJohnMultipliers karushKuhnTuckerMultipliers = FritzJohnMultipliers.KarushKuhnTucker (
			null,
			new BarrierFixedPointFinder (
				objectiveFunction,
				ConstraintFunctionArray (
					x0,
					x1,
					x2,
					halfWidth,
					false
				),
				new InteriorPointBarrierControl (
					InteriorPointBarrierControl.VARIATE_CONSTRAINT_SEQUENCE_CONVERGENCE,
					5.0e-06,
					1.0e-07,
					1.0e+10,
					0.5,
					20
				),
				null
			).solve (
				new double[]
				{
					x0 + 0.25 * halfWidth,
					x1 + 0.25 * halfWidth,
					x2 + 0.25 * halfWidth
				}
			).constraintMultiplierArray()
		);

		OptimizationFramework optimizationFramework = new OptimizationFramework (
			objectiveFunction,
			null,
			ConstraintFunctionArray (
				x0,
				x1,
				x2,
				halfWidth,
				true
			)
		);

		System.out.println();

		System.out.println ("\t||---------------------------------------------------||");

		System.out.println ("\t||    KKT NECESSARY & SUFFICIENT CONDITIONS CHECK    ||");

		System.out.println ("\t||---------------------------------------------------||");

		System.out.println ("\t|| KKT Multiplier Compatibility             : " +
			optimizationFramework.isCompatible (
				karushKuhnTuckerMultipliers
			) + "   ||"
		);

		System.out.println ("\t|| Dual Feasibility Check                   : " +
			karushKuhnTuckerMultipliers.dualFeasibilityCheck() + "   ||"
		);

		System.out.println ("\t|| Primal Feasibility Check                 : " +
			optimizationFramework.primalFeasibilityCheck (
				variateArray
			) + "   ||"
		);

		System.out.println ("\t|| Complementary Slackness Check            : " +
			optimizationFramework.complementarySlacknessCheck (
				karushKuhnTuckerMultipliers,
				variateArray
			) + "  ||"
		);

		System.out.println ("\t|| First Order Necessary Condition Check    : " +
			optimizationFramework.isFONC (
				karushKuhnTuckerMultipliers,
				variateArray
			) + "   ||"
		);

		System.out.println ("\t|| Second Order Sufficiency Condition Check : " +
			optimizationFramework.isSOSC (
				karushKuhnTuckerMultipliers,
				variateArray,
				true
			) + "   ||"
		);

		System.out.println ("\t||---------------------------------------------------||");

		System.out.println();

		System.out.println ("\t||------------------------------------------------------------------------------------------------------||");

		System.out.println ("\t||                 KKT NECESSARY & SUFFICIENT CONSTIONS - ZERO, FIRST, & SECOND ORDERS                  ||");

		System.out.println ("\t||------------------------------------------------------------------------------------------------------||");

		String[] necessarySufficientConditionOrderArray =
			optimizationFramework.necessarySufficientQualifier (
				karushKuhnTuckerMultipliers,
				variateArray,
				true
			).conditionOrder();

		for (int necessarySufficientConditionOrderIndex = 0;
			necessarySufficientConditionOrderIndex < necessarySufficientConditionOrderArray.length;
			++necessarySufficientConditionOrderIndex)
		{
			System.out.println (
				"\t|| " +
				necessarySufficientConditionOrderArray[necessarySufficientConditionOrderIndex]
			);
		}

		System.out.println ("\t||------------------------------------------------------------------------------------------------------||");

		System.out.println();
	}
}