Convex Optimization

Analogy to understand convex optimization !

Imagine you have a shape, like a bowl, and you want to find the lowest point inside the bowl. Convex optimization is like finding that lowest point in a special kind of shape called a convex shape.

A convex shape is one that is smooth and doesn't have any bumps or valleys. It's like a perfectly round hill or a bowl without any dents. Because it's smooth, you can easily find the lowest point inside it.

In convex optimization, we use math to solve problems by finding the lowest point (or sometimes the highest point) in these smooth shapes. We have a special function that tells us how high or low each point is, and we want to find the point that gives us the lowest value for that function.

We also have some rules or conditions that the points inside the shape need to follow. These rules help us define the shape and make sure it's a nice, smooth, and predictable shape.

By using math and special techniques, we can figure out the exact lowest point in the shape. This is useful in many areas, like designing efficient routes for cars, finding the best way to pack items into a box, or even training computers to learn from data.

So, convex optimization is like finding the lowest point in a smooth shape using math, and it helps us solve all kinds of problems in a smart and efficient way.

What is convex function ?

A convex function is a mathematical function that has a special property: when you connect any two points on the function's graph with a straight line, the line lies entirely above the graph.

Imagine drawing a curved line on a piece of paper. If the line is convex, it means that no matter which two points you choose on the line, the straight line you draw between them will never dip below the curve. It will always stay above or on the curve.

In other words, a convex function is like a hill or a mountain shape. It always curves upward and doesn't have any valleys or dips. It's like a smiley face!

The important thing about convex functions is that they have predictable behavior. If you want to find the minimum point on the curve, you know it will be at the bottom of the curve because the curve always goes up. And if you want to find the maximum point, you know it will be at the highest point of the curve.

Convex functions are used in many areas of mathematics, optimization, and machine learning. They help us solve problems efficiently and find optimal solutions.

What is convex optimziation ? ( From math literature )

Convex optimization refers to the field of mathematical optimization that deals with optimizing convex objective functions over convex sets. In convex optimization, the goal is to find the minimum (or maximum) value of a convex function within a feasible region defined by convex constraints.

A function is considered convex if, for any two points in its domain, the line segment connecting those points lies entirely above the graph of the function. In other words, a function is convex if its second derivative is non-negative over its entire domain.

Convex optimization has gained significant importance in various fields, including machine learning, operations research, economics, engineering, and finance, due to its desirable properties and wide range of applications.

Key characteristics of convex optimization include:

1. Convex Objective Function: The objective function to be minimized (or maximized) is convex, meaning that it has a non-negative second derivative. Convex functions have a single global minimum (or maximum) and no local minima (or maxima).
2. Convex Constraints: The feasible region or set of allowed solutions is defined by convex constraints. These constraints are typically linear or convex functions that restrict the search space for the optimization problem.
3. Optimality Conditions: Convex optimization problems have well-defined optimality conditions. If a convex function has a minimum (or maximum) point, it is also a global minimum (or maximum). Additionally, any local minimum (or maximum) is also a global minimum (or maximum).
4. Efficient Algorithms: Convex optimization problems can be solved efficiently using a variety of algorithms, including interior-point methods, gradient-based methods, and subgradient methods. These algorithms take advantage of the convexity of the problem to find the optimal solution efficiently.

Convex optimization provides a powerful framework for solving a wide range of optimization problems in a principled and efficient manner. Its applications in machine learning include linear regression, support vector machines, logistic regression, neural network training, and many more. By formulating problems as convex optimization problems, practitioners can leverage the rich theory and efficient algorithms available to find optimal solutions.

import cvxpy as cp
import numpy as np


# Define the variables
x = cp.Variable()
y = cp.Variable()


# Define the objective function
objective = cp.Minimize((x - 1)**2 + (y - 2)**2)


# Define the constraints
constraints = [x + y >= 1]


# Define the problem
problem = cp.Problem(objective, constraints)


# Solve the problem
problem.solve()


# Print the optimal solution and objective value
print("Optimal Solution:")
print("x =", x.value)
print("y =", y.value)
print("Optimal Objective Value:", problem.value)