Will Yuan's Blog

In nonlinear programming, the Karush–Kuhn–Tucker (KKT) conditions are necessary conditions to determine whether a point is an extreme point. The necessary condition here means that the solution that satisfies the KKT conditions is not necessarily the optimal solution (e.g., saddle point), but if the KKT conditions are not satisfied, it must not be the optimal solution.

For convex programming, the KKT conditions are sufficient and necessary conditions to determine whether a point is an extreme point. If a point satisfies the conditions, it must be an extreme point and must be a global optimal solution.

Note: In a convex optimization problem, the objective function is convex and the domain is defined as a convex set.

Lagrangian Function

Common Commands

git init

Initialize the repository.

1

git init

Basic Concept

Tabu Search (TS) is a meta-heuristic algorithm that was first proposed by Glover in 1986. The algorithm avoids repeated searches by introducing a tabu table, and pardons some good solutions or states in tabu table through amnesty rules, so as to achieve a better global optimization effect.

Steps

Tabu Search algorithm typically includes the following key steps:

Particle swarm optimization (PSO) was first proposed by James Kennedy and Russell Eberhart in 1995, also known as particle swarm algorithm.

The basic idea of the particle swarm algorithm comes from the study of the foraging behavior of bird flocks. Each particle can be regarded as a bird, and the process of searching for a solution is similar to the process of a flock of birds looking for food. In the process of searching for food, each bird knows the best location it has found. At the same time, information is shared within the flock, so that each bird also knows the best location the entire flock has found.

The advantage of PSO is that it is simple, easy to implement, has fewer parameters that need to be adjusted, and has better global optimization capabilities.

Basic Concept

Bug Description

• IDE: IntelliJ IDEA 2021.3
• Language: Java
• Error: Unable to find main class

I have created a multi-module Spring Boot project that will serve as a tool library for other projects to use. When building the multi-module Spring Boot project, the IDE prompts the following error: Unable to find main class.

Solution

Bug Description

• IDE: IntelliJ IDEA 2021.3
• Language: Java
• Error: Java package xxx does not exist

I imported a library into a service of a module in a multi-module Spring Boot project. The relevant import statement is written in the code, and the relevant dependency is also introduced in the pom.xml. When building the project, the IDE prompts this error: Java package xxx does not exist.

Solution

scipy.optimize

SciPy provides functions for minimizing (or maximizing) objective functions, possibly subject to constraints. It includes solvers for nonlinear problems (with support for both local and global optimization algorithms), linear programming, constrained and nonlinear least-squares, root finding, and curve fitting.

This is the official manual of scipy.optimize: Optimization and root finding (scipy.optimize) — SciPy v1.13.0 Manual

scipy.optimize.linprog is used here to solve the linear programming problem. More information about scipy.optimize.linprog: scipy.optimize.linprog — SciPy v1.13.0 Manual

Note:

For obtaining the minimum spanning tree, the Prim algorithm has been introduced before, and here is another algorithm: Kruskal algorithm.

Kruskal Algorithm Steps

• Step 1: Sorts all edges in the graph by weight from smallest to largest.

• Step 2: Try adding edges to the tree from smallest to largest, and if the newly added edge forms a loop with other edges in the tree, discard the edge and continue trying the other edges.

• Step 3: If $n-1$ edges are added to the tree, the minimum spanning tree is built, where $n$ is the number of vertices of the graph.

Note that in the process of adding edges to the tree, Disjoint Set Union (DSU) is used to determine if a loop is formed.

Minimum Spanning Tree

For an undirected graph, the Minimum Spanning Tree is a connected subgraph of the original graph, which contains all the vertices of the original graph, and the sum of its edge weights is the smallest. We can use Prim algorithm to get the minimum spanning tree.

Prim Algorithm Steps

The algorithm usually includes the following steps:

How to calculate the distance between two coordinate points (knowing longitude and latitude) in Python? Three methods are given here:

Implement the Haversine Formula

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import math
from math import radians, sin, cos, asin

def haversine(lat1, lon1, lat2, lon2):
    # The average radius of the earth is approximately 6371.393km
    EARTH_RADIUS = 6371

    # Convert to radians
    lat1 = radians(lat1)
    lon1 = radians(lon1)
    lat2 = radians(lat2)
    lon2 = radians(lon2)

    # Calculate the difference between converted latitude and longitude
    delta_lat = lat2 - lat1
    delta_lon = lon2 - lon1

    # Haversine formula
    temp = math.pow(sin(delta_lat / 2), 2) + cos(lat1) * cos(lat2) * math.pow(sin(delta_lon / 2), 2)
    distance = 2 * asin(math.sqrt(temp)) * EARTH_RADIUS

    return distance

new_dist = haversine(36.1628, 114.2581, 36.5935, 114.6296)
print("The distance calculated using the Haversine formula is:", new_dist, "km")

The output is as follows: