Optimization Techniques in Machine Learning
(MAS5007)
Module-4
Convex Optimization Models: A Deterministic Optimization
Model-A General Solution Technique Based on Optimization
Problems-A Gambling Model with Unknown Win Probabilities.
Second order cone optimization, Semidefinite optimization,
Convex composite optimization.
A Deterministic Optimization Model is a type of mathematical optimization model in
which all the input data and parameters are known with certainty and do not involve
randomness or probabilistic elements. These models are widely used in operations
research, engineering, economics, and computer science where the environment and system
behaviours are predictable.
Key Characteristics:
1. Deterministic Nature: All variables, parameters, and outcomes are precisely known.
2. No Randomness: Unlike stochastic models, there is no uncertainty in the input.
3. Predictability: The same input will always produce the same output.
Types of Deterministic Optimization Models:
1. Linear Programming (LP)
Objective and constraints are linear.
Example: Minimize cost subject to resource constraints.
2. Integer Programming (IP)
Decision variables must take integer values.
3. Nonlinear Programming (NLP)
Either the objective or constraints (or both) are nonlinear.
4. Dynamic Programming (DP)
Problem is broken into subproblems and solved recursively.
5. Network Optimization
Deals with flow problems like shortest path, maximum flow, etc.
Applications:
Supply chain and logistics optimization
Scheduling and resource allocation
Network routing and bandwidth allocation
Energy management
Manufacturing and production planning
4. Solution Technique
Apply the appropriate deterministic technique:
For Linear Programming (Problem-A):
Graphical Method (if two variables)
Simplex Method
Dual Simplex Method
Interior-Point Method
Steps in Simplex Method (general approach):
1. Convert to standard form
2. Set up the initial simplex tableau
3. Identify the entering and leaving variables
4. Perform pivoting to update the tableau
5. Repeat until optimality condition is met
5. Implementation
Solve the model using:
Manual computation (for small problems)
Software tools:
o Python (PuLP, SciPy, CVXPY)
o MATLAB
o R (with lpSolve)
o Solver in Excel
6. Solution Interpretation
Interpret values of decision variables
Evaluate the optimal value of the objective function
Check for sensitivity or what-if analysis
7. Validation and Verification
Ensure the model correctly represents the real-world system
Test with different data sets or scenarios
Perform post-optimality analysis if needed
Second-order cone optimization (SOCO)
Second-order cone optimization (SOCO)—also known as second-order cone
programming (SOCP)—is a type of convex optimization problem that generalizes linear
and (convex) quadratic programming. It's particularly useful in problems where the
constraints or objectives involve norms or certain types of quadratic forms.
Semidefinite Programming
(Goto another PPT of Semidefinite Programming)
Gambling model with unknown win probabilities
A gambling model with unknown win probabilities is a framework for decision-
making under uncertainty, where the probabilities of outcomes (e.g., winning or
losing a bet) are not precisely known. This setup is common in real-world
gambling scenarios like sports betting, poker, or games with incomplete
information, where players must make decisions based on partial knowledge,
estimates, or observed data. The model can be studied as a convex composite
optimization problem when formulated with specific objectives, such as
maximizing expected utility or minimizing risk, often incorporating
regularization to handle uncertainty.
A Gambling Model with Unknown Win Probabilities is a type of decision-
making under uncertainty problem, where the player (or decision-maker) does
not know the exact probability of winning in a gambling scenario but must
make strategic choices to maximize expected reward or minimize risk over
time.
This situation is typically modeled using Bayesian decision theory, multi-
armed bandits, or reinforcement learning.
5. Objectives and Policies
Maximize expected total reward over T rounds
Minimize probability of ruin (capital hitting 0)
Identify best gambling strategy as fast as possible
6. Applications
Financial trading strategies with uncertain returns
Clinical trials (choose best treatment without full info)
Online advertising (which ad gets the most clicks)
Adaptive learning systems
7. Challenges
Exploration-exploitation trade-off
Short time horizons (limited capital or rounds)
Risk constraints (ruin probability)
Convex Composite Optimization is a class of optimization problems
where the objective function is a composition of a convex function and a smooth (possibly
non-linear) mapping. These problems arise in many applications, including machine learning,
signal processing, and control theory.