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();
    }
}